How do I rigorously compute probabilities over infinite sequences of coin flips?

Question

Problem Statement: Two players take turns flipping a fair coin. The first player to get heads wins the game. What is the probability that the player taking the first turn will win the game?

Analysis: Let $x$ be the probability that the next player to flip the coin will win the game. Then $x$ satisfies the equation:

$$x=\frac12\times1+\frac12\times(1-x)$$

since $\frac12$ of the time the player gets heads and wins the game immediately, and $\frac12$ of the time the player gets tails and the opponent has a probability of $1 - x$ of losing the game. The only solution to the equation is $x = \frac23$, and hence the probability that the player taking the first turn will win the game is $\frac23$. I have also verified this result empirically.

Question: Which tools can I use to solve the above and similar problems methodically and rigorously? The main issue I have with the approach above is that:

1. I don't know how to methodically produce such equations, and hence for more complicated scenarios I have a low level of certainty that they are correct, and
2. the method as stated above seems unsound. The fact that the answer satisfies an equation does not immediately imply that a solution to the equation is the answer. In particular, for more complicated scenarios I sometimes get equations which have several solutions and have to resort to simulation to find which one is the right answer.

Thank you!

Answer 1

You are correct in thinking that the method you describe isn't strictly rigorous. To make it rigorous, you need to argue that the desired probability actually exists.

To see the problem, just look at divergent Geometric series. If, say, $S$ denotes the "sum" of $\sum 2^n$ then it is easy to see that $2S=S-1$, so $S=-1$. But of course the series diverges so this formal computation doesn't compute the sum in any traditional sense.

In your case, one can, for example, truncate the question. Letting $p_n$ denote the probability that the first player wins on the $n^{th}$ turn. That exists, clearly, and you can easily show that $p_n\to 0$ and that $\sum p_n$ converges. The limit of that sum is $p$, by definition. In the same spirit, you can solve the given problem precisely by writing $p$ as a Geometric Series. In variants of this question, with players moving between many active states, exact formulations are typically not available (or are too messy to use sensibly).

To be sure, this sort of argument is frequently used without taking the extra step of demonstrating existence. It's fairly safe to do that in cases where it is clear that the "infinite" game in question will actually end very rapidly with probability approaching $1$.

Answer 2

You can indeed solve the problem using the sum of geometric series, which might be a more practical way of approaching this problem. Let $A_{n}$ denote the probability of the player who has the first turn to win on his $n$-th turn. Let $B_{n}$ denote the probability of the second player winning on his $n$-th turn. Then:

$$ A_{n} = \frac{1}{2^{2n-1}}$$

This is a geometric progression with the first member $a_{1} = \frac{1}{2}$, and common ratio $q = \frac{1}{4}$.

$$ B_{n} = \frac{1}{2^{2n}} $$ And this is a geometric progression with the first member $b_{1}=\frac{1}{4}$ and common ratio $q=\frac{1}{4}$.

The probability of player $A$ winning the game is given by the sum:$$ \sum_{i=1}^{\infty}A_{i}=\frac{\frac{1}{2}}{1-\frac{1}{4}}=\frac{2}{3} $$ And the probability of player B winning the game is given by the sum: $$\sum_{i=1}^{\infty}B_{i}=\frac{\frac{1}{4}}{1-\frac{1}{4}}=\frac{1}{3}$$ We can therefore conclude the player $A$ will win $2/3$ of all games, and the player $B$ will win $1/3$ of all games. As you have pointed out this can be easily verified empirically. Note, that it is possible to extended this approach to arbitrary number of players. :)

Answer 3

You can define this problem as an absorbing Markov chain with the following transition matrix:

$$ \begin{array}{c|ccc} & \text{S1} & \text{S2} & \text{W} \\ \hline \text{S1} & 0 & 1-p & p \\ \text{S2} & 1-p & 0 & p \\ \text{W} & 0 & 0 & 1 \\ \end{array} $$

Where $S1$ and $S2$ are states representing the two players' turns, $W$ is the absorbing state representing a win, $p$ is the probability of winning (0.5 in the case of a fair coin), and $1-p$ is the probability of moving to the next player's turn.

Let's call this transition matrix $P$, which can be generalized as:

$$ P = \begin{bmatrix} Q & R \\ 0 & I \end{bmatrix} $$

Where $Q$ is a square submatrix containing the transition states, and $R$ is a submatrix containing the absorbing states.

An important component of many absorbing Markov chain calculations is the fundamental matrix:

$$ F=(I-Q)^{-1} $$

Which tells you the expected number of times each state will be visited given the state that you started in.

$$ F = \begin{bmatrix} 4/3 & 2/3 \\ 2/3 & 4/3 \end{bmatrix} $$

So, for example, the top right value means that if you start in state $S1$ (the top row), you expect to visit state $S2$ (second column) $2/3$ times.

To get to what you want (probability of winning), you then do:

$$ B = F \tilde{R} $$

Where $\tilde{R}$ is a square matrix where the diagonal is the row sums of $R$. The result is:

$$ B = \begin{bmatrix} 4/3 & 2/3 \\ 2/3 & 4/3 \end{bmatrix} \begin{bmatrix} 1/2 & 0 \\ 0 & 1/2 \end{bmatrix} $$

$$ B = \begin{bmatrix} 2/3 & 1/3 \\ 1/3 & 2/3 \end{bmatrix} $$

The first row is the probability each player wins if S1 starts, and the second row is the probability each player wins if S2 starts.

The book "Finite Markov Chains" by Kemeny and Snell goes into a lot of detail describing many different types of calculations you can apply to absorbing Markov chains, including the ones used here. I believe the book is available online for free (legally). For a quick lookup, there's a brief description of many of them (not all) in the overview of my software package for working with absorbing Markov chains: https://andrewmarx.github.io/samc/articles/overview.html#analytical-functions (the wording is geared towards ecologists, but it's all generalizable)

Answer 4

Here is my attempt at rigorously justifying the equation $x=\frac12\cdot 1+\frac12\cdot (1-x)$, where $x$ is the probability that player one wins.

For each $n\ge 1$, let $H_n$ be a random variable which is equal to $1$ if the $n^{\text{th}}$ flip is heads, and zero otherwise. Let $T_n$ denote the indicator random variable for the $n^\text{th}$ flip being tails. This means $H_n+T_n=1$.

I claim that $$ 1=H_1+T_1H_2+T_1T_2H_3+T_1T_2T_3H_4+\dots \tag 1 $$ This is equivalent to the statement that if you flip a coin infinitely many times, then you will eventually get heads for the first time on some flip. In this asnwer, I will take $(1)$ as an axiom, and use that to prove $x=\frac12 \cdot 1+\frac12\cdot (1-x)$. I think that $(1)$ is a more basic question then what you are confused about.

Let $X$ be the random variable which is equal to $1$ if player one wins, and zero otherwise. In terms of the indicator variables $(H_n)_{n\ge 1}$ and $(T_n)_{n\ge 1}$, $$ X=H_1+T_1T_2H_3+T_1T_2T_3T_4H_5+\dots \tag2 $$ We now reason as follows: $$ \begin{align} X&= H_1+ T_1\big(T_2H_3+T_2T_3T_4H_5+\dots\big) \\&= H_1+ T_1\left( \begin{array}{cl} &\big(\color{blue}{H_2+T_2H_3+T_2T_3H_4+T_2T_3T_4T_5H_6+}\dots\big) \\ -&\big(H_2+\phantom{+T_2H_3+}T_2T_3H_4+\phantom{+T_2T_3T_4T_5H_6}\dots\big) \end{array}\right) \\&= H_1 + T_1\Big(\color{blue}1 -\big(H_2+T_2T_3H_4+T_2T_3T_4T_5H_6+\dots\big)\Big) \end{align}\tag3 $$ We are almost done. Define $$ X'={H_2+T_2T_3H_4+T_2T_3T_4T_5H_6+\dots},\tag4 $$ so we can rewrite $(4)$ as follows: $$ X=H_1+T_1\cdot (1-X').\tag5 $$ By comparing $(2)$ and $(4)$ carefully, it should be clear that $X$ and $X'$ are random variables with the same distribution. The idea is that $X$ is defined by a certain formula in terms of $H_1,T_1,H_2,T_2,\dots$, while $X'$ is the same formula applied to $H_2,T_2,H_3,T_3,\dots$, but these are infinite series of events with the same distribution. In particular, $\mathbb{E}[X]=\mathbb{E}[X']$.

Furthermore, by independence of the series of coin flips, it should be clear that $X'$ is independent of $T_1$. Therefore, if we take the expected value of both sides of $(5)$, we get $$ \begin{align} \mathbb E[X] &= \mathbb E[H_1]+\mathbb E[T_1]\cdot \mathbb E[1-X'] \\&=\tfrac12+\tfrac12\cdot (1-\mathbb E[X']) \end{align} $$ Finally, after noting that $\mathbb E[X]=\mathbb E[X']=x$, the above equation is exactly what we wanted to derive.

Answer 5

As your problem corresponds to an event in a properly-defined probability space (see below for a proof), your method is correct becuase you just used a simple formula involving conditional probabilities.

Consider the following general result in measure theory [1]:

Let $\{(E_t,\mathcal E_t,\Bbb P_t): t\in T\}$ be a non-empty collection of probability spaces indexed by some set $T$, then there is a unique probability measure $\Bbb P$ on the product space $$(\times_{t\in T}E_t,\otimes_{t\in T}\mathcal E_t)$$ such that the coordinate maps $$\pi_s:\times_{t\in T}E_t\ni x=(x_t)_{t\in T}\to x_s\in E_s, s\in T$$ are independent, and $$\Bbb P(\pi_s^{-1}(B_s))=\Bbb P_s(B_s)$$ for each $s\in T$.

From the above, you can see that your problem is realted to an event in such a product probability space obtained from a countably infinte set of simple probabilty spaces, each of them models an experiment of flipping a fair coin, and thus your method that uses conditional probabilities on such a product probability space is valid.

Answer 6

You can address such problems by establishing a recurrence.

The probability that you win from your $n$-th turn is the probability for a head (you win immediately) plus the probability to access the next turn (you draw tail, he draws tail as well) times the probability to win from the $n+1$-th turn.

$$p_n=\frac12+\frac12\frac12p_{n+1}.$$

As the game has no memory, $p_n=p_{n+1}$ and the solution is $p=\frac23$.