Esta es una reformulación de un problema práctico que encontré.
Digamos que tenemos una secuencia infinita de bits aleatorios, i.i.d. Para cada bit $X_i$ , $P(X_i=1)=p$ .
¿Cuál es el tiempo esperado hasta obtener una secuencia de $n$ ¿1 bit?
Gracias.
Hay mucha literatura sobre estas cuestiones relativas al tiempo medio de los patrones. Para su problema particular, se puede encontrar una solución en la página 156 de Introducción a los modelos de probabilidad (10ª edición) por Sheldon Ross. La fórmula es $$E[T]=1/p+1/p^2+\cdots+1/p^n={(p^{-n}-1)/(1-p)}.$$
Como era de esperar, se trata de una función decreciente de $p$ por el hecho de ser fijo $n$ : se necesita más tiempo para ver los eventos más raros. Como $p$ pasa de 0 a 1, $E[T]$ disminuye desde el infinito hasta $n$ .
Añadido: Aquí hay una derivación de la fórmula en mi respuesta.
Dejemos que $T$ sea la variable aleatoria que registra la primera vez que vemos $n$ en una fila. También vamos a definir la variable aleatoria $L$ para ser la posición del primer bit cero en la secuencia.
Mirando la primera $n$ hay, a grandes rasgos, dos posibilidades: o bien obtengo el patrón deseado de $n$ unos o tengo un cero a la vez $k$ y todo el problema vuelve a empezar.
Más formalmente, condicionando el valor de $L$ obtenemos \begin{eqnarray*} E[T] &=& \sum_{k=1}^{n} E[T \ |\ L=k]\ P(L=k) + E[T\ |\ L> n]\ P(L>n)\cr &=& \sum_{k=1}^{n} (k+E[T])\ P(L=k) + n P(L > n)\cr &=& \sum_{k=1}^{n} (k+E[T])\ p^{k-1}(1-p) + n p^n. \end{eqnarray*}
Resolviendo esta ecuación para $E[T]$ da la fórmula.
Hay muchas generalizaciones de este problema y variaciones de la prueba anterior que utilizan, por ejemplo, cadenas de Markov o martingalas, o funciones generadoras, etc. Además del libro de Ross mencionado anteriormente, tal vez le interese consultar
He aquí un enfoque de función generadora para este problema.
Preliminares
Para $0\le k<n$ , dejemos que un átomo $a_k$ sea una secuencia de $k$ $1$ bits seguidos de un $0$ poco. Que un átomo terminal $a_n$ sea una secuencia de $n$ $1$ bits. Deja que un completo $n$ sea una secuencia binaria que termina en la primera subsecuencia de $n$ consecutivos $1$ bits. Cualquier $n$ puede escribirse como una secuencia única de átomos seguida de un átomo terminal. La probabilidad de que aparezca un átomo es $p^k(1-p)$ y la longitud de un átomo es $k+1$ . La probabilidad de que aparezca un átomo terminal es $p^n$ y la longitud de un átomo terminal es $n$ .
Por lo tanto, para cada átomo $a_k$ definan el monomio $\phi_x(a_k)$ como $$ \phi_x(a_k)=\left\{\begin{array}{ll}p^k(1-p)x^{k+1}&\text{if }0\le k< n\\p^nx^n&\text{if }k=n\end{array}\right.\tag{1} $$ y para la concatenación de dos secuencias binarias, $s_1$ y $s_2$ $$ \phi_x(s_1s_2)=\phi_x(s_1)\phi_x(s_2)\tag{2} $$ La probabilidad de cualquier secuencia de átomos $s$ es el coeficiente del monomio $\phi_x(s)$ y la longitud de $s$ es el exponente de $x$ en $\phi_x(s)$ .
La función generadora
Por lo tanto, la probabilidad de un $n$ secuencia con longitud $k$ procedente de la concatenación de $j$ y un átomo terminal es el coeficiente de $x^k$ en $$ \begin{align} &(\phi_x(a_0)+\phi_x(a_1)+\phi_x(a_2)+\dots+\phi_x(a_{n-1}))^j\phi(a_n)\\ &=p^nx^n((1-p)x)^j\left(1+px+p^2x^2+\dots+p^{n-1}x^{n-1}\right)^j\\ &=p^nx^n\left((1-p)x\frac{1-p^nx^n}{1-px}\right)^j\tag{3} \end{align} $$ Sumando todo $j$ la probabilidad de que se complete $n$ secuencia con longitud $k$ es el coeficiente de $x^k$ en $$ \begin{align} f_n(x) &=\sum_{j=0}^\infty p^nx^n\left((1-p)x\frac{1-p^nx^n}{1-px}\right)^j\\ &=\frac{p^nx^n}{1-(1-p)x\frac{1-p^nx^n}{1-px}}\tag{4} \end{align} $$ Eso es, $f_n(x)$ es la función generadora de la probabilidad de un completo $n$ secuencia con una longitud determinada.
Desde $f_n(1)=1$ la probabilidad de que un $n$ secuencia se produce eventualmente es $1$ .
Duración prevista $$ f_n(x)=\sum_{k=0}^\infty c_kx^k\tag{5} $$ donde $c_k$ es la probabilidad de que se complete $n$ secuencia con longitud $k$ . Por lo tanto, $xf_n^\prime(x)$ evaluado en $x=1$ es $$ \sum_{k=0}^\infty kc_k\tag{6} $$ que es la longitud esperada de un $n$ secuencia.
$$ xf'(x)=p^nx^n\frac{n\frac{1-x}{1-px}+x\frac{1-p}{1-px}\frac{1-p^nx^n}{1-px}}{\left(1-(1-p)x\frac{1-p^nx^n}{1-px}\right)^2}\tag{7} $$ Evaluar $(7)$ en $x=1$ produce que la longitud esperada de un $n$ secuencia es $$ \mathrm{E}(k)=\frac{1-p^n}{p^n(1-p)}\tag{8} $$
Variación esperada
Utilizando la misma idea que se utilizó para conseguir $(6)$ , "tomamos la derivada y multiplicamos por $x$ " dos veces para ver que $xf_n^\prime(x)+x^2f_n^{\prime\prime}(x)$ evaluado en $x=1$ es $$ \sum_{k=0}^\infty k^2c_k\tag{9} $$ que es el cuadrado esperado de la longitud de un $n$ secuencia. $$ \begin{align} xf_n^\prime(x)+x^2f_n^{\prime\prime}(x) &=\frac{p^nx^n}{(1-px)^3\left(1-(1-p)x\left(\frac{1-p^nx^n}{1-px}\right)\right)^3}\\ &\times\left( \begin{aligned} &n^2(1-x)(1-px)\left(1-x-(1-p)xp^nx^n\right)\\ &+2n(1-p)x\left(1-x-(2-x-px)p^nx^n\right)\\ &+(1-p)x(1-p^nx^n)\left(1+x-(1-p)xp^nx^n\right)\\ \end{aligned} \right)\tag{10} \end{align} $$ Evaluar $(10)$ en $x=1$ se obtiene que el cuadrado esperado de la longitud de un $n$ secuencia es $$ \mathrm{E}(k^2)=\frac{2(1-p^n)}{p^{2n}(1-p)^2}-\frac{1+2n-p^n}{p^n(1-p)}\tag{11} $$ Combinando $(8)$ y $(11)$ obtenemos que la varianza esperada de la longitud de un $n$ secuencia es $$ \begin{align} \mathrm{Var}(k) &=\mathrm{E}(k^2)-\mathrm{E}(k)^2\\ &=\frac{1-p^{2n+1}}{p^{2n}(1-p)^2}-\frac{2n+1}{p^n(1-p)}\tag{12} \end{align} $$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
