I'm talking about a Roulette wheel with $38$ equally probable outcomes. Someone mentioned that he guessed the correct number five times in a row, and said that this was surprising because the probability of this happening was $$\left(\frac{1}{38}\right)^5$$

This is true if you only play the game $5$ times. However, if you play it more than $5$ times there's a higher (should be much higher?) probability that you'll get $5$ in a row at some point.

I was thinking about how surprised this person should be at their streak of $m$ correct guesses given that they play $n$ games, each with probability $p$ of success. It makes intuitive sense that their surprise should be proportional to $1/q$ (or maybe $\log(1/q)$ since $1$ in a billion doesn't surprise you $10$ times more than $1$ in $100$ million), where $q$ is the probability that they get at least one streak of $m$ correct guesses at some point in their $n$ games.

So, with the Roulette example I was thinking about, $p=1/38$ and $m=5$.

I tried to find an explicit formula for $q$ in terms of $n$, and encountered some difficulty, because of the non-independence of "getting a streak in the first five tries" and "getting a streak in tries $2$ through $6$" (if the first is a failure, it's much more likely that the second will be too).

In summary, two questions:

  1. How do I find the probability that you get $5$ correct guesses in a row at some point if you play $n$ games of Roulette?

  2. More generally, what is the probability that you get $m$ successes at some point in a series of $n$ events, each with probability $p$ of success?

The variables satisfy $\,\,\,m,n \in \mathbb{N}$, $\,\,\,m\leq n$, $\,\,\,p \in \mathbb{R}$, $\,\,\,0 \leq p \leq 1$.

If we write the answer to the second question as a function $q(m,n,p)$, then we can say that $q$ should be increasing with $n$, decreasing with $m$, and increasing with $p$. It should equal $p^n$ when $m=n$ and should equal $1$ when $p=1$ and $0$ when $p=0$.

I feel as though this should be a basic probability problem, but I'm having trouble solving it. Maybe some kind of recursive approach would work? Given $q(n,m,p)$, I think I could write $q(n+1,m,p)$ using the probability that the last $m-1$ results are all successes ...


You have a six-state system.
State 1: Not on a run. Either you haven't started, or the last guess was wrong.
State 2: The last guess was correct.
State 3: The last two guesses were correct.
State 4: The last three guesses were correct.
State 5: The last four guesses were correct.
State 6: You have a 5-in-a-row.
The transition matrix is $$A=\left(\begin{array}{cccccc} 1-p&p&0&0&0&0\\ 1-p&0&p&0&0&0\\ 1-p&0&0&p&0&0\\ 1-p&0&0&0&p&0\\ 1-p&0&0&0&0&p\\ 0&0&0&0&0&1 \end{array}\right)$$
The initial vector is $\vec{v}=(1,0,0,0,0,0)$
To find the probabilities after $n$ rounds, calculate $\vec{v}A^n$

  • $\begingroup$ I guess this is somewhat like a "recursive" method for finding the probability. +1, now I'll go figure out whether $A$ is diagonalizable, which would make finding $A^n$ way easier :) $\endgroup$ – Zubin Mukerjee Dec 26 '14 at 15:14
  • 1
    $\begingroup$ @ZubinMukerjee I've been trying to diagonalize this, it's a disaster. I think this is the best answer you're going to get. $\endgroup$ – Matt Samuel Dec 26 '14 at 15:20
  • 1
    $\begingroup$ Michael, the vector should be a row vector and the multiplication on the right. $\endgroup$ – Matt Samuel Dec 26 '14 at 15:26
  • $\begingroup$ @MattSamuel So $\vec{v}=(1,0,0,0,0,0)$ and the probability is the $6^\text{th}$ entry of the vector $\vec{v}A^n$? $\endgroup$ – Zubin Mukerjee Dec 26 '14 at 15:28
  • 1
    $\begingroup$ @ZubinMukerjee yes that's right. $\endgroup$ – Matt Samuel Dec 26 '14 at 15:33

Feller, "An Introduction to Probability Theory and Its Applications", Third Edition, gives a useful approximation on p. 325, equation 7.11.

Suppose we toss a possibly biased coin $n$ times, where the probability of a head is $p$ and $q = 1-p$. Let $q_n$ be the probability there is no run of $r$ successive heads. Then

$$q_n \sim \frac{1-px}{(r+1-rx)q} \cdot \frac{1}{x^{n+1}} $$

where $x$ is the smallest positive root of $1 - x + q p^r x^{r+1} = 0$.

For your problem, we have $r = 5$, $p = 1/38$, and $q = 37/38$, from which we calculate $x \approx 1 + 1.228854 \times 10^{-8}$.

It works out that $q_n = 1/2$ for $n \approx 5.64 \times 10^7$, i.e. it takes about 56 million trials to have a 50% chance of guessing correctly 5 times in a row.


To answer your general question, if the events are independent then the probability of getting only $m$ successes at a row once is $$(n-m+1)p^m(1-p)^{n-m}$$ This is because one can have success $m$ times at a row out of $n$ plays in $n-m+1$ ways and in each of these events have a probability $p^m$ of happening and the failures then happen in the rest of the $n-m$ cases with probability $(1-p)^{n-m}$.

EDIT: As I understand now my previous answer does not correctly address the question. Now, let $P(m,n)$ denote the required probability which is of getting $m$ or more consecutive successes in a series of $n$ independent events. Then, basically we want the event that the first time $m>1$ consecutive successes occur. Now, let $R_k(m,n)$ denotes the probability that $m$ consecutive successes happen for the first time at $n\ge k> m$ th trail. Then we have $$R_k(m,n)=qR_{k-1}(m,n-1)+pqR_{k-2}(m,n-2)+p^2qR_{k-3}(m,n-3)+\cdots+p^{m-1}qR_{k-m}(m,n-m)$$ with $R_1(m,n)=\cdots=R_{m-1}(m,n)=0,R_{m}(m,n)=p^m$ where $q=1-p$. Now, the probability $R_{k}(m,n)$ should not depend upon the second argument as long as $k\le n$. Then calling only $R_{k}$, and defining $r=[R_1\cdots R_n]^T$, we have the equation $$R_k=qR_{k-1}+pqR_{k-2}+\cdots+qp^{m-1}R_{k-m}$$ which can be solved by solving the equation $$x^m-qx^{m-1}-\cdots-qp^{m-2}x-qp^{m-1}=0$$ to get $R_k=\sum_{i=1}^m a_i \lambda_i^k$ where $\lambda_i$ are the roots of the last equation and the coefficients $a_i$ can be obtained from the initial conditions. Then, we have $$P(n,m)=\sum_{k=n-m}^n R_k=\sum_{i=0}^m a_i \frac{\lambda_i^{n-m}(1-\lambda_i^{m+1})}{1-\lambda_i}$$

  • $\begingroup$ I think your first formula is incorrect. Getting $m$ successes in a row at the very beginning of your $n$ trials is not independent from getting $m$ successes after $1$ failure (given that you didn't do the first thing, it's much less likely that you did the second). $\endgroup$ – Zubin Mukerjee Dec 26 '14 at 14:52
  • $\begingroup$ I am talking about ${only}$ $m$ successes at a row, that is I consider the case where the player wins only in those $m$ consecutive trials and loose everywhere else. In that case the two events that you mention ${are}$ independent. $\endgroup$ – Samrat Mukhopadhyay Dec 26 '14 at 14:55
  • $\begingroup$ Okay, but my question was about getting $m$ successes in a row at some point (not necessarily a failure in every other trial). $\endgroup$ – Zubin Mukerjee Dec 26 '14 at 14:57
  • $\begingroup$ Ok, for that I am adding the answer. $\endgroup$ – Samrat Mukhopadhyay Dec 26 '14 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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