¿Probabilidad de que una cadena binaria aleatoria contenga una serie larga de 1s?

Question

Para algunos fijos $n$ , dejemos que $p_n$ sea la probabilidad de que una cadena binaria infinita aleatoria contenga una serie de $1$ s, que contienen $n$ más $1$ s que el número total que aparece antes de la ejecución.

Por ejemplo, si $n=2$ la cadena binaria $010010111100...$ es del tipo que buscamos, pero la cadena $01001011100...$ no lo es (todavía). Llama a una ejecución de $1$ s que sea lo suficientemente largo, como los cuatro $1$ s en la primera cadena, un una carrera satisfactoria .

¿Existe alguna forma razonablemente agradable de calcular $p_n$ ?

Esto es lo que sé:

1. Podemos calcular el número esperado de ejecuciones satisfactorias en una cadena. Supongamos que un recorrido satisfactorio comienza después de $k$ bits preliminares. Si $k=0$ esto ocurre con probabilidad $2^{-n}$ ; en caso contrario, se produce con probabilidad $\sum_{i=0}^{k-1} {k-1 \choose i} 2^{-n-k-i}=2^{-n-k}\left(\frac{3}{2}\right)^k$ . La suma de todos los $k$ obtenemos que el número esperado de ejecuciones satisfactorias es $3(2^{-n})$ y así $p_n<3(2^{-n})$ . Se puede ampliar este argumento para calcular $p_n$ por inclusión-exclusión, pero me parece que sería increíblemente feo. De hecho, $3(2^{-n})$ es una estimación bastante buena para $p_n$ ya que la probabilidad de que una cadena dada tenga múltiples ejecuciones satisfactorias es muy baja.

2. Al condicionar la ubicación del primer $0$ en la cadena, podemos obtener una relación de recurrencia: $p_n=2^{-n+1}+\sum_{i=1}^{n-1} 2^{-i+1}p_{n+i}$ . Esto no es suficiente para calcular $p_n$ por sí solo, incluso dados algunos valores iniciales -- el mayor índice que aparece en él es $p_{2n-1}$ por lo que si tratas de usarlo recursivamente nunca aprenderás nada sobre $p_n$ para $n$ incluso. Podrías sacar algo de esto sustituyéndolo repetidamente en sí mismo (en la forma que lo he dado, con el coeficiente más pequeño señalado), y usando el límite de 1. para hacer algún tipo de argumento de límite, pero esto también me parece desagradable.

¿Qué opinas?

(Esto viene originalmente de este Magic: the Gathering escenario, pero espero haber logrado de- Magia ).

Answer 1

Ligero cambio trivial en la notación: Dejemos que $P_n$ sea la probabilidad de que cada serie de 1s consecutivos en nuestra cadena no supere $n$ más las carreras anteriores acumuladas.

Entonces, se cumple la siguiente recursión lineal (equivalente a la de su segunda aproximación):

$$P_n = \sum_{k=1}^n P_{n+k} \; 2^{-k} \hspace{12mm} n=1, 2 \ldots \tag{1} $$

(se obtiene sumando sobre todas las longitudes posibles de la primera carrera; porque, después de la primera carrera de longitud $k$ tenemos el problema del equívoco con $n$ sustituido por $k+n$ )

Esta recursión es bastante complicada de resolver, porque nuestro "valor inicial" sería $P_{\infty}=1$ y la recursión no es reversible en el tiempo. Este es mi enfoque (quizás haya procedimientos más elegantes, no estoy muy familiarizado con esto).

Intento una solución de la forma

$$P_n = 1 + a_1 2^{-n} + a_2 2^{-2n} + a_3 2^{-3n} + \cdots$$

En realidad, sólo mantendremos los términos con exponentes de la forma $-(2^p-1)n$ . Es decir, establecemos $a_i=0$ a menos que $i = 2^p-1$ para algún número entero $p$ . Llamando a $Q(r, n) = 2^{-r \, n}$ tenemos:

$$P_n = Q(0,n) + a_1 \, Q(1 , n) + a_3 \, Q(3,n) + a_7 \, Q(7,n) + a_{15} \, Q(15,n) +\cdots$$

Ahora, es sencillo comprobar (suma geométrica) que:

$$\sum_{k=1}^n Q(r,n+k) \; 2^{-k} = \frac{1}{2^{r+1}-1} \bigl( Q(r,n) - Q(2r+1,n) \bigr) $$

Por lo tanto, la recursión (1) induce las transformaciones $Q_0 \to Q_0 -Q_1$ , $Q_1 \to \frac{1}{3}(Q_1 -Q_3)$ , $Q_3 \to \frac{1}{7}(Q_3 -Q_7)$ etc., y así se pueden obtener los coeficientes:

$$\begin{align} a_1 &= \frac{a_1}{3} - 1 \Rightarrow a_1 = -\frac{3}{2} \\ a_3 &= \frac{a_3}{7} - \frac{a_1}{3} \Rightarrow a_3 = \frac{1}{3} \frac{7}{6} \frac{3}{2}=\frac{7}{6 \times 2}\\ a_7 &= \frac{a_7}{15} - \frac{a_3}{7} \Rightarrow a_7 = - \frac{1}{7} \frac{15}{14} \frac{1}{3} \frac{7}{6} \frac{3}{2} =-\frac{15}{14 \times 6 \times 2} \\ a_{15} &= \cdots = \frac{31}{30 \times 14 \times 6 \times 2}\\ a_{2^p-1} &= \cdots = (-1)^p \frac{2^{p-1}-1}{(2^{p-1}-2) \times (2^{p-2}-2) \cdots \times 14 \times 6 \times 2}\\ \end{align} $$

O, más compacto (quizás no más esclarecedor) :

$$ a_{2^p-1} = \frac{2-2^{-p}}{(2;2)_p}$$

donde $(a;q)_n$ es el q-Símbolo del martillo .

Algunos valores numéricos:

$ a_1=-1.50$ , $ a_3\approx0.58333$ , $a_7\approx-0.08929 $ , $a_{15}\approx 0.00615$ , $a_{31}\approx-0.0002$

Así que, finalmente

$$ P_n = 1 - \frac{3}{2} 2^{-n} + \frac{7}{12} 2^{-3 n } + \cdots =\\ = 1 +\sum_{p=1}^\infty \frac{2-2^{-p}}{(2;2)_p}2^{-(2^p-1)n}$$

Esto converge bastante rápido, especialmente para grandes $n$ .

Para obtener, según la pregunta original, la probabilidad de que alguna carrera sea mayor o igual que $m$ , evaluaríamos

$$1 - P_{m-1} = 3 \, 2^{-m} - \frac{14}{3} 2^{-3 m} + \cdots $$

que en la primera aproximación coincide con la estimación de la OP (usando la expectativa); es una aproximación bastante buena para, digamos, $n>4$ .

        n        1         2         3         4         5        6          7     
 p(n) exact   0.32222   0.63411   0.81364   0.90639   0.95314   0.97656   0.98828  
 p(n) approx  0.25000   0.62500   0.81250   0.90625   0.95312   0.97656   0.98828  

---

Añadido Límites rigurosos para $P(n)$ se puede obtener observando que, con mi definición, es equivalente a la probabilidad de que una secuencia de variables geométricas iid $x_i = 1, 2 \cdots$ alcanzando valores en $x_1 \le n$ , $x_2 \le n + x_1 $ , $x_3 \le n + x_1 + x_2$ ...

Así que

$$P(n) = \sum_{k_1}^{n} 2^{-k_1} \sum_{k_2}^{n+k_1} 2^{-k_2} \sum_{k_3}^{n+k_1+k_2} 2^{-k_3} \cdots$$

En particular, un límite inferior para el $m$ -en este producto anidado infinito se obtiene fijando los valores exteriores en $k_1=1$ , $k_2=1$ ..., así que

$$P(n) \le \sum_{k_1}^{n} 2^{-k_1} \sum_{k_2}^{n+1} 2^{-k_2} \sum_{k_3}^{n+2} 2^{-k_3} \cdots = (1 - 2^{-n})(1 - 2^{-n-1})(1 - 2^{-n-2}) = \\ = \prod_{i=0}^\infty (1 - 2^{-n} 2^{-i})= S(2^{-n},2^{-1}) $$ donde $S(a,q)=\prod_{i=0}^\infty (1 - a q^{i})$ es el símbolo q-Pochamer o (serie q) QPochhammer[a,q]

Podemos comprobar que esto tiende a 1 cuando $a\to 0$ por utilizando el límite $0<-\log(1-x)<2x$ para $0<x \le 1/2$ Así que $\log( S(2^{-n},2^{-1})$ está acotado entre $0$ y $-2^{-n+1}$ . Por lo tanto, $\lim_{n\to\infty} P(n)=1$ .

Añadido 2: Respecto a la unicidad: Debemos demostrar que la recursión (1), con la condición de contorno $P_{\infty}=1$ no admite más de una solución (con $0 \le P_n \le 1)$ . Esto equivale a demostrar que la recursión no tiene solución con $P_{\infty}=0$ excepto el trivial: $P_n=0$ . 

Ahora, supongamos que $P_{n_1}>0$ . Entonces, la ecuación (1) implica que existe al menos una $n_2$ en $n_1 +1 \cdots 2 n_1$ con $P_{n_2} > P_{n_1}$ . Aplicando lo mismo a $n_2$ esto implica que podemos encontrar una subsecuencia creciente de $P(n)$ por lo que su límite no puede ser cero.

Answer 2

Esta respuesta tiene una etapa de "motivación" y después una etapa de "cálculos". Aunque la deducción de las fórmulas no es tan agradable como las fórmulas proporcionadas por el OP y leonbloy, creo que mi respuesta se califica de "agradable", al menos porque obtengo una recurrencia decreciente y por su sabor "constructivo". Por favor, prepárate para ver un montón de símbolos de suma, pero no te impacientes, simplemente no olvides la moraleja del razonamiento, y siéntete libre de saltarte los pasos fáciles.

FASE 1: MOTIVACIÓN

Siempre intento resolver los problemas relativos a las cadenas binarias aleatorias de forma constructiva. Entonces podemos preguntarnos: ¿cómo "construir" una cadena "admisible"?

Así es como procedo: digamos que usted quiere que la condición deseada se cumpla en el $r$ -a la carrera de $1$ s (en breve, $1$ - Ejecutar ) y no antes. Entonces se construye el anterior $1$ -Corridas con longitudes prescritas $k_1,k_2,\dots,k_{r-1}\geq1$ . Ahora debemos intercalar $0$ -corre entre nuestros $1$ - y se ejecuta. La primera $0$ -run, que nos pondrán antes de la primera $1$ -run, puede tener cualquier longitud $i_1$ incluyendo el cero (porque su secuencia puede o no comenzar con $1$ ). Por otro lado, la otra división $0$ -las carreras deben tener una longitud positiva (porque deben separar nuestro $1$ -runs).

Por lo tanto, las longitudes $i_1,\dots,i_r$ de la $0$ -se satisfacen las carreras $i_1\geq0$ y $i_2,\dots,i_r\geq1$ . Por último, el $r$ -en $1$ -la ejecución debe tener una longitud mayor o igual que $n+k_1+\cdots+k_{r-1}$ . En realidad, podemos suponer que esta longitud es exactamente igual a $n+k_1+\cdots+k_{r-1}$ porque en este caso no importa cómo sea el resto de la secuencia.

Por supuesto, la condición deseada no se cumple antes del $r$ -si y sólo si $k_j\leq s_{j-1}$ para $j=1,\dots,r-1$ , siendo $s_j=n-1+k_1+\cdots+k_j$ ( $s_0=n-1$ ).

El conjunto de secuencias construidas de la manera descrita anteriormente, con los valores $k_i$ y $i_j\ $ fijo tiene probabilidad

$$\underbrace{2^{-(i_1+\cdots+i_r)}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(n+k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,.$$

Queda por sumar este valor sobre todos los valores admisibles de $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$ . En otras palabras, la probabilidad deseada es igual a

$$\sum_{r=1}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}2^{-(i_1+\cdots+i_r)}\,2^{- (k_1+\cdots+k_{r-1})}\,2^{-(n+k_1+\cdots+k_{r-1})}\,.$$

La parte de la suma que implica el $i_j$ puede resolverse fácilmente: recordemos que $\sum_{i=0}^\infty 2^{-i}=2$ y $ \sum_{i=1}^\infty2^{-i}=1$ por lo que nuestra suma se simplifica a

$$2^{1-n}\sum_{r=1}^\infty\ \sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}\,.$$

Ahora nos concentramos en la suma interna, es decir, con $r$ arreglado. Tenemos

$$\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}=\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}\sum_{k_{r-1}=1}^{s_{r-2}}4^{-k_{r-1}}\,.$$

Desde $\sum_{k=1}^s4^{-k}=\frac13(1-4^{-s})$ nuestra suma se convierte en

$$\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}(1-4^{-s_{r-2}})$$

$$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}4^{-s_{r-2}}$$

$$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\,4^{-(n-1)}\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-2(k_1+\cdots+k_{r-2})}$$

Ahora voy a tratar de convencerte de que esto es realmente un disminuyendo recurrencia, a diferencia del planteamiento de OP y leonbloy (que por supuesto son muy inteligentes y esclarecedores). Este es un buen momento para hacer una generalización del problema e introducir alguna notación conveniente:

ETAPA 2: CÁLCULOS

Dejemos que $p\in(0,1)$ y que $q=1-p$ . Ahora suponemos que la probabilidad de $1$ en cada lugar de una cadena binaria es igual a $p$ (por lo que la probabilidad de $0$ es $q$ ). En el caso de interés tenemos $p=q=1/2$ pero el caso general no es más difícil que este caso particular.

Razonando como en la etapa anterior, la probabilidad del conjunto de secuencias deseadas con los números $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$ fijo es igual a

$$\underbrace{q^{i_1+\cdots+i_r}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{n+k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,,$$

Es importante distinguir el caso $r=1$ de la probabilidad anterior: en este caso no hay elección de números $k_1,\dots,k_{r-1}$ sólo elegimos $i_1\geq0$ por lo que en este caso la probabilidad es igual a $p^nq^{i_1}$ . Por lo tanto, la probabilidad total es igual a

$$\sum_{i_1=0}^\infty p^nq^{i_1}+\sum_{r=2}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}q^{i_1+\cdots+i_r}\,p^{k_1+\cdots+k_{r-1}}\,p^{n+k_1+\cdots+k_{r-1}}\,.$$

$$=\frac{p^n}{1-q}+\frac{p^n}{1-q}\sum_{r=2}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\bigl(p^2\bigr)^{k_1+\cdots+k_{r-1}}\,.$$

Definir

$$S(\alpha,1)=1;\ S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_1+\cdots+k_{r-1}}\,,\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$$

Entonces nuestra probabilidad se puede escribir como

$$\frac{p^n}{1-q}\sum_{r=1}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}S(p^2,r)\,.$$

Tenemos $S(\alpha,1)=1$ y para $r\geq2$ :

$$S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_{r-1}}$$

$$=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\biggl[\frac{\alpha}{1-\alpha}\,(1-\alpha^{s_{r-2}})\biggr]$$

$$=\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}-\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}+s_{r-2}}$$

$$=\frac{\alpha}{1-\alpha}S(\alpha,r-1)-\frac{\alpha}{1-\alpha}\,\alpha^{n-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{2(k_1+\cdots+k_{r-2})}$$

$$=\frac{\alpha}{1-\alpha}\,S(\alpha,r-1)-\frac{\alpha^n}{1-\alpha}\,S(\alpha^2,r-1)\,.$$

Cambiar $\alpha$ por $\alpha^j$ obtenemos, para $r\geq2$ :

$$S(\alpha^j,r)=\frac{\alpha^j}{1-\alpha^j}\,S(\alpha^j,r-1)-\frac{\alpha^{jn}}{1-\alpha^j}\,S(\alpha^{2j},r-1)\,.$$

¿Por qué diablos hice esto? porque definiendo

$$b_j=\frac{\alpha^j}{1-\alpha^j},\ c_j=-\,\frac{\alpha^{jn}}{1-\alpha^j}\quad \style{font-family:inherit;}{\text{and}}\quad T(j,r)=S(\alpha^j,r)$$

la recurrencia se convierte en

$$T(j,1)=1;\quad T(j,r)=b_j\,T(j,r-1)+c_j\,T(2j,r-1),\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$$

OK, estoy de acuerdo en que esto no es un genuino recurrencia decreciente, como índice $j$ está aumentando; afortunadamente, el índice $r$ disminuye. En general, estas recurrencias pueden resolverse explícitamente, ya sea con las manos desnudas o utilizando sistemas de álgebra computacional. Más adelante trataré de resolverlas paso a paso, en beneficio de quienes me creyeron (¿o descreyeron?) y aguantaron hasta este punto.