If you attempt to predict a Roulette wheel $n$ times, what's the probability you'll get $5$ in a row at some point?

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$

• 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 :) – Zubin Mukerjee Dec 26 '14 at 15:14
• @ZubinMukerjee I've been trying to diagonalize this, it's a disaster. I think this is the best answer you're going to get. – Matt Samuel Dec 26 '14 at 15:20
• Michael, the vector should be a row vector and the multiplication on the right. – Matt Samuel Dec 26 '14 at 15:26
• @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$? – Zubin Mukerjee Dec 26 '14 at 15:28
• @ZubinMukerjee yes that's right. – 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}$$

• 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). – Zubin Mukerjee Dec 26 '14 at 14:52
• 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. – Samrat Mukhopadhyay Dec 26 '14 at 14:55
• Okay, but my question was about getting $m$ successes in a row at some point (not necessarily a failure in every other trial). – Zubin Mukerjee Dec 26 '14 at 14:57
• Ok, for that I am adding the answer. – Samrat Mukhopadhyay Dec 26 '14 at 14:58