Si he entendido bien, entonces el problema es encontrar una distribución de probabilidad para el momento en que la primera ejecución de $n$ o más cabezas termina.
Editar Las probabilidades pueden determinarse con precisión y rapidez utilizando la multiplicación de matrices, y también es posible calcular analíticamente la media como $\mu_-=2^{n+1}-1$ y la varianza como $\sigma^2=2^{n+2}\left(\mu-n-3\right) -\mu^2 + 5\mu$ donde $\mu=\mu_-+1$ pero probablemente no exista una forma cerrada sencilla para la propia distribución. A partir de un cierto número de lanzamientos, la distribución es esencialmente una distribución geométrica: tendría sentido utilizar esta forma para las monedas más grandes. $t$ .
La evolución en el tiempo de la distribución de probabilidad en el espacio de estados puede modelarse mediante una matriz de transición para $k=n+2$ estados, donde $n=$ el número de lanzamientos consecutivos de la moneda. Los estados son los siguientes:
- Estado $H_0$ , no hay cabezas
- Estado $H_i$ , $i$ cabezas, $1\le i\le(n-1)$
- Estado $H_n$ , $n$ o más cabezas
- Estado $H_*$ , $n$ o más cabezas seguidas de una cola
Una vez que se entra en el estado $H_*$ no puedes volver a ninguno de los otros estados.
Las probabilidades de transición a los estados son las siguientes
- Estado $H_0$ : probabilidad $\frac12$ de $H_i$ , $i=0,\ldots,n-1$ es decir, que se incluye a sí mismo pero no al Estado $H_n$
- Estado $H_i$ : probabilidad $\frac12$ de $H_{i-1}$
- Estado $H_n$ : probabilidad $\frac12$ de $H_{n-1},H_n$ es decir, del estado con $n-1$ cabezas y a sí mismo
- Estado $H_*$ : probabilidad $\frac12$ de $H_n$ y la probabilidad 1 de $H_*$ (sí)
Así, por ejemplo, para $n=4$ Esto da como resultado la matriz de transición
$$ X = \left\{ \begin{array}{c|cccccc} & H_0 & H_1 & H_2 & H_3 & H_4 & H_* \\ \hline H_0 & \frac12 & \frac12& \frac12& \frac12 &0 & 0 \\ H_1 & \frac12 &0 & 0 &0 & 0 & 0 \\ H_2 & 0 & \frac12 &0 &0 & 0 & 0 \\ H_3 & 0 & 0 &\frac12 &0 & 0 & 0 \\ H_4 & 0 & 0 &0 &\frac12 & \frac12 & 0 \\ H_* & 0 & 0 & 0&0 &\frac12 & 1 \end{array}\right\} $$
Para el caso $n=4$ el vector inicial de probabilidades $\mathbf{p}$ es $\mathbf{p}=(1,0,0,0,0,0)$ . En general, el vector inicial tiene $$\mathbf{p}_i=\begin{cases}1&i=0\\0&i>0\end{cases}$$
El vector $\mathbf{p}$ es la distribución de probabilidad en espacio para cualquier momento. La fdc requerida es una fdc en tiempo y es la probabilidad de haber visto al menos $n$ el lanzamiento de la moneda termina con el tiempo $t$ . Se puede escribir como $(X^{t+1}\mathbf{p})_k$ , observando que llegamos al estado $H_*$ 1 paso de tiempo después del último en la serie de lanzamientos consecutivos de monedas.
La pmf requerida en el tiempo puede escribirse como $(X^{t+1}\mathbf{p})_k - (X^{t}\mathbf{p})_k$ . Sin embargo, numéricamente, esto implica restar un número muy pequeño de un número mucho mayor ( $\approx 1$ ) y restringe la precisión. Por lo tanto, en los cálculos es mejor establecer $X_{k,k}=0$ en lugar de 1. Entonces escribiendo $X'$ para la matriz resultante $X'=X|X_{k,k}=0$ el pmf es $(X'^{t+1}\mathbf{p})_k$ . Esto es lo que se implementa en el sencillo programa R de abajo, que funciona para cualquier $n\ge 2$ ,
n=4
k=n+2
X=matrix(c(rep(1,n),0,0, # first row
rep(c(1,rep(0,k)),n-2), # to half-way thru penultimate row
1,rep(0,k),1,1,rep(0,k-1),1,0), # replace 0 by 2 for cdf
byrow=T,nrow=k)/2
X
t=10000
pt=rep(0,t) # probability at time t
pv=c(1,rep(0,k-1)) # probability vector
for(i in 1:(t+1)) {
#pvk=pv[k]; # if calculating via cdf
pv = X %*% pv;
#pt[i-1]=pv[k]-pvk # if calculating via cdf
pt[i-1]=pv[k] # if calculating pmf
}
m=sum((1:t)*pt)
v=sum((1:t)^2*pt)-m^2
c(m, v)
par(mfrow=c(3,1))
plot(pt[1:100],type="l")
plot(pt[10:110],type="l")
plot(pt[1010:1110],type="l")
El gráfico superior muestra el pmf entre 0 y 100. Los dos gráficos inferiores muestran la pmf entre 10 y 110 y también entre 1010 y 1110, lo que ilustra la autosimilitud y el hecho de que, como dice @Glen_b, la distribución parece poder aproximarse a una distribución geométrica tras un periodo de asentamiento.
![enter image description here]()
Es posible investigar más a fondo este comportamiento utilizando una descomposición de vectores propios de $X$ . Al hacerlo, se demuestra que el para un tamaño suficientemente grande $t$ , $p_{t+1}\approx c(n)p_t$ , donde $c(n)$ es la solución de la ecuación $2^{n+1}c^n(c-1)+1=0$ . Esta aproximación mejora con el aumento de $n$ y es excelente para $t$ en el rango de unos 30 a 50, dependiendo del valor de $n$ como se muestra en el gráfico del error logarítmico que se muestra a continuación para calcular $p_{100}$ (colores del arco iris, rojo a la izquierda para $n=2$ ). (De hecho, por razones numéricas, sería mejor utilizar la aproximación geométrica para las probabilidades cuando $t$ es mayor).
![enter image description here]()
Sospecho(n) que puede haber una forma cerrada disponible para la distribución porque las medias y las varianzas las he calculado de la siguiente manera
$$ \begin{array}{r|rr} n & \text{Mean} & \text{Variance} \\ \hline 2 &7& 24& \\ 3 &15& 144& \\ 4 &31& 736& \\ 5 &63& 3392& \\ 6 &127& 14720& \\ 7 &255& 61696& \\ 8 &511& 253440& \\ 9 &1023& 1029120& \\ 10&2047& 4151296& \\ \end{array} $$
(Tuve que aumentar el número del horizonte temporal a t=100000 para conseguir esto pero el programa seguía funcionando para todos $n=2,\ldots,10$ en menos de unos 10 segundos). Las medias, en particular, siguen un patrón muy obvio; las varianzas, no tanto. He resuelto un sistema de transición de 3 estados más sencillo en el pasado, pero hasta ahora no he tenido suerte con una solución analítica sencilla para éste. Quizá haya alguna teoría útil que desconozco, por ejemplo, relacionada con las matrices de transición.
Editar : después de un montón de falsos comienzos, he dado con una fórmula de recurrencia. Sea $p_{i,t}$ sea la probabilidad de estar en el estado $H_i$ en el momento $t$ . Sea $q_{*,t}$ sea la probabilidad acumulada de estar en el estado $H_*$ es decir, el estado final, en el momento $t$ . NB
- Para cualquier $t$ , $p_{i,t}, 0\le i\le n$ y $q_{*,t}$ son una distribución de probabilidad sobre el espacio $i$ e inmediatamente después utilizo el hecho de que sus probabilidades suman 1.
- $p_{*,t}$ forman una distribución de probabilidad en el tiempo $t$ . Más adelante, utilizaré este hecho para derivar las medias y las varianzas.
La probabilidad de estar en el primer estado en el momento $t+1$ es decir, sin cabezas, viene dada por las probabilidades de transición de los estados que pueden volver a él desde el tiempo $t$ (utilizando el teorema de la probabilidad total). \begin{align} p_{0,t+1} &= \frac12p_{0,t} + \frac12p_{1,t} + \ldots \frac12p_{n-1,t}\\ &= \frac12\sum_{i=0}^{n-1}p_{i,t}\\ &= \frac12\left( 1-p_{n,t}-q_{*,t} \right) \end{align} Pero para llegar desde el estado $H_0$ a $H_{n-1}$ toma $n-1$ pasos, por lo tanto $p_{n-1,t+n-1} = \frac1{2^{n-1}}p_{0,t}$ y $$ p_{n-1,t+n} = \frac1{2^n}\left( 1-p_{n,t}-q_{*,t} \right)$$ Una vez más, por el teorema de la probabilidad total, la probabilidad de estar en el estado $H_n$ en el momento $t+1$ es \begin{align} p_{n,t+1} &= \frac12p_{n,t} + \frac12p_{n-1,t}\\ &= \frac12p_{n,t} + \frac1{2^{n+1}}\left( 1-p_{n,t-n}-q_{*,t-n} \right)\;\;\;(\dagger)\\ \end{align} y utilizando el hecho de que $q_{*,t+1}-q_{*,t}=\frac12p_{n,t} \implies p_{n,t} = 2q_{*,t+1}-2q_{*,t}$ , \begin{align} 2q_{*,t+2} - 2q_{*,t+1} &= q_{*,t+1}-q_{*,t}+\frac1{2^{n+1}}\left( 1-2q_{*,t-n+1}+q_{*,t-n} \right) \end{align} Por lo tanto, cambiar $t\to t+n$ , $$2q_{*,t+n+2} - 3q_{*,t+n+1} +q_{*,t+n} + \frac1{2^n}q_{*,t+1} - \frac1{2^{n+1}}q_{*,t} - \frac1{2^{n+1}} = 0$$
Esta fórmula de recurrencia se verifica para los casos $n=4$ y $n=6$ . Por ejemplo, para $n=6$ un gráfico de esta fórmula utilizando t=1:994;v=2*q[t+8]-3*q[t+7]+q[t+6]+q[t+1]/2**6-q[t]/2**7-1/2**7 da la precisión de la orden de la máquina.
![enter image description here]()
Editar No veo dónde encontrar una forma cerrada de esta relación de recurrencia. Sin embargo es posible obtener una forma cerrada para la media.
A partir de $(\dagger)$ y observando que $p_{*,t+1}=\frac12p_{n,t}$ , \begin{align} p_{n,t+1} &= \frac12p_{n,t} + \frac1{2^{n+1}}\left( 1-p_{n,t-n}-q_{*,t-n} \right)\;\;\;(\dagger)\\ 2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right)+2p_{*,t+1} &= 1-q_{*,t} \end{align} Tomando sumas de $t=0$ a $\infty$ y aplicando la fórmula de la media $E[X] = \sum_{x=0}^\infty (1-F(x))$ y señalando que $p_{*,t}$ es una distribución de probabilidad da \begin{align} 2^{n+1}\sum_{t=0}^\infty \left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2\sum_{t=0}^\infty p_{*,t+1} &= \sum_{t=0}^\infty(1-q_{*,t}) \\ 2^{n+1} \left(2\left(1-\frac1{2^{n+1}}\right)-\;1\;\right) + 2 &= \mu \\ 2^{n+1} &= \mu \end{align} Este es el medio para alcanzar el estado $H_*$ la media para el final de la racha de cabezas es una menos que esta.
Editar Un enfoque similar utilizando la fórmula $E[X^2] = \sum_{x=0}^\infty (2x+1)(1-F(x))\;$ de esta pregunta produce la varianza. \begin{align} \sum_{t=0}^\infty(2t+1)\left (2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2 p_{*,t+1}\right) &= \sum_{t=0}^\infty(2t+1)(1-q_{*,t}) \\ 2\sum_{t=0}^\infty t\left (2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2 p_{*,t+1}\right) + \mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(2\left(\mu-(n+2)+\frac1{2^{n+1}}\right)-(\mu-(n+1))\right) + 4(\mu-1) &\\+ \mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(2(\mu-(n+2))-(\mu-(n+1))\right) + 5\mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(\mu-n-3\right) + 5\mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(\mu-n-3\right) -\mu^2 + 5\mu &= \sigma^2 \end{align}
Las medias y varianzas pueden generarse fácilmente de forma programada. Por ejemplo, para comprobar las medias y varianzas de la tabla anterior, utilice
n=2:10
m=c(0,2**(n+1))
v=2**(n+2)*(m[n]-n-3) + 5*m[n] - m[n]^2
Por último, no estoy seguro de lo que querías cuando escribiste
cuando una cola golpea y rompe la racha de cabezas la cuenta comenzaría de nuevo desde el siguiente lanzamiento.
Si te refieres a cuál es la distribución de probabilidad para el siguiente hora a la que se realiza la primera tirada de $n$ o más cabezas termina, entonces el punto crucial está contenido en este comentario de @Glen_b que es que el proceso comienza de nuevo después de una cola (c.f. el problema inicial en el que se podía conseguir una tirada de $n$ o más cabezas inmediatamente).
Esto significa que, por ejemplo, el tiempo medio hasta el primer evento es $\mu-1$ pero el tiempo medio entre eventos es siempre $\mu+1$ (la varianza es la misma). También es posible utilizar una matriz de transición para investigar las probabilidades a largo plazo de estar en un estado después de que el sistema se haya "asentado". Para obtener la matriz de transición adecuada, hay que poner $X_{k,k,}=0$ y $X_{1,k}=1$ para que el sistema vuelva inmediatamente al estado $H_0$ del estado $H_*$ . Entonces el El primer vector propio escalado de esta nueva matriz da las probabilidades estacionarias . Con $n=4$ estas probabilidades estacionarias son
$$ \begin{array}{c|cccccc} & \text{probability} \\ \hline H_0 & 0.48484848 \\ H_1 & 0.24242424 \\ H_2 & 0.12121212 \\ H_3 & 0.06060606 \\ H_4 & 0.06060606 \\ H_* & 0.03030303 \end{array} $$ El tiempo esperado entre estados viene dado por el recíproco de la probabilidad. Por lo tanto, el tiempo esperado entre las visitas a $H_* = 1/0.03030303 = 33 = \mu + 1$ .
Anexo : Programa de Python utilizado para generar probabilidades exactas para n = número de cabezas consecutivas sobre N lanzamientos.
import itertools, pylab
def countinlist(n, N):
count = [0] * N
sub = 'h'*n+'t'
for string in itertools.imap(''.join, itertools.product('ht', repeat=N+1)):
f = string.find(sub)
if (f>=0):
f = f + n -1 # don't count t, and index in count from zero
count[f] = count[f] +1
# uncomment the following line to print all matches
# print "found at", f+1, "in", string
return count, 1/float((2**(N+1)))
n = 4
N = 24
counts, probperevent = countinlist(n,N)
probs = [count*probperevent for count in counts]
for i in range(N):
print '{0:2d} {1:.10f}'.format(i+1,probs[i])
pylab.title('Probabilities of getting {0} consecutive heads in {1} tosses'.format(n, N))
pylab.xlabel('toss')
pylab.ylabel('probability')
pylab.plot(range(1,(N+1)), probs, 'o')
pylab.show()
