88
$\begingroup$

A fair coin is tossed repeatedly until 5 consecutive heads occurs.

What is the expected number of coin tosses?

$\endgroup$
4
  • 5
    $\begingroup$ Yet another copy and paste from Brilliant.org: brilliant.org/i/5rCgJ3 $\endgroup$
    – Erick Wong
    Apr 17 '13 at 5:49
  • 2
    $\begingroup$ @ErickWong: Is this a recent problem on brilliant.org? $\endgroup$
    – robjohn
    Apr 17 '13 at 8:48
  • 1
    $\begingroup$ geeksforgeeks.org/… $\endgroup$ Jul 2 '20 at 13:02
  • $\begingroup$ Downvoted because steal. $\endgroup$
    – SAJW
    Apr 10 '21 at 20:48

15 Answers 15

117
$\begingroup$

Let $e$ be the expected number of tosses. It is clear that $e$ is finite.

Start tossing. If we get a tail immediately (probability $\frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\frac{1}{4}$), then the expected number is $e+2$. Continue $\dots$. If we get $4$ heads then a tail, the expected number is $e+5$. Finally, if our first $5$ tosses are heads, then the expected number is $5$. Thus $$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{16}(e+4)+\frac{1}{32}(e+5)+\frac{1}{32}(5).$$ Solve this linear equation for $e$. We get $e=62$.

$\endgroup$
15
  • 2
    $\begingroup$ It is clear that e is finite, but how can you show it properly though ? Thanks. $\endgroup$
    – Dark
    Jul 3 '15 at 17:39
  • 5
    $\begingroup$ If one wants, let $X$ be the number of tosses. Then $\Pr(X=n)\le (1/2)^{n-5}$. So $E(X)\le \sum n (1/2)^{n-5}$, a convergent series. $\endgroup$ Jul 3 '15 at 17:58
  • 29
    $\begingroup$ The same method obviously generalizes to give $e_n$, the expected number of tosses to get $n$ consecutive heads ($n \ge 1$): $$e_n=\frac{1}{2}(e_n+1)+\frac{1}{4}(e_n+2)+\frac{1}{8}(e_n+3)+\frac{1}{16}(e_n+4)+\cdots +\frac{1}{2^n}(e_n+n)+\frac{1}{2^n}(n),$$ the solution of which is easily found to be $$e_n = 2(2^n - 1).$$ $\endgroup$
    – r.e.s.
    Jul 19 '15 at 23:57
  • 7
    $\begingroup$ Why are TT, TTT not considered? $\endgroup$
    – Jaydev
    Jul 24 '17 at 1:24
  • 7
    $\begingroup$ @Jaydev TT and TTT both are covered by the case "if we get a tail immediately". $\endgroup$
    – David K
    Oct 6 '17 at 13:13
48
$\begingroup$

Lets calculate it for $n$ consecutive tosses the expected number of tosses needed.

Lets denote $E_n$ for $n$ consecutive heads. Now if we get one more head after $E_{n-1}$, then we have $n$ consecutive heads or if it is a tail then again we have to repeat the procedure.

So for the two scenarios:

  1. $E_{n-1}+1$
  2. $E_{n}{+1}$ ($1$ for a tail)

So, $E_n=\frac12(E_{n-1} +1)+\frac12(E_{n-1}+ E_n+ 1)$, so $E_n= 2E_{n-1}+2$.

We have the general recurrence relation. Define $f(n)=E_n+2$ with $f(0)=2$. So,

\begin{align} f(n)&=2f(n-1) \\ \implies f(n)&=2^{n+1} \end{align}

Therefore, $E_n = 2^{n+1}-2 = 2(2^n-1)$

For $n=5$, it will give us $2(2^5-1)=62$.

$\endgroup$
4
  • 2
    $\begingroup$ Amazing solution, thank you $\endgroup$
    – Jaydev
    Jul 24 '17 at 1:30
  • $\begingroup$ Nice solution! I didn't realize we can form a recurrence relation for expectation. $\endgroup$
    – Idonknow
    Dec 28 '19 at 13:28
  • 1
    $\begingroup$ Beautiful construction of f(n) $\endgroup$ Dec 24 '20 at 15:52
  • $\begingroup$ For those of you who did not understand. we are in a state where we already have n-1 heads. So either we get one more heads, or we get a tails and we need to get n consecutive heads again. $\endgroup$ Oct 8 '21 at 9:17
33
$\begingroup$

Here is a generating function approach.

Consider the following toss strings, probabilities, and terms

$$ \color{#00A000}{ \begin{array}{llc} T&\frac12&\qquad\frac12x\\ HT&\frac14&\qquad\frac14x^2\\ HHT&\frac18&\qquad\frac18x^3\\ HHHT&\frac1{16}&\qquad\frac1{16}x^4\\ HHHHT&\frac1{32}&\qquad\frac1{32}x^5\\ \color{#C00000}{HHHHH}&\color{#C00000}{\frac1{32}}&\color{#C00000}{\qquad\frac1{32}x^5} \end{array} } $$ Each term has the probability as its coefficient and the length of the string as its exponent.

Possible outcomes are any combination of the green strings followed by the red string. We get the generating function of the probability of ending after $n$ tosses to be $$ \begin{align} f(x)&=\sum_{k=0}^\infty\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)^k\frac1{32}x^5\\ &=\frac{\frac1{32}x^5}{1-\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)}\\ &=\frac{\frac1{32}x^5}{1-\frac{\frac12x-\frac1{64}x^6}{1-\frac12x}}\\ &=\frac{\frac1{32}x^5-\frac1{64}x^6}{1-x+\frac1{64}x^6} \end{align} $$ The average duration is then $$ \begin{align} f'(1) &=\left.\frac{\left(\frac5{32}x^4-\frac6{64}x^5\right)\left(1-x+\frac1{64}x^6\right)-\left(\frac1{32}x^5-\frac1{64}x^6\right)\left(-1+\frac6{64}x^5\right)}{\left(1-x+\frac1{64}x^6\right)^2}\right|_{\large x=1}\\ &=\frac{\frac4{64}\frac1{64}+\frac1{64}\frac{58}{64}}{\left(\frac1{64}\right)^2}\\[12pt] &=62 \end{align} $$

$\endgroup$
11
  • 1
    $\begingroup$ Could you elaborate briefly on why the derivative gives the expected number of flips? $\endgroup$ Aug 20 '13 at 2:37
  • 3
    $\begingroup$ @AustinMohr: If $f(x)$ is the generating function of the probability $p_n$ of the ending after $n$ tosses $$ f(x)=\sum_{n=0}^\infty p_nx^n $$ then, because the probability of lasting an infinite number of tosses is $0$, we have $$ \begin{align} f(1) &=\sum_{n=0}^\infty p_n\\ &=1 \end{align} $$ Furthermore, $$ \begin{align} f'(1) &=\sum_{n=0}^\infty n\,p_n\\ &=\mathrm{E}(n) \end{align} $$ $\endgroup$
    – robjohn
    Aug 20 '13 at 5:13
  • $\begingroup$ Do you know how to find the distribution (or expectation and variance) for the number of tosses until either 5 consecutive heads or 5 consecutive tails? (Or 5 consecutive equal results from rolling dice.) Is there a question on math.se about this? $\endgroup$ Dec 15 '15 at 14:17
  • $\begingroup$ I found an answer using martingales here: quora.com/… but I'm curious if there is a generating functions way (also about the distribution, say variance or number of trials until 90% probability of seeing what we want). $\endgroup$ Dec 15 '15 at 14:31
  • 1
    $\begingroup$ @Jaydev: note that the substrings listed in the table are components of the full string. the full string is composed of a combination of the green substrings followed by the red substring. Thus, $TT$ is represented by $$\overbrace{\left(\tfrac12x\right)}^{\color{#0A0}{T}}\overbrace{\left(\tfrac12x\right)}^{\color{#0A0}{T}}=\tfrac14x^2$$ $\endgroup$
    – robjohn
    Jul 24 '17 at 1:53
13
$\begingroup$

This problem is solvable with the next step conditioning method. Let $\mu_k$ denote the mean number of tosses until 5 consecutive heads occurs, given that $k$ consecutive heads just occured. Obviously $\mu_5=0$. Conditioning on the outcome of the next coin throw: $$ \mu_k = 1 + \frac{1}{2} \mu_{k+1} + \frac{1}{2} \mu_0 $$ Solving the resulting linear system:

In[28]:= Solve[Table[mu[k] == 1 + 1/2 mu[k + 1] + mu[0]/2, {k, 0, 4}],
   Table[mu[k], {k, 0, 4}]] /. mu[5] -> 0

Out[28]= {{mu[0] -> 62, mu[1] -> 60, mu[2] -> 56, mu[3] -> 48, 
  mu[4] -> 32}}

Hence the expected number of coin flips $\mu_0$ equals 62.

$\endgroup$
6
  • $\begingroup$ What tool did you use for solving? $\endgroup$
    – hola
    May 11 '15 at 17:19
  • $\begingroup$ @pushpen.paul I used Mathematica $\endgroup$
    – Sasha
    May 11 '15 at 17:20
  • $\begingroup$ Can you please explain the original equation? $\endgroup$
    – BOS
    Sep 20 '16 at 15:58
  • $\begingroup$ @BOS Since $\mu_k$ is the conditional expectation, consider the next coin toss. Because a new toss was made, we add 1, in the next state, with equal probabilities we either get next head, in which case we gonna get $k+1$ heads, hence $\mu_{k+1}$, or the tail, in which case we break the streak of consecutive heads, hence $\mu_0$. $\endgroup$
    – Sasha
    Sep 23 '16 at 3:03
  • 1
    $\begingroup$ @Sasha This is the Markov way of solving it, right? This seems most intuitive to me of all methods presented here. $\endgroup$ Dec 22 '17 at 8:06
3
$\begingroup$

Use Markov chains. The nice part of Markov Chains is that they can be applied to a huge class of similar problems with relatively little thought (it's almost formulaic in application). It's also the most intuitive way to handle these problems.

(in Matlab code notation below)

%% setup full transition matrix with states from zero heads to 5 heads

T = $[ones(5,1)*.5,eye(5)*.5];$

$T = [T;zeros(1,6)]$

%%Take subset "Q" comprised of just transient states (5 heads is absorbing state) $Q = T(1:end-1,1:end-1);$

$M = inv(eye(5)-Q)$

absorbing Markov Chain has a similar example as this question BTW...

ans =

62
60
56
48
32

Where each row is the expected number of steps before being absorbed when starting in that transient state (0 through 4 heads, top to bottom).

$\endgroup$
3
$\begingroup$

I’m slightly surprised that no one has suggested this solution yet in such a highly active question.

Call a stretch of $5$ tosses all of which are heads a “success”. Divide a long series of tosses into segments after each tails that follows a success. The expected number of (overlapping) successes in each resulting segment is $1+\frac12+\frac14+\cdots=2$. Denote by $x$ the expected length of these segments up to the end of the first success. We must have $\frac{x+2}2=2^5$, since each segment on average contains $x+2$ tosses and $2$ successes, and the average number of successes per toss is $2^{-5}$. Thus $x=2^6-2=62$. Our initial state, in which we haven’t counted any heads yet, is equivalent to the state after a tails. Thus in this case, too, $62$ is the expected number of tosses up to the end of the first success.

$\endgroup$
1
  • $\begingroup$ Can you please explain a little bit more? How did you come up with 1+1/2+1/4+⋯ sum? $\endgroup$ Sep 22 '21 at 9:58
2
$\begingroup$

We can solve this without equations. Ask the following (auxiliary) question: how many flips you need to get either $N$ heads or $N$ tails. Then to get $N$ heads only you need twice as many flips. Start with the question of how many flips you need to get either $H$ or $T$. The answer is $$x = \frac12 (1) + \frac12 (1) = 1.$$ The reason is that there is $\frac12$ probability to get $H$, and after $1$ flip you are done. The same for $T$. To get only one $H$ you then need two flips. OK. Now we ask what it takes to get $HH$ or $TT$. The result is $$x=\frac12(1+2) + \frac12(1+2).$$ The number $2$ appears because, say you flip $H$ first, then you need on average $2$ flips to get another $H$, as we learned earlier. The same for $T$. So you need $3$ flips to get $TT$ or $HH$, and you need $6$ flips to get $HH$ only. And so on. You need $\frac12 (1+6) + \frac12(1+6) = 7$ flips to get either $HHH$ or $TTT$, and $14$ to get $HHH$ only. If you need $HHHH$ or $TTTT$, then flip $\frac12(1+14) + \frac12(1+14) = 15$ times, or $30$ times to get just $HHHH$. The sequence is $1, 3, 7, 15, \ldots$ to get either heads or tails. The formula is easy to extract: you need $2^N-1$ flips to get either $N$ heads or $N$ tails, or $2^{N+1}-2$ to get $N$ heads only. If $N=5$ we get the answer: $62$.

$\endgroup$
1
$\begingroup$

The question can be generalized to what is the expected number of tosses before we get x heads.Let's call this E(x). We can easily derive a recursive formula for E(x). Now, there are a total of two possibilities, first is that we fail to get the xth consecutive heads in xth attempt and second, we succeed. Probability of success is 1/(2^x) and probability of failure is 1-(1/(2^x)).

Now, if we were to fail to get xth consecutive heads in xth toss (i.e. case 1), the we will have to use a total of (E(x)+1) moves, because one move has been wasted.

On the other hand if we were to succeed in getting xth consecutive head in xth toss (i.e. case 2), the total moves is E(x-1)+1 , because we now take one move more than that was required to get x-1 consecutive heads.

So,

E(x) = P(failure) * (E(x)+1) + P(success) * (E(x-1)+1)
E(x) = [1-(1/(2^x))] * (E(x)+1) + [1/(2^x)] * (E(x-1)+1)

Also E(0) = 0 , because expected number of tosses to get 0 heads is zero, duh

now,

E(1) = (1-0.5) * (E(1)+1) + (0.5) * (E(0)+1) => E(1) = 2

E(2) = (1-0.125) * (E(1)+1) + (0.125) * (E(1)+1) => E(2) = 6

Similarly,

E(3) = 14

E(4) = 30

E(5) = 62

$\endgroup$
1
$\begingroup$

I would simplify the problem as follows:

Let $e$ = Expected number of flips until $5$ consecutive $H$, i.e., $E[5H]$
Let $f$ = Expected number of flips until $5$ consecutive $H$ when we have seen one $H$, i.e., $E[5H|H]$
Let $g$ = Expected number of flips until $5$ consecutive $H$ when we have seen two $H$, i.e., $E[5H|2H]$
Let $h$ = Expected number of flips until $5$ consecutive $H$ when we have seen three $H$, i.e., $E[5H|3H]$
Let $i$ = Expected number of flips until $5$ consecutive $H$ when we have seen four $H$, i.e., $E[5H|4H]$

Now Start flipping coin, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ then expected number of flips until 5 consecutive $H$ is $(f+1)$. Alternatively if $T$, we wasted 1 flip and expected number is still $(e+1)$ $$ e=\frac12(e+1)+\frac12(f+1)\; $$

We now need $f$ to solve above to get $e$. Now we start with 1 $H$ and seeking 4 more $H$ to get total 5 $H$. Again, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $2H$ so far) then expected number of flips until 5 consecutive $H$ is $(g+1)$. Alternatively if $T$, we wasted this flip and expected number is back to $(e+1)$

$$ f=\frac12(g+1)+\frac12(e+1)\; $$

Continuing this way... $$ g=\frac12(h+1)+\frac12(e+1)\; $$ $$ h=\frac12(i+1)+\frac12(e+1)\; $$

Finally, Now we have 4 $H$ and seeking last $H$ to get total 5 $H$. Still, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $5H$) then we need just $1$ flip. Alternatively if $T$ is observed, we wasted this flip and expected number is back to $(e+1)$ $$ i=\frac12(1)+\frac12(e+1)\; $$

Solving these equations, $e=62$, $f=60$, $g=56$, $h=48$, $i=32$
This solution offers some insight into conditional expectations of number of flips needed till 5 consecutive $H$ given 1, 2, 3 and 4 consecutive $H$.

$\endgroup$
1
$\begingroup$

No one else seems to have suggested the following approach. Suppose we keep flipping a coin until we get five heads in a row. Define a "run" as either five consecutive heads or a tails flip plus the preceding streak of heads flips. (A run could be a single tails flip.) The number of coin flips is equal to the number of runs with at least four heads ($R_{4+}$), plus the number of runs with at least three heads ($R_{3+}$), and so on down to the number of runs with at least zero heads ($R_{0+}$). We can see this by expanding the terms:

$R_{0+}$ = # runs with 0 heads + # runs with 1 head + ... + # runs with 5 heads

$R_{1+}$ = # runs with 1 head + # runs with 2 heads + ... + # runs with 5 heads

...

$R_{4+}$ = # runs with 4 heads + # runs with 5 heads

# flips = # flips in runs with 0 heads + # flips in runs with 1 head + ... + # flips in runs with 5 heads

# flips in runs with 0 heads = # runs with 0 heads

# flips in runs with 1 head = 2 x # runs with 1 head

...

# flips in runs with 4 heads = 5 x # runs with 4 heads

# flips in runs with 5 heads = 5 x # runs with 5 heads

By linearity of expectation, the expected number of coin flips is $E(R_{0+}) + E(R_{1+}) + \ldots + E(R_{4+})$. $E(R_{4+})$ is $2 E(R_{5+}) = 2$, because one half of the time we flip at least four heads in a row, we go on to flip five heads in a row, i.e. the following coin flip is heads. In other words, in expectation, it takes two runs that start with four heads to achieve one run of five heads. Likewise, $E(R_{3+}) = 2 E(R_{4+}) = 4$, $E(R_{2+}) = 2 E(R_{3+}) = 8$, $E(R_{1+}) = 2 E(R_{2+}) = 16$, and $E(R_{0+}) = 2 E(R_{1+}) = 32$. The expected number of coin flips is $32 + 16 + 8 + 4 + 2 = 62$.

More generally, given a biased coin that comes up heads $p$ portion of the time, the expected number of flips to get $n$ heads in a row is $\frac{1}{p} + \frac{1}{p^2} + \ldots + \frac{1}{p^n} = \frac{1 - p^n}{p^n(1 - p)}$.

$\endgroup$
0
$\begingroup$

A recursive programming solution is also possible. Below is the solution in Python

# Expected number of tosses to get n heads
def Expectation(n):
    if n == 0:
        return 0

    return 2**n + Expectation(n-1)

>>> Expectation(1)
2
>>> Expectation(2)
6
>>> Expectation(3)
14
>>> Expectation(5)
62
>>> Expectation(10)
2046
$\endgroup$
0
$\begingroup$

Here is an answer that uses martingale. We think in terms of a game: at every time step we toss a coin, you can bet any amount $x$; if the coin toss comes up head, you gain $x$, otherwise you lose $x$. Now let's construct a strategy such as if the $n$th coin toss is tail, then you position (cumulative gain) will be $-n$. So clearly, we should bet 1 on the first toss. If we get a tail, our position is -1, and we will bet 1 again; if we get a head, our position is 1, and we should bet 3 next, since we want to get to -2 if the second toss is a tail. How much should we bet after 2 heads in a row? Let's say the next toss is the $k+1$th toss, then $k-2$th toss was a tail, and by our strategy, our position after $k-2$th toss was $-(k-2)$; after that we bet 1, a head showed up, and then we bet 3, again a head, so our position now is $-(k-2)+4=-k+6$. We want to get to $-(k+1)=-k-1$, so we should bet 7 on the $k+1$th toss. By the same reasoning, we should bet 15 after the third head in a row, and 31 after the fourth head in a row. Since the up and down are symmetric, our position $X$ is a martingale. Let $\tau$ be the first time we have 5 consecutive heads. $\tau$ has finite expectation, so by optional sampling theorem, $X$ stopped at $\tau$ is also a martingale. What is our position at $\tau$? According to our strategy, our position will be $-(\tau-5)+1+3+7+15+31=-\tau+62$. Since our position stopped at $\tau$ is a martingale, and our position starts at 0, this means $$\mathbb{E}[-\tau+62]=0$$ and $$\mathbb{E}[\tau]=62$$

$\endgroup$
-2
$\begingroup$

The question is ambiguous. A simple thought experiment renders some interesting notions. We are told the coin is a fair coin but not told how the coin is flipped. We assume a fair flip or toss as well but not told. We know a fair coin renders a 50% exact chance of the coin landing on either side. A fair coin must of been proven to be a fair coin. To prove a coin is fair we must check the coin is fair. A process known as a Bernoulli process can be used to prove a coins fairness. However this also assumes the toss is random not really fair. Also we must check whether the flip is fair. The coin could be flipped unfairly and render a much different result then expected formulas and equations might suggest. If the coin used is proven fair and flipped unfairly we could have the coin land all heads every toss and the expected answer would be 5 or all tails and the expected answer is infinity. With a provably fair coin and fair toss the expectation of fairness is that each toss renders a different answer than the previous toss ensuring fairness and the expectation would be infinity as well. If we assume a fair coin and random toss then the expectation would be above a number with probabilities and odds not necessarily just a single answer. The probability of the fair coin being randomly tossed hitting five heads in a row tends to a probable expectation of occurrence as the number of tosses tends to infinity. A reasonable expectation is something different. This is where the probability and odds of occurrence is high enough to assume it is likely to occur once. This is where the other answers can come in but none suggest what the probability or odds of the expectation being correct is. For an example of the probability and odds of the occurrence of at least once let us look at 10 tosses. Each toss could land either way. We could look at all possible permutations of tosses as a start. We consider the number of options or outcomes of each flip being 2 either heads or tails and the number of places to apply those flips being 10 tosses occur. To determine how many total possible outcomes we use the permutations formula for a ordered set with repetition which is n^r. This formula is developed by the number of options n and the number of times we consider those options r or n x n r times or n^r. n = 2 in this example and r = 10 or 2^10 = 1024. We next look at all situations where 5 heads can occur in a row. Let 0 be tails and 1 be heads. 1111111111 is an option 1111100000 is an option too an so on. To determine how many of the 1024 would be 5 in a row we look at each type of situation. Situation type one is where 5 in a row and all others are tails. Next is where 5 are heads in a row 4 tails and 1 additional is heads. Next is 5 heads in a row 3 tails and 2 additional heads. Next 5 heads 2 tails and 3 additional heads. Next is 5 heads 1 tails and 4 heads. Finally all heads.

1 [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 2 [0, 0, 0, 0, 1, 1, 1, 1, 1, 0] 3 [0, 0, 0, 0, 1, 1, 1, 1, 1, 1] 4 [0, 0, 0, 1, 0, 1, 1, 1, 1, 1] 5 [0, 0, 0, 1, 1, 1, 1, 1, 0, 0] 6 [0, 0, 0, 1, 1, 1, 1, 1, 0, 1] 7 [0, 0, 0, 1, 1, 1, 1, 1, 1, 0] 8 [0, 0, 0, 1, 1, 1, 1, 1, 1, 1] 9 [0, 0, 1, 0, 0, 1, 1, 1, 1, 1] 10 [0, 0, 1, 0, 1, 1, 1, 1, 1, 0] 11 [0, 0, 1, 0, 1, 1, 1, 1, 1, 1] 12 [0, 0, 1, 1, 0, 1, 1, 1, 1, 1] 13 [0, 0, 1, 1, 1, 1, 1, 0, 0, 0] 14 [0, 0, 1, 1, 1, 1, 1, 0, 0, 1] 15 [0, 0, 1, 1, 1, 1, 1, 0, 1, 0] 16 [0, 0, 1, 1, 1, 1, 1, 0, 1, 1] 17 [0, 0, 1, 1, 1, 1, 1, 1, 0, 0] 18 [0, 0, 1, 1, 1, 1, 1, 1, 0, 1] 19 [0, 0, 1, 1, 1, 1, 1, 1, 1, 0] 20 [0, 0, 1, 1, 1, 1, 1, 1, 1, 1] 21 [0, 1, 0, 0, 0, 1, 1, 1, 1, 1] 22 [0, 1, 0, 0, 1, 1, 1, 1, 1, 0] 23 [0, 1, 0, 0, 1, 1, 1, 1, 1, 1] 24 [0, 1, 0, 1, 0, 1, 1, 1, 1, 1] 25 [0, 1, 0, 1, 1, 1, 1, 1, 0, 0] 26 [0, 1, 0, 1, 1, 1, 1, 1, 0, 1] 27 [0, 1, 0, 1, 1, 1, 1, 1, 1, 0] 28 [0, 1, 0, 1, 1, 1, 1, 1, 1, 1] 29 [0, 1, 1, 0, 0, 1, 1, 1, 1, 1] 30 [0, 1, 1, 0, 1, 1, 1, 1, 1, 0] 31 [0, 1, 1, 0, 1, 1, 1, 1, 1, 1] 32 [0, 1, 1, 1, 0, 1, 1, 1, 1, 1] 33 [0, 1, 1, 1, 1, 1, 0, 0, 0, 0] 34 [0, 1, 1, 1, 1, 1, 0, 0, 0, 1] 35 [0, 1, 1, 1, 1, 1, 0, 0, 1, 0] 36 [0, 1, 1, 1, 1, 1, 0, 0, 1, 1] 37 [0, 1, 1, 1, 1, 1, 0, 1, 0, 0] 38 [0, 1, 1, 1, 1, 1, 0, 1, 0, 1] 39 [0, 1, 1, 1, 1, 1, 0, 1, 1, 0] 40 [0, 1, 1, 1, 1, 1, 0, 1, 1, 1] 41 [0, 1, 1, 1, 1, 1, 1, 0, 0, 0] 42 [0, 1, 1, 1, 1, 1, 1, 0, 0, 1] 43 [0, 1, 1, 1, 1, 1, 1, 0, 1, 0] 44 [0, 1, 1, 1, 1, 1, 1, 0, 1, 1] 45 [0, 1, 1, 1, 1, 1, 1, 1, 0, 0] 46 [0, 1, 1, 1, 1, 1, 1, 1, 0, 1] 47 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0] 48 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 49 [1, 0, 0, 0, 0, 1, 1, 1, 1, 1] 50 [1, 0, 0, 0, 1, 1, 1, 1, 1, 0] 51 [1, 0, 0, 0, 1, 1, 1, 1, 1, 1] 52 [1, 0, 0, 1, 0, 1, 1, 1, 1, 1] 53 [1, 0, 0, 1, 1, 1, 1, 1, 0, 0] 54 [1, 0, 0, 1, 1, 1, 1, 1, 0, 1] 55 [1, 0, 0, 1, 1, 1, 1, 1, 1, 0] 56 [1, 0, 0, 1, 1, 1, 1, 1, 1, 1] 57 [1, 0, 1, 0, 0, 1, 1, 1, 1, 1] 58 [1, 0, 1, 0, 1, 1, 1, 1, 1, 0] 59 [1, 0, 1, 0, 1, 1, 1, 1, 1, 1] 60 [1, 0, 1, 1, 0, 1, 1, 1, 1, 1] 61 [1, 0, 1, 1, 1, 1, 1, 0, 0, 0] 62 [1, 0, 1, 1, 1, 1, 1, 0, 0, 1] 63 [1, 0, 1, 1, 1, 1, 1, 0, 1, 0] 64 [1, 0, 1, 1, 1, 1, 1, 0, 1, 1] 65 [1, 0, 1, 1, 1, 1, 1, 1, 0, 0] 66 [1, 0, 1, 1, 1, 1, 1, 1, 0, 1] 67 [1, 0, 1, 1, 1, 1, 1, 1, 1, 0] 68 [1, 0, 1, 1, 1, 1, 1, 1, 1, 1] 69 [1, 1, 0, 0, 0, 1, 1, 1, 1, 1] 70 [1, 1, 0, 0, 1, 1, 1, 1, 1, 0] 71 [1, 1, 0, 0, 1, 1, 1, 1, 1, 1] 72 [1, 1, 0, 1, 0, 1, 1, 1, 1, 1] 73 [1, 1, 0, 1, 1, 1, 1, 1, 0, 0] 74 [1, 1, 0, 1, 1, 1, 1, 1, 0, 1] 75 [1, 1, 0, 1, 1, 1, 1, 1, 1, 0] 76 [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] 77 [1, 1, 1, 0, 0, 1, 1, 1, 1, 1] 78 [1, 1, 1, 0, 1, 1, 1, 1, 1, 0] 79 [1, 1, 1, 0, 1, 1, 1, 1, 1, 1] 80 [1, 1, 1, 1, 0, 1, 1, 1, 1, 1] 81 [1, 1, 1, 1, 1, 0, 0, 0, 0, 0] 82 [1, 1, 1, 1, 1, 0, 0, 0, 0, 1] 83 [1, 1, 1, 1, 1, 0, 0, 0, 1, 0] 84 [1, 1, 1, 1, 1, 0, 0, 0, 1, 1] 85 [1, 1, 1, 1, 1, 0, 0, 1, 0, 0] 86 [1, 1, 1, 1, 1, 0, 0, 1, 0, 1] 87 [1, 1, 1, 1, 1, 0, 0, 1, 1, 0] 88 [1, 1, 1, 1, 1, 0, 0, 1, 1, 1] 89 [1, 1, 1, 1, 1, 0, 1, 0, 0, 0] 90 [1, 1, 1, 1, 1, 0, 1, 0, 0, 1] 91 [1, 1, 1, 1, 1, 0, 1, 0, 1, 0] 92 [1, 1, 1, 1, 1, 0, 1, 0, 1, 1] 93 [1, 1, 1, 1, 1, 0, 1, 1, 0, 0] 94 [1, 1, 1, 1, 1, 0, 1, 1, 0, 1] 95 [1, 1, 1, 1, 1, 0, 1, 1, 1, 0] 96 [1, 1, 1, 1, 1, 0, 1, 1, 1, 1] 97 [1, 1, 1, 1, 1, 1, 0, 0, 0, 0] 98 [1, 1, 1, 1, 1, 1, 0, 0, 0, 1] 99 [1, 1, 1, 1, 1, 1, 0, 0, 1, 0] 100 [1, 1, 1, 1, 1, 1, 0, 0, 1, 1] 101 [1, 1, 1, 1, 1, 1, 0, 1, 0, 0] 102 [1, 1, 1, 1, 1, 1, 0, 1, 0, 1] 103 [1, 1, 1, 1, 1, 1, 0, 1, 1, 0] 104 [1, 1, 1, 1, 1, 1, 0, 1, 1, 1] 105 [1, 1, 1, 1, 1, 1, 1, 0, 0, 0] 106 [1, 1, 1, 1, 1, 1, 1, 0, 0, 1] 107 [1, 1, 1, 1, 1, 1, 1, 0, 1, 0] 108 [1, 1, 1, 1, 1, 1, 1, 0, 1, 1] 109 [1, 1, 1, 1, 1, 1, 1, 1, 0, 0] 110 [1, 1, 1, 1, 1, 1, 1, 1, 0, 1] 111 [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] 112 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

1024 permutations 112 total with 5 in a row of 1 112 / 912 odds of 5 in a row 112 / 1024 probability of 1 in a row of 5 or 10.9375 % probability of getting 1 in a row of 5 912 total without 1 in a row of 5 912 / 112 odds of 1 never in a row of 5 912 / 1024 probability of 1 never in a row of 5 or 89.0625 % probability never in a row of 5

The python 2 code I wrote to calculate the list and print it and the total

inp = int(3) while inp != int(1) and inp != int(0) and inp != int(2): inp = int(input('warning lists grow very big very fast so use with caution! Enter 2 for complete list 1 for list meeting criteria and 0 for no list : Print list of permutations? ')) if inp == 1: p = 1 elif inp == 2: p = 2 else: p = 0 nin = 0 while nin <=0: nin = int(input('Enter number of options or characters to select between: ')) n = nin rin = 0 while rin <= 0: rin = int(input('Enter string length or number of places the options are applied: ')) r = rin woin = -1 while woin < 0 or woin >= n: woin = int(input('Enter the option number to appear in a row: ')) wo = woin noin=[] c=0 for i in range(n-1): if i != wo: noin.append(str(i)) c+=1 roin = 0 while roin <= 0: roin = int(input('Enter number of times option to appear in a row: ')) ro = roin a = 0 ra = n**r s = str(r) i = 0 def baseconv(t,v): if t <2: return oput=[] while v!=0: oput.insert(0,v%t) v = v/t if oput == []: oput.insert(0,0) return oput def padnum(s,z): if s == len(z): return z while len(z) < s: z.insert(0,0) return z while i < ra: y=baseconv(n,i) y=padnum(r,y) if p == 2: print i+1, print y z = 0 for x in range(len(y)): if y[x] == wo: z += 1 if z >= ro: a += 1 if p == 1: print a, print y break elif z<ro: z = 0 i += 1 f=ra-a print
print ra, print 'permutations' print a, print 'total with', print ro, print 'in a row of', print wo print a, print '/', print f, print 'odds of', print ro, print 'in a row' print a, print '/', print ra print 'probability of', print wo, print 'in a row of', print ro print 'or' print float(float(a)/float(ra))*float(100), print '% probability of getting', print wo, print 'in a row of', print ro

print f, print 'total without', print wo, print 'in a row of', print ro

print f, print '/', print a, print 'odds of', print wo, print 'never in a row of', print ro

print f, print '/', print ra print 'probability of', print wo, print 'never in a row of', print ro print 'or' print float(float(f)/float(ra))*float(100), print '% probability never in a row of ', print ro

We then take the number of possible answers that render the correct result of 5 heads in a row and divide by the total number of permutations. At 20 tosses:

1048576 permutations 262008 total with 5 in a row of 1 262008 / 786568 odds of 5 in a row 262008 / 1048576 probability of 1 in a row of 5 or 24.9870300293 % probability of getting 1 in a row of 5 786568 total without 1 in a row of 5 786568 / 262008 odds of 1 never in a row of 5 786568 / 1048576 probability of 1 never in a row of 5 or 75.0129699707 % probability never in a row of 5

At 25 tosses :
33554432 permutations 10455246 total with 5 in a row of 1 10455246 / 23099186 odds of 5 in a row 10455246 / 33554432 probability of 1 in a row of 5 or 31.1590611935 % probability of getting 1 in a row of 5 23099186 total without 1 in a row of 5 23099186 / 10455246 odds of 1 never in a row of 5 23099186 / 33554432 probability of 1 never in a row of 5 or 68.8409388065 % probability never in a row of 5

At 30 tosses :

1073741824 permutations 395386763 total with 5 in a row of 1 395386763 / 678355061 odds of 5 in a row 395386763 / 1073741824 probability of 1 in a row of 5 or 36.8232618086 % probability of getting 1 in a row of 5 678355061 total without 1 in a row of 5 678355061 / 395386763 odds of 1 never in a row of 5 678355061 / 1073741824 probablity of 1 never in a row of 5 or 63.1767381914 % probability of 1 never in a row of 5

At 40 the list is 1,099,511,627,776 and I might update when the program completes.

The probability at 30 tosses is greater than playing roulette on the thirds options and that would be a reasonable expectation of success according to gambling probability.

The list grows very large very fast but anyways hope this helps.

$\endgroup$
-3
$\begingroup$

Expectation for getting n consecutive heads is : 2*(2^n-1). Thus for 5 heads it is = 62.

$\endgroup$
1
  • 9
    $\begingroup$ How did you get the formula? $\endgroup$
    – hola
    May 11 '15 at 18:25
-4
$\begingroup$

By conclusion and some other mathmatical proof. To get consecutive n heads or tails expected number is $2^n+1 -2$.

So, here answer is $2^6- 2 =62$.

$\endgroup$
1
  • 1
    $\begingroup$ I do not understand the first sentence. Also, this is essentially identical to this answer (plugging in numbers to a known formula). $\endgroup$
    – user1729
    Dec 11 '19 at 11:05

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.