# Given n raffles, what is the chance of winning k in a row?

I was reading this interesting article about the probability of of tossing heads k times in a row out of n tosses. The final result was

$$P = 1-\frac{\operatorname{fib}_k(n+2)}{2^n}\;,$$

where $\operatorname{fib}_k(n)$ is the $n$-th $k$-step Fibonacci number.

However, I could not figure out how to adapt it to cases where the probability is not half but just some generic $p$. How do I approach that, and is there a generic solution for all $p$?

To be clear, $n$ is the number of raffles, $p$ is the probability of winning a single one, and $k$ is the number of consecutive successes required. $P$ is the desired value.

-

We can proceed as follows. Let $p$ be the probability that we flip a head, and $q=1-p$ the probability that we flip tails. Let us search for the probability that we do NOT have at least $k$ heads in a row at some point after $n$ flips, which we will denote $P(n,k)$.

Given a sequence of coin tosses (of length at least $k)$ which does not have $k$ heads in a row, the end of sequence must be a tail followed by $i$ heads, where $0\leq i<k$. We will let $P(n,k,i)$ denote the probability that a string of length $n$ has less than $k$ heads AND ends with $i$ heads. Clearly $P(n,k)=\sum P(n,k,i)$. (Also note that we can still work with $n<k$ by treating a string of just $i$ heads as being in the class $(n,k,i)$).

Suppose we have a series of $n$ coin flips, with no more than $k$ heads, and we are in the class $(n,k,i)$. What can happen if we flip the coin once more? If we get tails, we end up in class $(n+1,k,0)$, which happens with probability $q$, and if we get heads, we end up in the class $(n,k,i+1)$ which happens with probability $p$. The only caveat is that if $i=k-1$, our string will have $k$ heads in a row if the next run is a head.

From this, and using the fact that the $(n+1)$st flip is independent of the flips that came before, we can calculate:

$$P(n+1,k,i+1)=pP(n,k,i) \qquad 0\leq i<k,$$

and so $$P(n,k,i)=p^iP(n-i,k,0) \qquad 0\leq i<k.$$

This could have been seen more directly by noting that the only way to be in the class $(n,k,i)$ is to have a string in class $(n-i,k,0)$ and to then have $i$ heads in a row, which happens with probability $p^i$. This means that we only need to use things of the form $P(n,k)$ and $P(n,k,0)$ in our calculations.

By similar reasoning about how strings come about, we have $$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).$$

This gives us a nice linear recurrence relation for $P(n,k,0)$ very similar to the one for the $k$-Fibonacci numbers, and dividing by $q$, we see that $P(n,k)$ satisfies the same recurrence. Adding the initial condition $P(n,k)=1$ if $n<k$ allows us to easily generate the values we need.

Moreover, if we multiply our recurrence by $p^{-(n+1)}$, we get a slightly simpler recurrence for $Q(n+1,k,0)=p^{-(n+1)}P(n+1,k,0)$, namely

$$Q(n+1,k,0)=\frac{q}{p} \sum_{i=0}^{k-1} Q(n-i,k,0).$$

When $p=q$, this becomes the recurrence for the $k$-Fibonacci numbers.

-