\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}