Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.