Número esperado de lanzamientos para obtener una sola Cara seguida de k Colas Consecutivas

Question

Estoy trabajando en una pregunta de probabilidad donde debo encontrar el número esperado de lanzamientos para lograr el siguiente patrón:

HTTTTTTTT...... (k-Colas consecutivas (T))

Hice esta respuesta como el caso base para resolver este problema:

https://math.stackexchange.com/q/364135

Sea e el número esperado de lanzamientos. Siguiendo la lógica de la respuesta, digamos que obtenemos una Cola (T) inmediatamente después de comenzar el experimento. Entonces el número esperado aumentaría en 1 ya que realmente necesitamos una Cabeza antes de la Cola. Por lo tanto, el número esperado sería $(e+1)$ con una probabilidad de $\frac{1}{2}$...

De manera similar, si obtengo una Cabeza (H) seguida de otra Cabeza (H), entonces el número esperado seguiría siendo $(e+1)$ con una probabilidad de $\frac{1}{2}$ ... y así sucesivamente.

La ecuación que derivé es algo así:

$$e = \frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+...+\frac{1}{2^{k+1}}(e+k+1)+\frac{1}{2^{k+1}}(k)$$

y después de resolver lo anterior para $e$ obtuve una forma final agradable como:

$$e = 3*(2^{k+1} - (k+2))$$

¿Alguien puede comentar sobre la precisión de la ecuación inicial que se me ocurrió? Porque tengo dudas al respecto. Creo que el primer término debería ser $\frac{1}{2}(e+1) + \frac{1}{2}(e+1)$.

¿Por qué dos veces? Porque esto puede ocurrir si obtenemos el primer lanzamiento como Cola (T) así como si obtenemos los dos primeros lanzamientos consecutivos como Cabezas (H) lo que significa que la primera Cabeza (H) es inútil y, por lo tanto, solo actuaría para aumentar el número esperado de lanzamientos en 1. ¿Es ese el caso?

Answer 1

El razonamiento del problema TTT no se traduce directamente al problema HTTT. En el problema TTT, si obtienes unas pocas T (menos de k) y luego una H, vuelves al punto de partida: buscando la primera ocurrencia de TTTT. En el problema HTTT, si obtienes un HT[...]TH con menos de k T, te hace retroceder pero no totalmente: estás buscando TTT, no HTTT (porque ya tienes una H). Vas a necesitar más de una variable.

Una solución simple es notar que el proceso consta de dos partes:

1. tirar la moneda hasta que obtengas la primera H, luego
2. tirar la moneda hasta que obtengas k T consecutivas, es decir exactamente https://math.stackexchange.com/q/364135

El número total esperado de tiradas es solo la suma de los dos, es decir, $2 + (2^{k+1}-2) = 2^{k+1}$

Más cercano a tu línea de razonamiento: permita que $e_1$ sea la respuesta al problema (número esperado de lanzamientos hasta HTTT...T), $e_2$ sea el número esperado de lanzamientos restantes dado que el resultado anterior es H. Considere $e_1$. Si el primer resultado es H, la respuesta es $e_2+1$. Si el primer resultado es T, volvemos al punto de inicio, por lo que la respuesta es $e_1+1. Por lo tanto:

$$ e_1=\frac{1}{2}(e_2+1)+\frac{1}{2}(e_1+1)\\ e_1=e_2+2 $$

De manera similar, para $e_2$ consideramos los prefijos mutuamente excluyentes H (con respuesta $e_2+1$), TH ($e_2$+2), TTH ($e_2+3$), ..., TT...TH (k-1 T's) ($e_2+k$) y finalmente TTT...T (k T's) ($k$, ya que es el final de la secuencia), por lo que obtenemos la ecuación $$ e_2=\left(\frac{1}{2}(e_2+1)+\frac{1}{4}(e_2+2)+...+\frac{1}{2^k}(e_2+k)\right)+\frac{1}{2^k}k\\ e_2=2^{k+1}-2 $$

Nota que este problema es un caso un poco especial: la ecuación para $e_2$ no involucra a $e_1$, por lo que podríamos resolver las ecuaciones para $e_1$ y $e_2$ de forma independiente. Para una cadena arbitraria obtendríamos un sistema de ecuaciones lineales. Ejercicio: HTH. Respuesta: (spoiler!)

$$e_1=1+\frac{1}{2}(e_1+e_2)\\e_2=1+\frac{1}{2}(e_2+e_3)\\e_3=1+\frac{1}{2}e_1$$

Answer 2

Para cada entero no negativo $r$,

• Sea $T^r$ la secuencia de $r$ lanzamientos consecutivos de $T$.$\\[4pt]$
• Sea $HT^r$ la secuencia de $r+1$ lanzamientos, donde el primer lanzamiento es $H$, seguido por la secuencia $T^r$.

Fija un entero positivo $k$.

Sea $e$ el número esperado de lanzamientos para obtener $k+1$ lanzamientos consecutivos que coincidan con la secuencia $HT^k$.

Reclamación:$\;e=2^{k+1}$.

Prueba:

Para $0\le r \le k$, sea $f(r)$ el número esperado de lanzamientos para obtener la secuencia $HT^k$, dado que se necesitan exactamente $r$ lanzamientos consecutivos de $T$ para completarla (es decir, la secuencia de los $k-r+1$ lanzamientos anteriores es $HT^{k-r}$).

Claramente, $f(0) = 0$.

Para la variable $e$, tenemos la recursión $$e = 1+\left({\small{\frac{1}{2}}}\right)e+\left({\small{\frac{1}{2}}}\right)f(k)$$ lo cual da como resultado $$e=2+f(k)\tag{eq1}$$

En particular, si $k=0$, entonces $e=2+f(0) = 2 = 2^{k+1}$, como se afirmó.

Para $1\le r \le k$, tenemos la recursión $$f(r) = 1+\left({\small{\frac{1}{2}}}\right)f(r-1)+\left({\small{\frac{1}{2}}}\right)f(k)\tag{eq2}$$

Consideremos dos casos . . .

Caso $(1)$:$\;k=1$.

Entonces para $r=1,\;(\text{eq}2)$ se reduce a $$f(1) = 1+\left({\small{\frac{1}{2}}}\right)f(0)+\left({\small{\frac{1}{2}}}\right)f(1)$$ lo cual da como resultado $f(1)=2$, por lo tanto $e=2+f(1) = 4 = 2^{k+1}$, como se afirmó.

Caso $(2)$:$\;k \ge 2$.

Entonces para $1\le r\le k,\;(\text{eq}2)$ produce $$f(r) - \left({\small{\frac{1}{2}}}\right)f(r-1)=1+\left({\small{\frac{1}{2}}}\right)f(k)\tag{eq3}$$ por lo tanto, dado que la $\text{RHS}$ de la ecuación anterior es constante, obtenemos la recursión $$f(r) - \left({\small{\frac{1}{2}}}\right)f(r-1)=f(r-1) - \left({\small{\frac{1}{2}}}\right)f(r-2)\tag{eq4}$$ para $2\le r\le k$.

Simplificando $(\text{eq4})$, obtenemos $$2f(r)-3f(r-1)+f(r-2)=0\tag{eq5}$$ para $2\le r\le k$.

Así, tenemos una recurrencia lineal homogénea de segundo orden con coeficientes constantes.

Notando que el polinomio característico de $(\text{eq}5)$ es $2x^2-3x+1 = (x-1)(2x-1)$, se sigue que existen constantes $a,b\in\mathbb{C}$ tales que $$f(r)=a+\frac{b}{2^r}\tag{eq6}$$ para $0 \le r \le k$.

De $f(0)=0$, $(\text{eq}6)$ da $b=-a$, por lo tanto $$f(r)=a-\frac{a}{2^r}\tag{eq7}$$ para $0 \le r \le k$.

Por $(\text{eq}7)$, obtenemos $f(1) = {\large{\frac{a}{2}}}$, por lo tanto, \begin{align*} &f(1) - \left({\small{\frac{1}{2}}}\right)f(0) = 1+\left({\small{\frac{1}{2}}}\right)f(k)&&\text{[por $(\text{eq}3)$]}\\[4pt] \implies\;&\left({\small{\frac{a}{2}}}\right) - \left({\small{\frac{1}{2}}}\right)(0) = 1+\left({\small{\frac{1}{2}}}\right)f(k)\\[4pt] \implies\;&a= 2+f(k)\\[4pt] \implies\;&a=e&&\text{[por $(\text{eq}1)$]}\\[4pt] \end{align*} por lo tanto, $(\text{eq}7)$ se convierte en $$f(r)=e-\frac{e}{2^r}\tag{eq8}$$ para $0 \le r \le k$.

Luego, usando $r=k$ en $(\text{eq}8)$, obtenemos \begin{align*} &f(k)=e-\frac{e}{2^k}\\[4pt] \implies\;&e-2=e-\frac{e}{2^k}&&\text{[por $(\text{eq}1)$]}\\[4pt] \implies\;&\frac{e}{2^k}=2\\[4pt] \implies\;&e=2^{k+1}\\[4pt] \end{align*> como se afirmó.

Answer 3

Usando $z$ para caras y $w$ para cruces, podemos codificar el problema en la siguiente función generadora:

$$(1+w+w^2+\cdots) \\ \times \sum_{q\ge 0} (z+z^2+\cdots)^q (w+w^2+\cdots+w^{k-1})^q \\ \times (z+z^2+\cdots) w^k.$$

Esto es

$$\frac{1}{1-w} \sum_{q\ge 0} \frac{z^q}{(1-z)^q} w^q \frac{(1-w^{k-1})^q}{(1-w)^q} \\ \times \frac{z}{1-z} w^k.$$

Ya no necesitamos distinguir caras y cruces en este momento y obtenemos

$$F(z) = \frac{z^{k+1}}{(1-z)^2} \frac{1}{1-z^2(1-z^{k-1})/(1-z)^2} \\ = \frac{z^{k+1}}{(1-z)^2-z^2(1-z^{k-1})} = \frac{z^{k+1}}{1-2z+z^{k+1}}.$$

La expectativa deseada está dada por

$$\left. z \frac{d}{dz} F(z) \right|_{z=1/2} \\ = z \left.\left(\frac{(k+1) z^{k}}{1-2z+z^{k+1}} - \frac{z^{k+1}}{(1-2z+z^{k+1})^2} (-2+(k+1)z^k ) \right)\right|_{z=1/2.} \\ = \frac{1}{2}\left(\frac{(k+1)/2^k}{1/2^{k+1}} - \frac{1/2^{k+1}}{1/2^{2k+2}} (-2 + (k+1)/2^k)\right) \\ = \frac{1}{2}(2(k+1) + 2^{k+2} - 2(k+1)) = \frac{1}{2} 2^{k+2}.$$

Esto es $$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[X] = 2^{k+1}.}$$

Hay un programa muy simple para verificar este resultado.

#include #include #include int main(int argc, char \*\*argv)
{
  int k = 4; long tind, trials = 1000;

  if(argc >= 2){
    k = atol(argv\[1\]);
    assert(k >= 1);
  }

  if(argc >= 3){
    trials = atol(argv\[2\]);
    assert(trials >= 1);
  }

  long long total = 0;

  for(tind=0; tind < trials; tind++){
    int pos, buf\[k+1\];

    for(pos=0; pos <= k; pos++){
      buf\[pos\] = -1;
    }

    int steps = 0; int found = 0;

    while(!found){
      int flip = drand48()\*(double)(2);
      steps++;

      for(pos=1; pos <= k; pos++){
        buf\[pos-1\] = buf\[pos\];
      }
      buf\[k\] = flip;

      if(buf\[0\] == 1){
        for(pos=1; pos <= k; pos++){
          if(buf\[pos\] == 1) break;
        }

        if(pos == k+1){
          found = 1;
        }
      }
    }

    total += steps;
  }

  printf("\[k=%d, trials=%ld\]; %le\\n",
         k, trials,
         (double)total/(double)trials);

  exit(0);
} 

Ejecuta esto para obtener por ejemplo

$ ./ct 5 100000000 [k=5, trials=100000000]; 6.399918e+01 $