Conseguir $k$ Cabezas consecutivas

Question

Si se lanza una moneda 3 veces, hay 8 resultados posibles:

$$\text{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}$$

En el experimento anterior vemos que 1 secuencia tiene 3 H consecutivas, 3 secuencias tienen al menos 2 H consecutivas y 7 secuencias tienen al menos una única H.

Supongamos que se lanza una moneda $n$ veces. ¿Cuántas secuencias obtendremos que contengan al menos $k$ ¿cabezas consecutivas?

Alguien resolvió este problema utilizando esta relación recursiva $$F(n,k) = 2F(n - 1,k) + 2^{(n-k-1)} - F(n-k-1,k)\,,$$ pero no puedo entender cómo funciona esta fórmula. ¿Alguien puede explicarlo?

Answer 1

Hay dos maneras de obtener una carrera de al menos $k$ cabezas en $n$ lanzamientos:

1. Ya había una racha de al menos $k$ cabezas en la primera $n-1$ lanzamientos. Estas posibilidades, que por definición son $F(n-1,k)$ puede ser seguido independientemente por cara o por cruz, duplicando así la cantidad a $2F(n-1,k)$ posibilidades.

2. El último lanzamiento creó una racha de al menos $k$ cabezas. Evidentemente, entonces, el último lanzamiento fue una cabeza y el último $k-1$ lanza fuera de la primera $n-1$ También los lanzamientos fueron cara, pero inmediatamente antes de esa secuencia hubo una cola. Independientemente de estos resultados, el primer $n-k-1$ los lanzamientos podrían haber sido cualquier cosa, produciendo $2^{n-k-1}$ posibilidades.

Sin embargo, algunas secuencias pueden haberse contabilizado tanto en (1) como en (2): son los que, en su caso, cumplen ambas condiciones. Aunque la condición (1) afirma que hubo una racha de menos $k$ cabezas en la primera $n-1$ lanzamientos, la condición (2) coloca esa secuencia dentro de la primera $n-k-1$ de los lanzamientos. Así, las secuencias doblemente contadas son aquellas en las que una serie de $k$ cabezas ya se habían observado dentro de la primera $n-k-1$ lanzamientos, una cantidad que los números $F(n-k-1,k)$ . Esta cantidad debe restarse de la suma de (1) y (2), dando lugar a la recursión.

Este argumento tiene sentido siempre que $n-k-1 \ge 0$ . Para iniciar la recursión, $F(n,k)=0$ siempre que $n\lt k$ y $F(k,k)=1$ , ambos resultados son obvios.