Me gustaría saber la respuesta exacta, así como una analítica de la solución a este problema.
Aquí está la respuesta exacta como una función de p=Pr, para varios valores de n. Deje L_n denotar la longitud de la secuencia de la primera vez que contiene una palabra repetida de longitud n. Directamente a la enumeración de las posibles secuencias, que nos encontramos (el uso de la Salvia) los siguientes resultados exactos:
n E(L_n | p=1/2) E(L_n | p)
- ---------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 5/2 -2*p^2 + 2*p + 2
2 35/8 2*p^4 - 4*p^3 - 3*p^2 + 5*p + 3
3 435/64 16*p^8 - 64*p^7 + 61*p^6 + 41*p^5 - 90*p^4 + 37*p^3 - 10*p^2 + 9*p + 4
4 2513/256 -64*p^18 + 576*p^17 - 1880*p^16 + 1984*p^15 + 3094*p^14 - 10682*p^13 + 9560*p^12 + 2050*p^11 - 9950*p^10 + 6696*p^9 - 841*p^8 - 898*p^7 + 420*p^6 + 8*p^5 - 129*p^4 + 54*p^3 - 12*p^2 + 14*p + 5
5 57922047/4194304 -13312*p^34 + 226304*p^33 - 1690752*p^32 + 7137280*p^31 - 17544144*p^30 + 18701616*p^29 + 29742468*p^28 - 163840744*p^27 + 339947916*p^26 - 413989056*p^25 + 268118367*p^24 + 32316996*p^23 - 278576119*p^22 + 333006671*p^21 - 241401935*p^20 + 128354791*p^19 - 59474305*p^18 + 28069920*p^17 - 12055855*p^16 + 2638562*p^15 + 1497144*p^14 - 1982176*p^13 + 1101961*p^12 - 307798*p^11 - 27907*p^10 + 68859*p^9 - 31985*p^8 + 9681*p^7 - 3530*p^6 + 1571*p^5 - 678*p^4 + 195*p^3 - 26*p^2 + 20*p + 6
En particular, tenemos la exacta expectativa \text{E}(L_4 | p={1\over 2})=2513/256 = 9.8164...
(Cross-check: simulaciones de Monte Carlo para n=1,2,3,4,5 son consistentes con estos valores numéricos a tres cifras significativas.)
El "directo enumeración" método calcula la expectativa de la siguiente manera, usando 1 0 a representar a \text{H} \text{T} respectivamente:
Deje S_n denota el conjunto de todas las posibles secuencias binarias que se puede obtener al voltear la moneda hasta una longitud-n repetición se produce. Ahora L_n es sólo la longitud de una secuencia, de manera que
\begin{align}\text{E}(L_n\mid p)&=\sum_{s\in S_n}\text{length}(s)\Pr(s)\\[2ex]
\end{align}
donde \Pr(s) = p^{\text{sum}(s)}(1-p)^{\text{length}(s)-\text{sum}(s)} with \text{sum}(s) being the number of 1s in s, and \text{length}(s)-\text{sum}(s) being the number of 0s in s.
The program at the above-given link implements this by starting with a list of all length-n sequences, then "growing" each of them in all possible ways by appending bits, until they stop growing when a repetition occurs. The result (stop_seqs(n)) is a listing of the set S_n, from which the expectation is calculated by the above summation.
Apparently, no closed-form solution is known for arbitrary nincluso en el caso de una moneda; sin embargo, asintótica resultados para este caso se han obtenido, por ejemplo, por Karnin, E. (1983), quien mostró que
E\left(L_n\,{\Large\vert}\,p={\small{1\over 2}}\right)\sim\sqrt{\pi\,2^n},\ \text{ as }n\to\infty,
que es igual que decir
\lim_{n\to\infty}{E(L_n\mid p={1\over 2}) \over \sqrt{\pi\,2^n}}=1.
But this is a poor approximation in your case of n=4, since \sqrt{\pi\,2^4}=7.0898\ldots, mientras que el valor exacto (por contacto directo de la enumeración)
es \text{E}(L_4\mid p={1\over 2})=2513/256 = 9.8164\ldots
PD: tengo la fuerte sospecha de que el entrevistador es la intención de la pregunta era el siguiente notable variante, que se obtiene por el solo hecho de cambiar una palabra en el citado párrafo (especialmente desde que en ambos ejemplos es la inicial de la secuencia de los cuatro lanzamientos que se repite):
Se están moviendo de un tirón una moneda hasta que la inicial de la secuencia de cuatro tirones se repite. Las secuencias se pueden solapar. Por ejemplo, si usted mueve de un tirón HTHTHT, la secuencia HTHT aparece en volteretas 1-4 y 3-6. En este caso, hemos hecho después de 6 tirones. Como otro ejemplo, si usted mueve de un tirón HHTTHHTT, la secuencia de HHTT repite en volteretas 1-4 y 5-8, y hemos terminado después de 8 lanzamientos. ¿Cuál es el número esperado de lanzamientos?
La respuesta a esta versión es el número entero n+2^n (donde n es la inicial del segmento de longitud, por ejemplo,n=4), no importa cuál puede ser el valor de p=\Pr(\text{H}) -- suponiendo que p es constante, 0<p<1, y que los lanzamientos son independientes!
Este resultado general puede ser demostrado por una menor variación de la prueba del Teorema 2 en este artículo en línea. El caso especial de p={1\over 2} puede ser demostrado por el siguiente argumento dado en el artículo enlazado por Karnin: teniendo en cuenta las palabras a los estados de una cadena de Markov, la matriz de transición se ve doblemente estocástica, lo que implica que el invariante de distribución asigna a cada estado la misma probabilidad de 2^{-n}; en consecuencia, se espera que el tiempo de espera (después de que el segmento inicial está formada) es el recíproco de este, es decir, 2^n, y el total esperado el tiempo de espera es, por tanto, n+2^n.
