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

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!

• "The fact that the answer satisfies an equation does not immediately imply that a solution to the equation is the answer": Yes it does, if the equation only has one solution. Commented Aug 11 at 9:41
• Hint: 1/2 the time, the first player will not immediately win. At this point, the first player now becomes the second player. Commented Aug 11 at 9:45
• These types equations you often see are derived rigorously using the law of total probability or law of total expectation Commented Aug 11 at 9:52
• To make the argument rigorous, you need to argue that the probability you want actually exists. Otherwise you can get nonsense this way. To show existence, you can, of course, invoke the geometric series (which gives another way to compute the answer).
– lulu
Commented Aug 11 at 9:55
• @Vercassivelaunos Here's a cheap example of non-uniqueness: suppose a type of bacteria divides with probability $p$ in a given second (else it dies). What is the probability, $\psi$, that the colony lives forever? Considering the first second, one gets $\psi=p\times (1-(1-\psi)^2)\implies \psi \in \{0, 2-\frac 1p\}$. Note that the non-zero solution is only physically sensible if $p≥.5$. But uniqueness is a bit of a red herring. If the desired probability does not exist then uniqueness won't save you.
– lulu
Commented Aug 11 at 10:12

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$$.

• Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Mathematics Meta, or in Mathematics Chat. Comments continuing discussion may be removed. Commented Aug 15 at 17:17

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. :)

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)

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.

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.

• In the particular case of a countably infinite product of $Uniform(\{ 0, 1 \})$, I've seen the resulting probability measure be referred to as "Lebesgue measure". Probably because if you consider the map to the interval $[0, 1]$ taking $(a_n)$ to the real number $\sum_{n=1}^\infty a_n 2^{-n}$ with binary expansion $0.a_1 a_2 \ldots$, this map roughly speaking gives an "a.e. isomorphism" between that measure and Lebesgue measure on $[0, 1]$. Commented Aug 12 at 16:27
• Of course, you would have to verify that the given event is measurable with respect to the product probability measure -- which follows from the fact that such measurable sets include the Borel sets (with respect to the product topology where $\{ 0, 1 \}$ is given the discrete topology), while the given event in fact turns out to be an open subset of $\{ 0, 1 \}^{\mathbb{N}_+}$. Commented Aug 12 at 16:31
• @DanielSchepler Thank you for the clarifying comments!
– Amir
Commented Aug 12 at 16:33

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$$.

• Note that in your solution you assumed (appropriately) that the probability distribution is the same for you and your opponent, allowing you to use $1-x$. Here this observation is not required, the resolution would work with two different biased coins. Commented Aug 11 at 18:53