A coin that lands on heads with probability $p$ is flipped until either $n$ consecutive heads appear or $n$ consecutive tails appear. What is the expected number of coin tosses?
I get
$$\mathbb{E}[C_n]=\mathbb{E}[\mathbb{E}[C_n|H]]=\mathbb{E}[C_n|H=1]\mathbb{P}(H=1)+\mathbb{E}[C_n|H=0](1-\mathbb{P}(H=1))$$
Where
$C_n$ is the number of flips until we get either $n$ consecutive heads or $n$ consecutive tails. $H=1$ iff we get $n$ consecutive heads before $n$ consecutive tails and is zero otherwise.
$$\mathbb{E}[C_n|H=1]=\frac {p^{-n}-1}{1-p}$$
$$\mathbb{E}[C_n|H=0]=\frac {(1-p)^{-n}-1}{p}$$
$$\mathbb{P}(H=1)=\frac{p^{n}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}+(1-p)p^{n-1}\frac{1-(1-p)^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$
As an answer, but, when trying to compute this value when $p=1$, which better be $n$, it is $2n$. what is wrong with the formula?
PS:
The way I got the terms is as follows:
If the first flip is tails, then the conditional expected value is $1+\mathbb{E}[C_n|H=1]$, if the first flip is heads and the second tails, the conditional expected value is $2+\mathbb{E}[C_n|H=1]$, if …, thus
$$\mathbb{E}[C_n|H=1]=\sum_{k=0}^{n-1}p^k(1-p)(1+k+\mathbb{E}[C_n|H=1])$$
Solving for $\mathbb{E}[C_n|H=1]$ gives
$$\mathbb{E}[C_n|H=1]=\frac{p^{-n}-1}{1-p}$$
Likewise for $\mathbb{E}[C_n|H=0]$ except that the probabilities are now inverted, thus:
$$\mathbb{E}[C_n|H=0]=\frac{(1-p)^{-n}-1}{p}$$
To compute $\mathbb{P}(H=1)$ we condition on whether the first flip is a head. Here, we have two possibilities, either the following $n-1$ flips are heads, or one of these $n-1$ flips results in tails, at which point we forget about all previous heads and imagine that our first flip is a tail, thus
$$P=\mathbb{P}(H=1|\text{first flip is heads})=p^{n-1}+(1-p^{n-1})\mathbb{P}(H=1|\text{first flip is tails})$$
To compute $\mathbb{P}(H=1|\text{first flip is tails})$, we have two possibilities again: either the following $n-1$ flips are all tails, in which case the probability of obtaining $n$ consecutive heads before $n$ consecutive tails is zero, or somewhere along the line we get a head, in which case we start all over again as if though our first flip had been a head. Thus
$$Q=\mathbb{P}(H=1|\text{first flip is tails})=(1-(1-p)^{n-1})\mathbb{P}(H=1|\text{first flip is heads})$$
We now have the simultaneous equations
$$\begin{align} P&=p^{n-1}+(1-p^{n-1})Q \\ Q &=(1-(1-p)^{n-1})P\end{align}$$
Which implies that $$P=\frac{p^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$
$$Q=\frac{p^{n-1}(1-(1-p)^{n-1})}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$
Remembering we had conditioned on the first flip, we now get
$$\mathbb{P}(H=1)=\frac{p^{n}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}+(1-p)p^{n-1}\frac{1-(1-p)^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$
Solved – When can I expect to get 5 heads in a row when tossing a coin
expected valueprobability
Related Solutions
This is a computational exercise, so think recursively. The current state of coin flipping is determined by the ordered pair $(N,M)$ with $N\ge M\ge 0$. Let the expected number of flips to reach $N$ consecutive heads be $e(N,M)$:
(1) There is a 50% chance the next flip will be heads, taking you to the state $(N,M+1)$, and a 50% chance the next flip will be tails, taking you to the state $(N,0)$. This costs one flip. Therefore the expectation (recursively) is given by
$$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$$
(2) Base conditions: you have already stipulated that
$$e(N,0) = 2^{N+1}-2$$
and obviously
$$e(N,N) = 0$$
(no more flips are needed).
Here's the corresponding Mathematica program (including caching of intermediate results to speed up the recursion, which effectively makes it a dynamic programming solution):
e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0
The program would look similar in other programming languages that support recursion. Mathematically, we can verify that $e(N,M) = 2^{N+1} - 2^{M+1}$ simply by checking the recursion, because it obviously holds for the base cases:
$$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$$
which is true for any $M$ and $N$, QED.
More generally, the same approach will establish that $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ when the coin has probability $p$ of heads. The hard part is working out the base condition $e(N,0)$. That is done by chasing the recursion out $N$ steps until finally $e(N,0)$ is expressed in terms of itself and solving:
$$\eqalign{ e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\ &= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ &= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$$
I am sure there are many ways to analyze this situation, but the following one is appealing for its simplicity and use of only the most basic properties of probability. Assuming ties for heads cause the game to continue until a result is uniquely determined, it shows the chance of a player winning the game is her relative odds: the proportion of her odds of heads, divided by the sum of the odds of heads among all players. The game length obviously has a geometric distribution. Its parameter is proportional to this sum of odds. The constant of proportionality is the product of all the chances of tails.
Other methods of resolving ties (to create a definite winner) can be analyzed in a similar way, starting with computing the chance that a given player will win a particular round and continuing as shown here.
Let there be $m$ players, each using a coin with probability $p_i$ of heads. Let $i,j,\ldots, k$ be any permutation of $(1,2,\ldots,m)$.
Suppose that when a tie occurs, no outcome is declared and play continues. Then the chance that player $i$ wins is the chance that she is the sole person to toss heads, equal to
$$p_i(1-p_j)\ldots(1-p_k) = \frac{p_i}{1-p_i}\prod_{l=1}^m (1-p_l) = \pi_i Q$$
where I have written $\pi_i = p_i/(1-p_i)$ for player $i$'s odds of heads and $Q$ for the product of all $1-p_l$ (the chance that everybody simultaneously observes a tail).
If no player wins a round, the game starts over, with exactly the same probabilities. Therefore the chance that player $i$ wins the entire game is the chance they can win a given round, divided by the sum of all players' chances to win the round:
$$\Pr(i\text{ wins}) = \frac{\pi_i Q}{\sum_{l=1}^m \pi_l Q} = \frac{\pi_i}{\sum_{l=1}^m \pi_l} = \frac{\pi_i}{\pi}.$$
It is their proportion of the total odds $\pi$.
The chance that the game ends on any particular round is the chance that exactly one player observes heads, equal to
$$\sum_{l=1}^m \pi_l Q = \pi Q.$$
Thus the length of the game has a geometric distribution with parameter $\pi Q$.
This result is supported by simulation:
It was carried out with this R script, which can simulate and summarize tens of millions of tosses per second for arbitrarily many players (up to limits determined by RAM).
coins <- log(2:10); coins <- coins / sum(coins)
n.players <- length(coins)
n.rounds <- 1e6
#
# Simulate many rounds.
#
system.time({
tosses <- matrix(runif(n.rounds * n.players), nrow=n.players) < coins
wins <- colSums(tosses) == 1
winners <- colSums(1:n.players * tosses) * wins
(results <- tabulate(winners[winners != 0], n.players))
})
#
# Compare to theory.
#
odds <- coins / (1-coins)
p <- odds / sum(odds)
rbind(Simulation=results / sum(results), Theory=p)
#
# Display the distribution of game lengths compared to the geometric distribution.
#
lengths <- diff(c(0, which(wins==TRUE)))
Q <- prod(1 - coins)
pQ <- sum(odds) * Q
n.max <- ceiling((log(.002) + log(pQ)) / log(1-pQ)) # Plotting limit
prob.geometric <- (1 - pQ)^(1:n.max - 1) * pQ
subtitle <- paste(sum(results),"games played with coins",
paste(round(coins, 2), collapse=","))
hist(lengths[lengths < n.max], freq=FALSE, breaks=(1:n.max)-1/2,
main="Simulation (bars) vs. Theory (lines)",
xlab="Game lengths",
sub=subtitle)
invisible(sapply(1:n.max, function(i) {
lines(c(i,i), c(0, prob.geometric[i]), lwd=2, col="Red")
}))
Best Answer
I couldn't follow your derivation, but I believe the correct way to solve the problem is as follows.
First, some notation: take $x_i$ to be the expected number of flips to reach the end state ($n$ consecutive heads or $n$ consecutive tails), given that we're on a "run" of exactly $i$ consecutive flips of heads. Similarly, take $y_i$ to be the expected number of flips to reach the end state, given that we're on a run of exactly $i$ consecutive flips of tails. Clearly, $x_n = y_n = 0$, since if we've already had $n$ consecutive heads or tails, we're done.
Then, we're interested in finding $x_0$ ($= y_0$). The relevant equations are (for $i < n$):
\begin{equation} \begin{split} x_i & = (1-p)(1 + y_1) + p(1 + x_{i+1}) \\ y_i & = p(1 + x_1) + (1-p)(1 + y_{i+1}) \end{split} \end{equation}
Let's derive the first equation (the second one is analogous). Suppose we're on a run of $i$ heads. We want to find the expected number of flips to end the game, which is $x_i$. Let's take our next flip. There's a probability $p$ that it comes up heads, which means we now have a run of $i+1$ heads. That's the second term on the right-hand-side of the equation: there's a probability of $p$ of moving from the state with $i$ consecutive heads to the state with $i+1$ consecutive heads, and it costs 1 flip in order to do so. There's also a probability $1-p$ that it comes up tails, in which case we have a run of only 1 tail. That's the first term on the right-hand-side of the equation: there's a probability of $1-p$ of moving from the state with $i$ consecutive heads to the state with 1 consecutive tail, and it costs us 1 flip in order to do so.
With these equations you can solve the problem for any $n$. I tried implementing this in Mathematica, and if $p = 0$ or $p = 1$, I indeed get that $x_0 = y_0 = n$, as expected.
I'm not sure if there's any closed form solution to the equations for arbitrary $n$; that's probably a question for the Math StackExchange.(Edit: see derivation below for the solution for arbitrary $n$).What I've sketched out here is a general approach for solving many types of coin flipping problems (and other problems). It essentially constructs a Markov chain that has states (e.g., 3 consecutive heads), and transition probabilities for moving between states (e.g., a probability of $1-p$ of moving from 3 consecutive heads to 1 tail). The absorbing states are the end states of the game. See, for instance, the answer to this question.
EDIT: For the particular case of $n=5$, I get (using Mathematica):
\begin{equation} x_0 = \frac{(5 - 10p + 10p^2 - 5p^3 + p^4)(1 + p + p^2 + p^3 + p^4)}{1 - 4p + 6p^2 - 4p^3 + p^4 + 4p^5 - 6p^6 + 4p^7 - p^8} \end{equation}
which seems to have the right limits (although it's possible I have a typo somewhere).
Edit #2: Following @whuber's advice, I solved the recurrence relation for general $n$. The solution is:
\begin{equation} \begin{bmatrix} x_0 \\ y_0 \end{bmatrix} = (A + B)[(I-A^{n-1})^{-1}(I-A)-B]^{-1}c + c \end{equation}
where \begin{equation} A = \begin{bmatrix} p & 0 \\ 0 & 1-p \end{bmatrix} \end{equation}
and
\begin{equation} B = \begin{bmatrix} 0 & 1-p \\ p & 0 \end{bmatrix} \end{equation}
and
\begin{equation} c = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{equation}
and $I$ is the identity matrix. For $n=5$, this gives the same result as above.