Número esperado de lanzar una moneda para obtener N consecutivos, dado M consecutivos

Question

Interviewstreet tuvo su segundo CodeSprint en enero, que incluyó la siguiente pregunta. La programación respuesta es publicado, pero no incluye una explicación estadística.

(Usted puede ver el problema original y publicado solución al iniciar sesión en la Interviewstreet sitio web con Google creds y, a continuación, ir al lanzar una Moneda problema de esta página.)

Lanzar Una Moneda

Usted tiene un imparcial de la moneda que desea mantener tirar hasta obtener N consecutivos cabezas. Has lanzado la moneda M veces y, sorprendentemente, todos los lanzamientos resultó en la cabeza.

¿Cuál es el número esperado de lanzamientos adicionales necesarios hasta obtener N consecutivas de los jefes?

Entrada:
La primera línea contiene el número de casos de T. Cada una de las siguiente líneas T contiene dos números de N y M.

Salida:
La salida de las líneas T que contiene la respuesta para el correspondiente caso de prueba. Impresión de la respuesta redondeado a exactamente 2 decimales.

Entrada De Ejemplo:
4
2 0
2 1
3 3
3 2

Ejemplo De Salida:
6.00
4.00
0.00
8.00

Ejemplo De Explicaciones:
Si N = 2 y M = 0, usted necesita para mantener a tirar la moneda hasta obtener 2 consecutivos cabezas. No es difícil mostrar que, en promedio, 6 de lanzar una moneda son necesarios.
Si N = 2 y M = 1, se necesitan de 2 consecutivos cabezas y ya tiene 1. Usted necesita para lanzar una vez más, no importa qué. En el primer sorteo, si te cabezas, está hecho. De lo contrario, usted necesita para volver a empezar, como el consecutivo contador se restablece, y que necesita para mantener tirar la moneda hasta obtener N=2 consecutivos cabezas. El número esperado de lanzar una moneda es así 1 + (0.5 * 0 + 0.5 * 6) = 4.0 Si N = 3 y M = 3, ya tiene 3 cabezas, por lo que no necesita de más lanzamientos.

Todas las ecuaciones matemáticas que se me ocurrió con las respuestas correctas para la muestra de entrada de datos mencionadas anteriormente, pero estaba equivocado para todos los otros conjuntos de entrada (que no conoce). Su solución programática parece resolver el problema muy diferentes de mi try-para-llegar-con-un-ecuación de método. Por favor alguien puede explicar cómo llegar a una ecuación que podría resolver esto?

Answer 1

Este es un computacional ejercicio, por tanto, pensar de forma recursiva. El estado actual de la moneda flipping es determinado por el par ordenado $(N,M)$$N\ge M\ge 0$. Deje que el número esperado de lanzamientos para llegar a $N$ consecutivos cabezas ser $e(N,M)$:

(1) Hay un 50% de probabilidad de que el siguiente turno será cabezas, teniendo al estado $(N,M+1)$, y un 50% de probabilidad de que el siguiente turno será colas, teniendo al estado $(N,0)$. Esto cuesta un flip. Por lo tanto, la expectativa (de forma recursiva) está dada por

$$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$$

(2) Base conditions: you have already stipulated that

$$e(N,0) = 2^{N+1}-2$$

and obviously

$$e(N,N) = 0$$

(no more flips are needed).

Here's the corresponding Mathematica program (including caching of intermediate results to speed up the recursion, which effectively makes it a dynamic programming solution):

e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0

The program would look similar in other programming languages that support recursion. Mathematically, we can verify that $e(N,M) = 2^{N+1} - 2^{M+1}$ simply by checking the recursion, because it obviously holds for the base cases:

$$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$$

which is true for any $M$ and $N$, QED.

---

More generally, the same approach will establish that $e(N,M) = \frac{p^{-N} - p^{M}}{1-p}$ when the coin has probability $p$ of heads. The hard part is working out the base condition $e(N,0)$. That is done by chasing the recursion out $N$ steps until finally $e(N,0)$ is expressed in terms of itself and solving:

$$\eqalign{ e(N,0) y= 1 + p e(N,1) + (1-p) e(n,0) \\ Y= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ Y= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$$

Answer 2

Para resolver este problema, voy a utilizar procesos estocásticos, los tiempos de parada, y la programación dinámica.

En primer lugar, algunas definiciones:

$$X_n \doteq \#\text{(of consecutive heads after the nth flip)}$$ También se permite un valor de $X_0$ a la media del número consecutivo de los jefes antes de empezar. Así, por $X_0 = 0$ y la secuencia de lanzamientos HHTHHHTHTTHH, los correspondientes valores de $X$ son 120123010012. Si tuviéramos $X_0 = M$, los valores de X (M+1)(M+2)0123010012.

A continuación, defina los siguientes tiempos de parada: $$\tau_N \doteq \min\{k: X_k = N\} \text{ and } \tau_0 \doteq \min\{k > 1: X_k = 0\} $$

El valor que estamos buscando es el valor esperado de $\tau_N$, el número de lanzamientos que se necesita para observar N consecutivos voltea $(X_{\tau_N} = N)$, dado que ya hemos observado M consecutivos voltea $(X_0 = M)$. Suponga $M \leq N$ como la respuesta es trivialmente 0 en caso contrario. Calculamos:

$$E[\tau_N|X_0 =M] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =M] $$ $$ = (N-M)(\frac{1}{2})^{N-M} + E[\tau_0|\tau_N > \tau_0,X_0 =M] + (1 - (\frac{1}{2})^{N-M})E[\tau_N|X_0 = 0]$$ Esto nos deja para calcular los últimos dos condicional expectativas.

El primero se corresponde con el número esperado de lanzamientos antes de conseguir una cola suponiendo una cola que se volcó antes de N consecutivos cabezas se observan asumiendo que se empiece con M consecutivos cabezas. No es demasiado difícil ver que

$$E[\tau_0|\tau_N > \tau_0,X_0 =M] = \sum^{N-M}_{j=1}(j)(\frac{1}{2})^j = 2 - (N-M+2)(\frac{1}{2})^{N-M}$$

Ahora todo lo que tenemos que hacer es calcular el segundo esperanza condicional que se corresponde con el número esperado de lanzamientos que se necesita para observar N consecutivos cabezas, empezando por 0. Con cálculos similares, vemos que

$$E[\tau_N|X_0 = 0] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =0]$$ $$ = N(\frac{1}{2})^{N} + E[\tau_0|\tau_N > \tau_0,X_0 =0] + (1 - (\frac{1}{2})^N)E[\tau_N|X_0 = 0]$$ $$= 2^N\lbrace N(\frac{1}{2})^{N} + (2 - (N+2)(\frac{1}{2})^{N})\rbrace$$ $$ = 2^{N+1} - 2$$

Esto le da una respuesta final de:

$$E[\tau_N|X_0 =M] = (N-M)(\frac{1}{2})^{N-M} + 2 - (N-M+2)(\frac{1}{2})^{N-M} + (1 - (\frac{1}{2})^{N-M})(2^{N+1} - 2)$$ $$ = 2^{N+1}-2^{M+1}$$

Esto está de acuerdo con los cuatro casos de prueba que he mencionado. Con una simple respuesta, puede haber una manera más fácil de calcular esto.

Answer 3

Advertencia: el siguiente no puede ser considerado como una respuesta apropiada en que no proporciona una forma cerrada de la solución a la pregunta, esp. cuando se compara con las respuestas anteriores. Yo sin embargo se encontró que el enfoque lo suficientemente interesante para trabajar la condición de distribución.

Considerar la cuestión preliminar de obtener una secuencia de $N$ jefes de $k$ lanza, con una probabilidad de $1-p(N,k)$. Esta está dada por la fórmula de recurrencia $$ p(N,k) = \begin{cases} 1 &\text{if } k<N\\ \sum_{m=1}^{N} \frac{1}{2^m}p(N,k-m) &\text{else}\\ \end{casos} $$ De hecho, mi razonamiento es que no consecutivas $N$ jefes de $k$ sorteos se puede descomponer según la primera aparición de una cola de salida de la primera $N$ tiros. Acondicionado en si esta primera cola se produce en el primer, segundo, ..., $N$th dibujar conduce a esta relación de recurrencia.

Luego, la probabilidad de obtener el primer consecutivos N de las cabezas en la $m\ge N$ tiros es $$ p(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N<m<2N+1 \end{casos} $$ El primer caso es auto-explicativo. el segundo caso corresponde a una cola que se produzcan en el $m-N-1$th dibujar, seguido por $N$ cabezas, y el último caso se prohíbe $N$ consecutivos cabezas antes de la $m-N-1$th dibujar. (Los dos últimos casos puede ser condensado en una sola, por supuesto!)

Ahora, la probabilidad de obtener $M$ cabezas de los primeros, y los primeros consecutivas $N$ cabezas en exactamente $m\ge N$ lanza (y no menos) es $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=N\\ 0 &\text{if } N<m\le N+M\\ \dfrac{1}{2^{M}}\sum_{r=M+1}^{N}\dfrac{1}{2^{r-M}}q(N,m-r)&\text{if } N+M<m \end{casos} $$ Por lo tanto la probabilidad condicional de espera $m$ pasos para obtener el $N$ consecutivos jefes dado el primer $M$ consecutivos cabezas es $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m\le N+M\\ \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M<m \end{casos} $$ El número esperado de sorteos pueden luego ser derivados por $$ \mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m) $$ o $\mathfrak{E}(M,N)-M$ para el número de adicionales pasos...