6
$\begingroup$

I thought of this question lately, but I'm not satisfied with the answer I got:

If I flip a coin 100 times, what is the probability that I will get a streak of at least ten of the same side?

The way I thought of solving it was just: $\left(90 \times 0.5 ^ 9\right) = 0.0879$, but this has to be wrong because, for the probability of getting a streak of at least 4 in the same scenario, it yields: $\left(96 \times 0.5 ^ 3\right) = 12$, which obviously doesn't make sense.

$\endgroup$
  • $\begingroup$ Not sure what the formula is, but I just ran some quick simulations, and whatever your formula is should give something close to 0.0866.... in case people want to check their work before they post. :) $\endgroup$ – Scott Apr 9 '16 at 13:17
6
$\begingroup$

According to this page, there is a closed form expression for just this problem.

...the probability, S, of getting K or more heads in a row in N independent attempts (where p is the probability of heads and q=1-p is the probability of tails) is:

$$ S(N,K) = p^K\sum_{T=0}^\infty {N-(T+1)K\choose T}(-qp^K)^T-\sum_{T=1}^\infty {N-TK\choose T}(-qp^K)^T $$

With the unusual convention that ${A\choose B}= 0$ for $A < B$. Numerical evaluation gives me 0.0441372 for the case of $p=1/2$, $N=100$, $K=10$.

Edit 1

Reworking it a bit to get rid of that weird convention just changes the upper limit.

$$ p^k \sum _{t=0}^{\frac{n-k}{k+1}} \binom{n-k (t+1)}{t} \left(-q p^k\right)^t-\sum _{t=1}^{\frac{n}{k+1}} \binom{n-k t}{t} \left(-q p^k\right)^t $$

The following Mathematica code gives you numbers, just plug in p, n, k in the last substitution bit.

-\!\(
\*UnderoverscriptBox[\(\[Sum]\), \(t = 1\), 
FractionBox[\(n\), \(1 + k\)]]\(
\*SuperscriptBox[\((\(-
\*SuperscriptBox[\(p\), \(k\)]\)\ q)\), \(t\)]\ Binomial[n - k\ t, 
       t]\)\) + p^k \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(t = 0\), 
FractionBox[\(\(-k\) + n\), \(1 + k\)]]\(
\*SuperscriptBox[\((\(-
\*SuperscriptBox[\(p\), \(k\)]\)\ q)\), \(t\)]\ Binomial[
       n - k\ \((1 + t)\), t]\)\) //. {k -> 10, n -> 100, q -> 1 - p, 
   p -> 1/2} // N

Edit 2

It has recently been pointed out by Mark L. Stone that the above is for a streak of heads, but not for the case of either streak occurring. I'd recommend reading his post below.

$\endgroup$
  • $\begingroup$ I'm not sure I'd call that a closed form, but it is definitely going to be something messy like that. $\endgroup$ – Thomas Andrews May 6 '13 at 20:17
  • $\begingroup$ I mean, it's not the case that Monte Carlo is the ONLY way to answer the question. It's not that bad when you expand it, each $(N,K)$ pair gives an $N$th order polynomial in the probability $p$ of the coin. $\endgroup$ – rajb245 May 6 '13 at 20:43
  • $\begingroup$ That's the probability of getting 10 or more heads in a row. Presumably if I want the probability of getting 10 or more of the same (of either heads or tails) in a row, it would be double that? $\endgroup$ – user1546083 May 6 '13 at 22:17
  • $\begingroup$ Note that with these parameters, it is not correct, contrary to the comment by @user1546083 immediately above, to perform a calculation for getting a streak of at least 10 heads, and then doubling it to include tails, because it is possible to get a streak of at least 10 heads and another of at least 10 tails in the same 100 coin flips. In light of this, the accepted answer by rajb245 does not answer the question as asked, and as of now, my answer is the only one to have exactly solved the question as asked, $\endgroup$ – Mark L. Stone Apr 13 '16 at 1:54
  • $\begingroup$ Good work, Mark. I indeed misinterpreted the question three years ago. I'm glad you came up with a method that gives the right answer. $\endgroup$ – rajb245 Apr 13 '16 at 15:37
3
$\begingroup$

EDIT: I have added to the end of this answer the solution to the generalization of this problem to a coin flip with probability p of heads. The question as stated is based on p = 0.5

This can be readily solved "exactly" by using a 10 state (stationary, i.e., time-homogeneous) discrete time Markov Chain, with state i, from 1 to 10, being the length of the current streak (whether heads or tails). The answer is 0.086659044348362, with which the comment by @Scott above is consistent. The details are below.

Take the initial state to be 1, corresponding to a streak of 1 after 1 coin flip (there will always be a streak of 1 after 1 coin flip). Let state 10 be an absorbing state (once state 10 is reached, a streak of at least 10 has occurred, so "we're done").

The one step transition matrix is populated as follows:

In state 1, there is a 0.5 probability of staying in state 1 (but now we have started a new streak on the other side of the coin), and 0.5 probability of moving to state 2.

In states 2 through 9: there is a 0.5 probability of moving to state 1 (i.e.,the current streak is terminated, and a new streak is started on the other side of the coin), and 0.5 probability of moving to the state incremented by 1 (i.e., from state i to state i+1).

State 10 has probability of 1 of staying in state 10, which is absorbing.

So to summarize, the one-state transition matrix is all zeros except for:

row 1 columns 1 and 2 are 0.5
rows 2 through 9: columns 1 and "row + 1" are 0.5
row 10: column 10 is 1

Because we start the Markov Chain after one coin toss, we need to do 99 more coin tosses, and therefore 99 Markov Chain steps to constitute 100 coin flips. Therefore the answer is the probability of being in state 10 after 99 Markov Chain steps, having started in state 1, and so is the (1,10) entry of the {one-step transition matrix to the 99 power}. The answer, as previously stated, is 0.086659044348362.

Note that with these parameters, it is not correct, contrary to a comment by @user1546083 above, to perform a calculation for getting a streak of at least 10 heads, and then doubling it to include tails, because it is possible to get a streak of at least 10 heads and another of at least 10 tails in the same 100 coin flips. In light of this, the accepted answer by @rajb245 does not answer the question as asked, and as of now, my answer is the only one to have exactly solved the question as asked, with @scott getting a consolation prize for having apparently correctly simulated the problem.

EDIT: Here is the generalization of this problem to a coin flip with probability p of heads.

The astute reader will note that my solution for the p = 0.5 case takes advantage of the symmetry between heads (H) and tails (T) in order to keep the state space down to 10 states, in which the state indicates the length of the current streak, and does not distinguish between H and T. In the general p not necessarily equal to 0.5 case, that "trick" no longer works, because the probability of extending the current streak depends on whether it is a streak of H or T.

Therefore, I now define a 21 state Markov Chain, with state 0 being the initial state of zero length streak, which is the state prior to the first coin toss. The remaining states are labeled 1H, 1T, 2H, 2T, ..., 10H, 10T, where the number indicates the length of the streak and the H or T indicates whether the streak is H or T. States 10H and 10T are both made to be absorbing states, and the probability of having a streak of (at least) 10H or (non-exclusive) 10T is the sum of the (0,10H) and (0,10T) entries of the one step transition matrix raised to the 100 power, i.e., of the 100 step transition matrix. The (0,10H) entry of that 100 step transition matrix is the probability that there is a streak of at least 10 heads and that it occurs before a streak (if any) of 10 tails. And of course, the (0,10T) entry of that 100 step transition matrix is the probability that there is a streak of at least 10 tails and that it occurs before a streak (if any) of 10 heads.

Starting in state 0, transition to 1H with probability p and to 1T with probability 1-p.

In state 1H, transition to 1T with probability 1-p and to 2H with probability p. In state 1T, transition to 1H with probability p and to 2T with probability 1-p. Etc. up through transitioning from states 9H and 9T.

States 10H and 10T are absorbing, so 10H transitions to 10H with probability 1, and 10T transitions to 10T with probability 1.

I will order the states as 0,1H,1T,2H,2T,...10H,10T. Given a value of p, the one-step transition matrix,TM, can be created in MATLAB (note that MATLAB array indices start with 1) with the code:

TM = zeros(21);
TM(1:2:19,2) = p; TM([1 2:2:18],3) = 1-p;
for i = 2:2:18, TM(i,i+2) = p; TM(i+1,i+3) = 1-p; end
MP(20,20) = 1; TM(21,21) = 1;

If we use this approach with p = 0.5, we of course duplicate the result of the earlier approach which was specialized for p = 0.5, namely that the (0,10H) and (0,10T) entries of the 100 step transition matrix are both 0.043329522174181, and their sum matches the previous result of 0.086659044348362 . If we let p = 0.6, then the (0,10H) entry of the 100 step transition matrix is 0.204426792384254, the (0,10T) entry of the 100 step transition matrix is 0.005246574538275, and their sum is 0.209673366922529, which is the probability of getting a H or (non-exclusive) T streak of at least 10 in a row. In the extreme case of p = 1, the probability of getting a streak of at least 10 heads is 1.

$\endgroup$
  • $\begingroup$ Is this your transition matrix: $$ T_1 = \frac{1}{2}\left[ \begin{array}{cccccccccc} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right] $$ $\endgroup$ – rajb245 Apr 13 '16 at 16:11
  • $\begingroup$ @ rajb245 , not quite.. You would need a 1 in the (10,10) entry, i.e., 1/2 * 2. Thanks. $\endgroup$ – Mark L. Stone Apr 13 '16 at 16:30
  • $\begingroup$ Ah yes, thanks! I couldn't get the numbers to match up, now they do. $\endgroup$ – rajb245 Apr 13 '16 at 16:40
  • $\begingroup$ In light of the edit I made, subsequent to the above comments, please note that the discussion with @ajb245 pertains to the transition matrix for my original solution, which is specialized for probability of heads = 0.5. $\endgroup$ – Mark L. Stone Apr 13 '16 at 23:21
  • 1
    $\begingroup$ @MarkL.Stone Shouldn't you edit your answer such that it reads "row 10: column 10 is 1"? $\endgroup$ – Dan Goldstein Nov 6 '17 at 15:36
2
$\begingroup$

EDIT: This answer is erroneous, because a streak can start at any number, not just at a given multiple at 10. Please disregard.

Q: If I flip a coin 100 times, what is the probability that I will get at least one streak of at least ten of the same side?

Assuming the coin is fair:

P(10 consecutive same side) = $0.5^{10}$
Conversely, the probability of that outcome not occurring is $1-0.5^{10}$. Call this outcome F.

Now, since you're flipping a coin 100 times, and 100 times corresponds to 10 such samples (of 10 flips each), we can do this simply with independence:

P(No Streak in 10 sets of samples): $F^{10}$
$\therefore$ P(At least one streak in 10 sets of samples) $= 1-F^{10}$
$\therefore$ P(At least one streak in 10 sets of samples) $= (1-(1-0.5^{10})^{10})$
$\therefore$ P(At least one streak in 10 sets of samples) $=0.00972...$

$\endgroup$
  • $\begingroup$ Cheers, this works. However, I don't see what you mean by "10 sets of samples"? $\endgroup$ – user1546083 May 6 '13 at 19:53
  • $\begingroup$ It should be "10 samples," I'll edit momentarily to clarify. Each "sample" has 10 flips, so 100 flips = 10 samples of 10 flips each. $\endgroup$ – xisk May 6 '13 at 19:54
  • $\begingroup$ $100$ corresponds to $91$ samples, since you can get $10$ heads in a row starting at any point. $\endgroup$ – Thomas Andrews May 6 '13 at 19:57
  • $\begingroup$ Certainly, even if you correct for the 91 samples issue, you get a problem that if you got $11$ in a row, you'd be counting the $10$ in a row twice; unlikely, so it gives a good approximation, but still not exactly equal. This is basically a really problematic answer $\endgroup$ – Thomas Andrews May 6 '13 at 20:00
1
$\begingroup$

Your calculation is essentially the expected number of streaks of that length. A naive approach would be that the chance that you don't start a run of $n$ on a a particular roll is $2^{n-1}$ as you realize. The chance of never starting a run of $10$ is then $(1-2^{9})^{91}$ and the chance of having at least one $1-(1-2^{9})^{91}\approx 0.163$ The reason for $91$ instead of $90$ is that you could start on any flip $1$ through $91$. The reason for the weasel words is this calculation assumes the chance of starting a run on flip 2 is independent of the chance of starting on 1 or 3, but they interact.

$\endgroup$
-1
$\begingroup$

I think it would be easier to use this formula $\sum_{i=1}^n \binom{n}{i}p^i(1-p)^{n-i} $, where $n$ is the number of times the action occurred (in this case, the coin flip), and $p$ is the probability of the chosen event happening (in this case, $\frac{1}{1024}$ for a streak of ten). Plugging that in would give us $\sum_{i=1}^{100} \binom{100}{i} (\frac{1}{1024})^i(1-\frac{1}{1024})^{100-i} \approx .0930826...$, or about 9.9%

$\endgroup$
  • $\begingroup$ There seems to be some disconnect between this approach and the problem formulation. The coin is flipped $100$ times, but a streak of ten of the same outcomes (all heads or all tails) does not occur solely because of one flip. So you cannot simply take $p = 1/1024$, and if you did, that binomial formula would sum up to $1.0$, not $0.093...$. $\endgroup$ – hardmath Oct 14 '18 at 0:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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