Podemos proceder de la siguiente manera. Deje $p$ la probabilidad de que voltear la cabeza, y la $q=1-p$ la probabilidad de que se flip colas. Permítanos buscar la probabilidad de que NO tenemos, al menos, $k$ cabezas en una fila en algún momento después de $n$ volteretas, que denominaremos $P(n,k)$.
Dada una secuencia de lanzar una moneda (de longitud de, al menos, $k)$ que no tiene $k$ cabezas en una fila, el final de la secuencia debe ser una cola seguido por $i$ cabezas, donde $0\leq i<k$. Vamos a dejar que $P(n,k,i)$ denotar la probabilidad de que una cadena de longitud $n$ tiene menos de $k$ jefes Y termina con $i$ cabezas. Claramente $P(n,k)=\sum P(n,k,i)$. (Tenga en cuenta también que todavía podemos trabajar con $n<k$ por el tratamiento de una cadena de sólo $i$ cabezas como en la clase $(n,k,i)$).
Supongamos que tenemos una serie de $n$ coin flips, con no más de $k$ cabezas, y estamos en la clase de $(n,k,i)$. Lo que puede suceder si lanzamos la moneda una vez más? Si conseguimos colas, terminamos en la clase de $(n+1,k,0)$, lo cual ocurre con probabilidad de $q$, y si tenemos jefes, terminamos en la clase de $(n,k,i+1)$ que sucede con una probabilidad de $p$. La única advertencia es que si $i=k-1$, nuestra cadena tendrá $k$ cabezas en una fila si el siguiente es un recorrido de la cabeza.
A partir de esto, y usando el hecho de que el $(n+1)$st flip es independiente de las volteretas que vinieron antes, podemos calcular:
$$P(n+1,k,i+1)=pP(n,k,i) \qquad 0\leq i<k, $$
y así
$$P(n,k,i)=p^iP(n-i,k,0) \qquad 0\leq i<k.$$
Esto podría haber sido visto más directamente al señalar que la única manera de estar en la clase $(n,k,i)$ es tener una cadena en la clase $(n-i,k,0)$ y, a continuación, ha $i$ cabezas en una fila, lo que ocurre con probabilidad de $p^i$. Esto significa que sólo tenemos que utilizar las cosas de la forma $P(n,k)$ $P(n,k,0)$ en nuestros cálculos.
Por un razonamiento similar acerca de cómo las cadenas de venir, tenemos
$$P(n+1,k,0)=qP(n,k)=q\sum_{i=0}^{k-1} P(n,k,i)=q\sum_{i=0}^{k-1} p^iP(n-i,k,0).$$
Esto nos da una buena lineal de la recurrencia de la relación de $P(n,k,0)$, muy similar a la de la $k$-los números de Fibonacci, y dividiendo por $q$, podemos ver que $P(n,k)$ satisface la misma recurrencia. La adición de la condición inicial $P(n,k)=1$ si $n<k$ nos permite generar fácilmente los valores que necesitamos.
Por otra parte, si multiplicamos nuestro recurrencia por $p^{-(n+1)}$, obtenemos un poco más simple recurrencia de $Q(n+1,k,0)=p^{-(n+1)}P(n+1,k,0)$, es decir,
$$Q(n+1,k,0)=\frac{q}{p} \sum_{i=0}^{k-1} Q(n-i,k,0).$$
Al $p=q$, esto se convierte en la recurrencia de la $k$-los números de Fibonacci.
