\documentclass[12pt]{article}
\title{Two Coin-Flipping Problems}
\author{Matt McCutchen}
\date{September 3, 2004}
% Page layout parameters
\pdfpagewidth 8.5in
\pdfpageheight 11in
\topmargin .1in
\textheight 9in
\textwidth 7.5in
\oddsidemargin -.5in
\evensidemargin -.5in
\headheight 0in
\headsep 0in
\parindent 0in
% Set the main font to sans-serif
\def\familydefault{\sfdefault}
\def\nCr#1#2{{\left( {{#1} \atop {#2}} \right)}}
\begin{document}
\maketitle
\parskip 0.13 in
As I was walking down the hall at school, Mr. Stein posed the following problem:
{\sl Someone flips a coin repeatedly. What is the probability that 3 heads occur before 8 tails?}
Unfortunately, this can be interpreted in two ways, and I neglected to ask which he intended.
{\bf Run version:} {\sl Someone flips a coin repeatedly. She stops when she gets either 3 heads
in a row or 8 tails in a row. What is the probablity that she gets 3 heads in a row?}
{\bf Total version:} {\sl Someone flips a coin repeatedly. She stops once she has flipped a total of 3 heads
or a total of 8 tails. What is the probablity that she gets the 3 heads?}
Fortunately, both versions can be solved without much difficulty.
\section*{Solution to the run version}
Consider the following problem:
{\sl Two players, A and B, take turns flipping a coin. A plays first. The first player to flip a head wins. What is the probability that A will win?}
This game could go on for any number of turns, so we must use a ``recursive'' approach. Let $p$ be the probability that A will win if it is the beginning of A's turn, and let $q$ be the probability that he will win if it is the beginning of B's turn.
When A takes a turn, the probability is $1/2$ that he will win immediately by flipping a head. If he does not win immediately, B's turn begins and he eventually wins with probability $q$. Therefore $p = 1/2 + (1/2)q$. When B's turn begins, the only way A can win is if B flips a tail; if this happens, A wins with probability $p$. We have shown that $q = (1/2)p$.
Solving these equations simultaneously yields $p = 2/3, q = 1/3$. A plays first, so his winning probability is $2/3$.
A similar technique will solve the run version of our problem. Let us replace the single coin-flipper by two players, H and T, who take turns flipping the coin. If H flips a head, she flips again; if she flips a tail, it becomes T's turn. The reverse is true for T.
If 3 heads occur in a row, we want H to win, and 8 tails should lead to a win for T. However, H need flip only 2 heads on her turn to win, because her turn began after T flipped a head and his turn ended. (We'll deal with the special case of the start of the game in a moment.) Similarly, T wins if he flips 7 tails in a row on his turn.
Let $p$ and $q$ be the winning probabilities for H at the beginning of her turn and T's turn, respectively. The rules above give us $p = 1/4 + (3/4)q$ and $q = (127/128)p$. The solution is $p = 128/131, q = 127/131$.
Our analysis is almost complete, but one thing is missing. How does the game begin? If we just awarded the first turn to H, for example, she could win with a run of only 2 heads. The correct procedure is to have someone flip a coin to determine who plays first. If the flip is heads, H plays, and if she flips 2 more consecutive heads, she has won with a run of 3 heads. This works. To find H's overall winning probability, we must average $p$ and $q$, because either player goes first with probability $1/2$. This comes to $255/262$. T wins with probability $7/262$.
In the general case where H needs a run of $h$ heads and T needs a run of $t$ tails, we get $p = 1/{2^{h-1}} + (1 - 1/{2^{h-1}})q$ and $q = (1 - 1/{2^{t-1}})p$, and the solution is $$p = \frac{2^t}{2^t+2^h-2}, q = \frac{2^t - 2}{2^t+2^h-2}.$$ H wins with probability $$\frac{2^t - 1}{2^t+2^h-2}.$$
\section*{Solution to the total version}
One could solve this version of the problem by working backwards and finding the probability for each $h$ and $t$ that H will eventually win if $h$ heads and $t$ tails have been flipped so far.
However, there's a secret. Suppose H and T agree beforehand that they will flip the coin 10 times no matter what and determine the winner after the fact. Someone must win, because at most 9 flips (2 heads and 7 tails) can occur without a winner. Moreover, it is impossible for both players to have at least their winning total of flips, because this would require 11 flips. Therefore, H wins the game if and only if the 10 flips contain at least 3 heads, and T wins if and only if there are at least 8 tails. The probability of $k$ heads in $n$ flips is just $\nCr{n}{k}/2^n$, so H wins with probability $$\left( \sum_{i=3}^{10} \nCr{10}{n} \right) \Big/ 2^{10}.$$
The argument above can be generalized to the case where H needs $h$ flips to win and T needs $t$ flips. H's probability of winning is then $$\left( \sum_{i=h}^{h+t-1} \nCr{h+t-1}{i} \right) \Big/ 2^{h+t-1}.$$ This can be evaluated on a TI-83 Plus as {\tt 1-binomcdf(h+t-1,1/2,t-1)}.
\medskip
\centerline{* * * * *}
\centerline{Beautiful typesetting courtesy of \LaTeX.}
\end{document}