Probabilidad para la longitud de la racha más larga en $n$ pruebas de Bernoulli

Question

Supongamos que se lanzó una moneda sesgada (probabilidad de que salga cara $p$) $n$ veces. Me gustaría encontrar la probabilidad de que la longitud de la racha más larga de caras, digamos $\ell_n$, exceda un número dado $m$, es decir, $\mathbb{P}(\ell_n > m).

Basta con encontrar la probabilidad de que la longitud de cualquier racha de caras exceda $m$. Estaba tratando de abordar el problema fijando una racha de $m+1$ caras, y contando el número de configuraciones de este tipo, pero no llegué a ninguna conclusión.

Es fácil simularlo:

Agradecería cualquier consejo sobre cómo resolver este problema analíticamente, es decir, expresar una respuesta en términos de una suma o una integral.

Gracias.

Answer 1

Este problema fue resuelto utilizando funciones generadoras por de Moivre en 1738. La fórmula que deseas es $$\mathbb{P}(\ell_n \geq m)=\sum_{j=1}^{\lfloor n/m\rfloor} (-1)^{j+1}\left(p+\left({n-jm+1\over j}\right)(1-p)\right){n-jm\choose j-1}p^{jm}(1-p)^{j-1}.$$

Referencias

1. Sección 14.1 Problemas e instantáneas del mundo de la probabilidad por Blom, Holst y Sandell

2. Capítulo V, Sección 3 Introducción a la probabilidad matemática por Uspensky

3. Sección 22.6 Una historia de probabilidad y estadística y sus aplicaciones antes de 1750 por Hald da soluciones de de Moivre (1738), Simpson (1740), Laplace (1812), y Todhunter (1865)

---

Añadido: La clase combinatoria de todas las secuencias de lanzamientos de moneda sin una racha de $ m $ caras seguidas es $$\sum_{k\geq 0}(\mbox{seq}_{< m }(H)\,T)^k \,\mbox{seq}_{< m }(H), $$ con la correspondiente función generadora de conteo $$H(h,t)={\sum_{0\leq j< m }h^j\over 1-(\sum_{0\leq j< m }h^j)t}={1-h^ m \over 1-h-(1-h^ m )t}.$$ Introducimos la probabilidad reemplazando $h$ con $ps$ y $t$ con $qs$, donde $q=1-p$: $$G(s)={1-p^ m s^ m \over1-s+p^ m s^{ m +1}q}.$$ El coeficiente de $s^n$ en $G(s)$ es $\mathbb{P}(\ell_n

La función $1/(1-s(1-p^ m s^ m q ))$ puede ser reescrita como \begin{eqnarray*} \sum_{k\geq 0}s^k(1-p^ m s^ m q )^k &=&\sum_{k\geq 0}\sum_{j\geq 0} {k\choose j} (-p^ m q)^js^{k+j m }\\ \end{eqnarray*}

El coeficiente de $s^n$ en esta función es $c(n)=\sum_{j\geq 0}{n-j m \choose j}(-p^ m q)^j$. Por lo tanto, el coeficiente de $s^n$ en $G(s)$ es $c(n)-p^ m c(n- m )." Por último, \begin{eqnarray*} \mathbb{P}(\ell_n\geq m)&=&1-\mathbb{P}(\ell_n

Answer 2

Define una cadena de Markov con estados $0, 1, \ldots m$ de modo que con probabilidad $1$ la cadena se mueva de $m$ a $m$ y para $i

Answer 3

Puedes encontrar una distribución límite, de lo contrario es un problema difícil y la solución en forma cerrada no tendrá mucho valor práctico. Consulta esto para un enfoque elemental. [Actualización] El enlace anterior se ha movido a esta nueva dirección. "Longest Run of Heads", M.F.Schilling.

Answer 4

Nota. La siguiente respuesta utiliza la misma metodología que la respuesta líder aceptada. Es autocontenida, incluye código de Maple y algunos elementos asintóticos. Quizás pueda servir como un propósito didáctico y mostrar que la computación básica es muy simple.

Con $z$ para éxitos y $w$ para fracasos obtenemos la función generadora

$$\left(1+z+\cdots+u\frac{z^m}{1-z}\right) \left(\sum_{q\ge 0} \frac{w^q}{(1-w)^q} \left(z+\cdots+u\frac{z^m}{1-z}\right)^q \right)\frac{1}{1-w}.$$

Ahora, como prueba de cordura, cuando ponemos $w=z$ y $u=1$ deberíamos obtener todas las cadenas binarias. Haciendo el cálculo encontramos

$$\frac{1}{1-z} \frac{1}{1-wz/(1-w)/(1-z)} \frac{1}{1-w} \\ = \frac{1}{(1-w)(1-z)-wz} = \frac{1}{1-w-z}.$$

Poniendo $z=w$ obtenemos

$$\frac{1}{(1-z)^2} \frac{1}{1-z^2/(1-z)^2} = \frac{1}{(1-z)^2-z^2} = \frac{1}{1-2z}$$

y la prueba de cordura se cumple.

Para las probabilidades, debemos restar el valor para $u=0$ de la función generadora y luego establecer $u=1$. Obtenemos para el término cero

$$\frac{1-z^m}{1-z} \left(\sum_{q\ge 0} \frac{w^q}{(1-w)^q} z^q \frac{(1-z^{m-1})^q}{(1-z)^q}\right) \frac{1}{1-w} \\ = \frac{1-z^m}{1-z} \frac{1}{1-wz(1-z^{m-1})/(1-w)/(1-z)} \frac{1}{1-w} = \frac{1-z^m}{(1-w)(1-z)-wz(1-z^{m-1})} = \frac{1-z^m}{1-w-z+wz^{m}}.$$

Para obtener las probabilidades, establecemos $z=pv$ y $w=(1-p)v$ para obtener el término uno

$$\frac{1}{1-w-z} = \frac{1}{1-(1-p)v-pv} = \frac{1}{1-v}$$

entonces $$[v^n] \frac{1}{1-v} = 1.$$

La contribución restada del término cero es

$$\frac{1- p^m v^m}{1-v+(1-p)p^m v^{m+1}}.$$

Ahora, para la extracción de coeficientes, escribimos

$$[v^Q] \frac{1}{1-v+(1-p)p^m v^{m+1}} \\ = [v^Q] \sum_{q\ge 0} (v-(1-p)p^m v^{m+1})^q \\ = [v^Q] \sum_{q\ge 0} \sum_{r=0}^q {q\choose r} v^{q-r} (-1)^r (1-p)^r p^{mr} v^{(m+1)r}. \\ = [v^Q] \sum_{q\ge 0} \sum_{r=0}^q {q\choose r} v^{mr+q} (-1)^r (1-p)^r p^{mr} \\ = \sum_{r=0}^{\lfloor Q/m\rfloor} {Q-mr\choose r} (-1)^r (1-p)^r p^{mr}.$$

Por lo tanto, obtenemos la forma cerrada

$$\bbox[5px,border:2px solid #00A000]{ 1 - a_N + p^m a_{N-m} \quad \text{donde} \quad a_Q = \sum_{r=0}^{\lfloor Q/m\rfloor} {Q-mr\choose r} (-1)^r (1-p)^r p^{mr}.}$$

Nota que para $N\lt m$ obtenemos

$$1- {N\choose 0} \times 1 \times 1\times 1 = 0$$

que es el resultado correcto. También para $N=m$ obtenemos

$$1 - 1 - {0\choose 1} \times -1 \times (1-p) \times p^m + p^m \times 1 = p^m $$

lo cual también es correcto.

Ahora, para un análisis asintótico, notamos que la raíz $\rho$ con el módulo más pequeño de $1-v+(1-p)p^m v^{m+1}$ es aquella cercana a $v_0=1$ y obtenemos de Newton-Raphson la primera aproximación

$$v_1 = v_0 - \frac{1-v_0 + (1-p)p^m v_0^{m+1}}{-1+(m+1)(1-p)p^m v_0^{m}}.$$

Esto resulta en

$$1+ \frac{(1-p)p^m}{1-(m+1)(1-p)p^m} = \frac{1-m(1-p)p^m}{1-(m+1)(1-p)p^m} = \rho.$$

El término correspondiente de la descomposición en fracciones parciales es

$$\frac{1}{v-\rho} \mathrm{Res}_{v=\rho} \frac{1}{1-v+(1-p)p^m v^{m+1}} \\ = \frac{1}{v-\rho} \times \left.\frac{1}{-1+(m+1)(1-p)p^m v^{m}}\right|_{v=\rho} \\ = - \frac{1}{\rho} \frac{1}{1-v/\rho} \frac{1}{-1+(m+1)(1-p)p^m \rho^{m}}.$$

Por lo tanto, obtenemos

$$\bbox[5px,border:2px solid #00A000]{ a_Q \sim \frac{1}{\rho^{Q+1}} \frac{1}{1-(m+1)(1-p)p^m \rho^{m}}.}$$

Podemos reemplazar $\rho$ por una mejor aproximación de Newton-Raphson en un contexto donde se requieren cálculos numéricos, lo cual se hace en el código de muestra que sigue.

MRUNPROB :=
proc(N, m)
option remember;
local ind, d, pos, cur, run, runs, prob,
    zcnt, wcnt;

    prob := 0;

    for ind from 2^N to 2\*2^N-1 do
        d := convert(ind, base, 2);

        cur := -1; pos := 1;
        run := \[\]; runs := \[\];

        while pos <= N do
            if d\[pos\] <> cur then
                if nops(run) > 0 then
                    runs :=
                    \[op(runs), \[run\[1\], nops(run)\]\];
                fi;

                cur := d\[pos\];
                run := \[cur\];
            else
                run := \[op(run), cur\];
            fi;

            pos := pos + 1;
        od;

        runs := \[op(runs), \[run\[1\], nops(run)\]\];

        if nops(select(r -> (r\[1\] = 1 and r\[2\] >= m), runs)) > 0
        then
            wcnt := add(\`if\`(r\[1\] = 0, r\[2\], 0), r in runs);
            zcnt := add(\`if\`(r\[1\] = 1, r\[2\], 0), r in runs);

            prob := prob + p^zcnt \* (1-p)^wcnt;
        fi;
    od;

    expand(prob);
end;

V1 :=
proc(N, m)
option remember;
local gf;

    gf := (1-p^m\*v^m)/(1-v+(1-p)\*p^m\*v^(m+1));
    expand(1-coeftayl(gf, v=0, N));
end;

a := (Q, m) ->
add(binomial(Q-m\*r,r)\*(-1)^r\*(1-p)^r\*p^(m\*r),
    r = 0 .. floor(Q/m));

V2 :=
proc(N, m)
option remember;
    expand(1-a(N,m)+p^m\*a(N-m,m));
end;

a2 :=
proc(Q, m)
local rho;

    rho := (1-m\*(1-p)\*p^m)/(1-(m+1)\*(1-p)\*p^m);

    1/rho^(Q+1)\*1/(1-(m+1)\*(1-p)\*p^m\*rho^m);
end;

a3 :=
proc(Q, m, p)
local rho;

    rho :=
    sort(\[fsolve(1-v + (1-p)\*p^m\*v^(m+1), v)\],
         (r1, r2) -> abs(r1-1) < abs(r2-1));
    rho := op(1, rho);

    1/rho^(Q+1)\*1/(1-(m+1)\*(1-p)\*p^m\*rho^m);
end;

Answer 5

No creo que obtengas una fórmula analítica simple. El problema es esencialmente equivalente a este, mira mi respuesta allí: implica la potencia $n$ de una matriz estocástica de $m \times m$ (nota que allí nos interesan las secuencias de longitud igual o mayor a $m$), utilizando una cadena de Markov (como sugirió en los comentarios Shawn). También puedes encontrar allí algunas aproximaciones asintóticas.