Este equipo especializado luego de días de investigación y recopilación de de datos, hemos dado con los datos necesarios, esperamos que resulte de gran utilidad para tu proyecto.
Solución:
Resolver un conjunto de recurrencias lineales es de hecho una buena y elemental forma de hacerlo, pero si resuelve las recurrencias en la respuesta de @Canardini, que hice usando Wolfram alpha, encontrará que la respuesta es $ E_X = 46656 = 6 ^ 6 $. Este es un número tan especial que podría preguntarse si hay una explicación más fundamental, y de hecho la hay, usando teoremas más poderosos de las cadenas de Markov.
Reclamo: Si lo desea string $ x $ tiene la propiedad de que dos copias de $ x $ no se puede superponer (lo que es válido para $ x = 123456 $ en la pregunta de OP pero no es válido para, por ejemplo, $ x = 111111 $ o $ x = 121212 $), luego el tiempo esperado hasta la primera aparición de $ x $ es $ 6 ^ L $ dónde $ L $ es la longitud de $ x $.
Considere una cadena de Markov con $ 6 ^ 6 $ estados, donde cada estado es una secuencia posible en $ 1,2,3,4,5,6 ^ 6 $ y registra el ultimo $ 6 $ rollos. Cada estado puede hacer la transición a $ 6 $ estados (es decir, tiene “grado externo” $ 6 $) con igual problema $ 1/6 $. Por ejemplo, el estado $ color rojo 1 13462 $ puede hacer la transición a $ 13462 color azul j $ dónde $ color azul j $ puede ser cualquiera de $ 1,2,3,4,5,6 $. El rojo $ color rojo 1 $ representa el resultado de la tirada de dados más antiguo que ha “caducado” y el azul $ color azul j $ representa el resultado de la tirada más reciente. Tenga en cuenta que cada estado también tiene “en grado” $ 6 $, es decir, solo $ 6 $ los estados pueden hacer la transición a él. (Los bucles propios son posibles y cuentan tanto como grados de entrada como de salida).
Es obvio que tal Cadena de Markov es aperiódica, positiva recurrente, irreductible, ergódica, etc., todo lo bueno. Además, debido a que cada estado de grado $ = $ fuera de grado $ = 6 $, la distribución estacionaria única de la cadena $ pi $ (también su distribución limitante) es el $ 6 ^ 6 $-vector largo cuyas entradas son $ 6 ^ – 6 $.
Un teorema poderoso (pero algo “intuitivamente obvio?”) Dice que, si $ tau_ xx $ es el tiempo de visita del estado $ x $ volver al estado $ x $, luego:
Teorema: para una cadena de Markov recurrente positiva, con distribución estacionaria $ pi, E[tau_xx] = 1 / pi_x $ para cualquier estado $ x $.
Por ejemplo, consulte la Proposición 2.6 de estas notas o el Teorema 1.19 de estas notas o (para una versión ligeramente diferente) wikipedia
En mi humilde opinión, este teorema es “intuitivamente obvio” en el siguiente sentido: la distribución límite $ pi $ significa que, a la larga, la cadena gastará $ pi_x $ fracción del tiempo en estado $ x $, por lo que tiene sentido que el tiempo entre visitas $ tau_ xx $ tiene un valor esperado de $ 1 / pi_x $. Sin embargo, tal argumento “intuitivo” no es riguroso, y el teorema tiene una prueba no trivial que hace uso de la recurrencia positiva.
De todos modos, basado en este teorema, y dejando $ x = 123456 $ el estado que nos interesa, tenemos $ E[tau_xx] = 1/6 ^ – 6 = 6 ^ 6 $. Es decir, si acabamos de rodar $ 123456 $, luego el tiempo esperado para lanzar el siguiente $ 123456 $ es $ 6 ^ 6 $. Esto no es lo mismo que la pregunta OP. Sin embargo, si acabamos de rodar $ 123456 $, entonces ninguno de estos resultados antiguos puede formar parte de la siguiente $ 123456 $, y por lo tanto esto es equivalente a rodar desde el principio (cuando el “historial” de los rollos es el vacío string). Este es un resultado directo del hecho de que dos cadenas de $ 123456 $ no puede superponerse. Entonces el mismo tiempo esperado $ 6 ^ 6 $ también responde a la pregunta OP.
Apéndice: para algunas otras cadenas, este teorema también proporciona una forma rápida de encontrar el tiempo esperado de la primera aparición. Por ejemplo, considere $ y = 111111 $. El mismo teorema dice que $ E[tau_yy] = 6 ^ 6 $. Pero también es obvio que la revisión puede ocurrir de inmediato (si la siguiente tirada es $ 1 $) o mucho más tarde. Es decir:
$$ E[tau_yy] = 1 + ( frac16 times 0 + frac56 times E[T_y]) $$
dónde $ T_y = $ tiempo hasta la primera aparición de $ y $ comenzando sin un historial útil (incluido el caso de comenzar desde cero, es decir, el historial vacío). Resolviendo esto tenemos:
$$ E[T_y] = (6 ^ 6 – 1) times frac65 = 55986 $$
que se puede verificar fácilmente resolviendo el conjunto correspondiente de recurrencias lineales para el string $ y = 111111 $.
Insinuación :
Imagínelo como una cadena de Markov. Empiezas en el estado $ X $ también conocido como “No logré obtener el string $ “123456” $.
El siguiente estado es $ 1 $, de lo contrario vuelvo al estado $ X $. Si estoy en el estado $ 1 $, el siguiente estado es $ 2 $, de lo contrario no puedo construir el string. En el último caso, o tienes un $ 1 $ y no empiezas de cero, o tienes $ 3,4,5 $ o $ 6 $.
Misma lógica para el estado $ 2,3,4,5 $.
Dejar $ E_m $ definir el número esperado de rollos necesarios del estado $ m $ para obtener el string $ 123456 $.
Trivialmente $ E_6 = 0 $.
$$ E_X = 1 + frac 1 6 E_1 + frac 5 6 E_X $$$$ E_1 = 1 + frac 1 6 E_1 + frac 4 6 E_X + frac 1 6 E_2 $$$$ E_2 = 1 + frac 1 6 E_1 + frac 4 6 E_X + frac 1 6 E_3 $$$$ E_3 = 1 + frac 1 6 E_1 + frac 4 6 E_X + frac 1 6 E_4 $$$$ E_4 = 1 + frac 1 6 E_1 + frac 4 6 E_X + frac 1 6 E_5 $$$$ E_5 = 1 + frac 1 6 E_1 + frac 4 6 E_X + frac 1 6 E_6 $$
Resuelves ese sistema de ecuaciones y tu respuesta es $ E_X $.
Por lo general, modelamos la situación con una cadena de Markov con los estados como en la siguiente imagen:
1/6 1/6 1/6 1/6 1/6 1/6
(*) -->-- *1 -->-- *12 -->-- *123 -->-- *1234 -->-- *12345 -->-- [*123456]
Initial Final
0 1 2 3 4 5 6
y también hay flechas que van hacia atrás con las probabilidades correspondientes que se extraerán de la siguiente matriz de Markov del proceso:
$$ A = begin bmatrix 5/6 & 1/6 \ 4/6 & 1/6 & 1/6 \ 4/6 & 1/6 & & 1/6 \ 4/6 & 1 / 6 & & & 1/6 \ 4/6 & 1/6 & & & & 1/6 \ 4/6 & 1/6 & & & & & 1/6 \ & & & & & & 1 \ end bmatrix . $$
(El estado $ 6 $ se hizo absorbente. Esto no nos importa.)
Encima, $ * $ es un reemplazo de “cualquier palabra (string, incluido el vacío) que no termina en $ 1 $“. También usamos $ 0,1,2,3,4,5,6, $ en lugar de tener una notación más simple. Dado que la primera notación que viene ahora es $ s_k $ para el número esperado de pasos para comenzar en $ k = * puntos k $ (bien, $ 0 = * $,) y terminan en $ 6 = * 123456 $. Por supuesto, $ s_6 = 0 $. Tenemos el obvio sistema de ecuaciones de Markov:
$$ left { begin alineado s_0 color rojo -1 & = frac 56s_0 + frac 16s_1 \ s_1 color rojo -1 & = frac 46s_0 + frac 16s_1 + frac 16s_2 \ s_2 color rojo -1 & = frac 46s_0 + frac 16s_1 qquad + frac 16s_3 \ s_3 color rojo -1 & = frac 46s_0 + frac 16s_1 qquad qquad + frac 16s_4 \ s_4 color rojo -1 & = frac 46s_0 + frac 16s_1 qquad qquad qquad + frac 16s_5 \ s_5 color rojo -1 & = frac 46s_0 + frac 16s_1 qquad qquad qquad qquad + frac 16s_6 \ s_6 & = 0 end alineado right. $$
Edición posterior:Corregido y respuesta completa. (Después de las vacaciones, ahora tenemos las habituales teorías de la relatividad general que gobiernan el tiempo y el espacio).
La primera ecuación corresponde a los siguientes pensamientos. Supongamos que estamos en el estado $ 0 = * $. Existen $ s_0> 0 $ pasos hasta llegar al estado final $ 6 = * 123456 $. Así que demos un paso (imaginario). Aterrizamos
- con probabilidad $ 5/6 $ de nuevo en $ 0 $, de donde más necesitamos en media $ s_0 $ pasos, y
- con probabilidad $ 1/6 $ en $ 1 $, de donde más necesitamos en media $ s_1 $ pasos.
Entonces, después del paso imaginario, necesitamos $ frac 56s_0 + frac 16s_1 $ pasos. Esto corresponde a $ s_0 color rojo -1 $. Las otras ecuaciones tienen motivaciones markovianas similares.
Esta solución del sistema es
$$ begin alineado s_0 & = 6 ^ 6 = 46656 , \ s_1 & = 6 ^ 6 – 6 ^ 1 = 46650 , \ s_2 & = 6 ^ 6 – 6 ^ 2 = 46620 , s_3 & = 6 ^ 6 – 6 ^ 2 = 46440 , \ s_4 & = 6 ^ 6 – 6 ^ 2 = 45360 , \ s_5 & = 6 ^ 6 – 6 ^ 5 = 38880 , \ s_6 & = 6 ^ 6 – 6 ^ 6 = 0 . end alineado $$
Entonces necesitamos en promedio $ 6 ^ 6 $ pasos desde el estado inicial hasta el estado final. Como subproducto del cálculo también obtenemos la información que hay en promedio $ 6 ^ 6-6 ^ k $ pasos, si partiéramos del estado $ k = * 12 puntos k $ hasta llegar a la final $ 6 = * 123456 $.
(Por favor ignore lo siguiente si es molesto).
Aquí hay una simulación lenta usando python / numpy / sage:
import numpy as np
d = np.random.random_integers(1, 6, 6^9) # 6^9 times rolling dices in an array
e = np.stack( [d[0:-5], d[1:-4], d[2:-3], d[3:-2], d[4:-1], d[5:]] )
patterns, count = np.unique(e, axis=1, return_counts=True)
N = 6^4 + 2*6^3 + 3*6^2 + 4*6 + 5
patterns[:, N]
count[N]
Resultados esta vez:
array([1, 2, 3, 4, 5, 6])
212
Así que en un largo string de longitud $ 6 ^ 9 $ tenemos el patrón array([1, 2, 3, 4, 5, 6]) algunos $ 212 $ veces, esto está cerca de $ 6 ^ 3 $, por lo que esperamos una media cerca $ 6 ^ 6 = 6 ^ 9/6 ^ 3 $.
valoraciones y reseñas
Si te ha resultado provechoso este artículo, sería de mucha ayuda si lo compartes con otros entusiastas de la programación de esta manera contrubuyes a dar difusión a nuestro contenido.