Espera que la longitud de una secuencia que contiene todas las palabras de una longitud dada.

Question

Corregir algunos alfabeto $\Sigma$ y un entero positivo $n$. ¿Cuál es el número esperado de letras aleatorias extraídas de $\Sigma$ hasta que toda la longitud-$n$ palabras están presentes?

Por ejemplo, supongamos $\Sigma = \{0,1\}.$, a Continuación, la cadena "10" contiene todos los posibles 1-letra de palabras, es decir, "0" y "1". La duración prevista para una cadena aleatoria es simplemente el cupón de colector problema con 2 tarjetas... así que la duración prevista es de 3.

Pero es más complicado cuando las palabras se pueden solapar. Para el mismo alfabeto y $n=2$ podemos ver que la cadena "00110" tiene todos los 2-letra de palabras, y me afirman que es el más corto de la cadena que hace. Pero ¿cuál es la duración esperada de una cadena aleatoria que contiene las cuatro cuerdas "00", "01", "10", y "11"? La costumbre de cupón-colector de enfoque no parece funcionar.

Answer 1

Bien, aquí tienes la solución, pero no es bastante.

Como indiqué en mi respuesta a Cubrir el tiempo de tablero de ajedrez (rey), no hay en principio ninguna dificultad en responder a esta pregunta. El cálculo de la espera de la cubierta el tiempo de un conjunto de patrones de $\cal S$ se reduce a calcular la espera de golpear tiempo de cada posible que no esté vacía subconjunto $A$$\cal S$:

$$\mathbb{E}(\text{cover time})=\sum_A (-1)^{|A|-1} \mathbb{E}(T_A)\tag1$$

Estos golpear a veces se definen por $T_A=\inf(n\geq 0: X_n\in A)$. Estos, a su vez, se puede encontrar utilizando una técnica de la Sección 14.3 (Patrones III) de los Problemas y las Instantáneas desde el Mundo de la Probabilidad por Blom, Holst, y Sandell.

Por ejemplo con cadenas de longitud dos nos encontramos $$\mathbb{E}(T_{00,01,10,11})=2$$ $$\mathbb{E}(T_{00,01,10})=\mathbb{E}(T_{01,10,11})=5/2,\quad \mathbb{E}(T_{00,10,11})= \mathbb{E}(T_{00,01,11})=9/4$$ $$\mathbb{E}(T_{00,01})=\mathbb{E}(T_{00,10})=\mathbb{E}(T_{00,11})=\mathbb{E}(T_{01,10})=\mathbb{E}(T_{01,11})=\mathbb{E}(T_{10,11})=3$$ $$\mathbb{E}(T_{00})=\mathbb{E}(T_{11})=6,\quad \mathbb{E}(T_{01})=\mathbb{E}(T_{10})=4$$

Conectar toda esta información en (1), encontramos que el tiempo de espera para ver todos los modelos de cuatro $00,01,10$, e $11$$19/2=9.5$.

Sólo por diversión, he calculado el tiempo de espera para ver todos los ocho patrones de longitud de tres a ${89259/ 3640}= 24.5217$.

Answer 2

Actualización: Esto está mal - lo siento, no entendí la pregunta, tengo entendido que estaban interesados en conseguir todas las permutaciones (palabras con letras diferentes).

---

Para $n=2$ no es difícil ver que la duración prevista es de 5 : duración prevista de la primera ejecución (2) + duración prevista de la segunda (2) + 1. Para $n>2$ me parece más difícil.

Aplicando el cupón-colector de enfoque, se podría decir que el número esperado de trata de recoger la $m$-th permutación (entre $n!$ permutaciones) es$1/p_m = n^n/(n!-m)$, por lo que

$$E_n = n^n \left( \frac{1}{1} + \frac{1}{2} + \dots +\frac{1}{n!} \right)=n^n H({n!})$$

Esto, por supuesto, es una aproximación, porque se supone que cada nueva letra de la secuencia da un nuevo $n$-palabra, independiente de los anteriores; pero la superposición debe introducir alguna dependencia. No está claro, sin embargo, el sentido de esta dependencia. Y esto, junto con el hecho de que un gran $n$ la probabilidad de que una palabra de ser una permutación (incluso para el "primer cupón") es baja, lleva a pensar que la aproximación podría ser razonable. Evidencia numérica ve a un acuerdo.

Por ejemplo: para $E_5 = 16777.7$, empíricamente llego $\approx 16730$.

---

Actualización: en Realidad no estamos interesados en conseguir todas las permutaciones ( $n!$ ), pero todas las palabras ($n^n$). El de arriba coupen-colector de enfoque también se puede aplicar, dándonos $E_n \approx n^n H(n^n) \sim n^{n+1} \log(n)$, pero la independencia de la asunción está menos justificado, y el resultado es menos preciso.

Podemos considerar cada palabra como un vértice en un grafo dirigido, o el estado de un doblemente estocástico de cadenas de Markov ($n$ igual no nulos entradas en cada columna de la fila). Estamos pidiendo, a continuación, sobre la cubierta del tiempo de esta cadena. Esto podría ayudar a localizar el material. Por ejemplo, aquí (sección 2.3) se afirma como un resultado conocido (pero las referencias que faltan) la asympotic

$$E_n \sim n^n \log(n)$$

También, ver aquí (página 11.3.3).