Formalise a trick of computing expectations

Question

First let's start with a good old problem:

Consider flipping a fair coin. Let $N_1$ be the number of flips you need to see the first heads (including the last flip of heads). Compute $\Bbb E(N_1)$.

We can do this by noting that $N_1$ is a geometric distribution. But let's do it differently this time. It's clear you have to expend the first flip. What happens then? If the first flip turns out heads (1/2 chance), you're done; if it turns out tails, then you'll need more flips, but the distribution of how many more flips you'll need is just the same as $N_1$. So we have $$\Bbb E(N_1) = \color{red}1 + \frac12\cdot 0 + \frac12\cdot \Bbb E(N_1).$$

A smart observation. But just how to show it is the real expectation in the rigorous sense? Is there anything slicker than explicitly writing out the summation $\Bbb E(N_1) = \sum_{k=0}^\infty k\Bbb P(N_1=k)$ and then decompose each $\Bbb P(N_1=k)$ by the partition formed by "first flip is heads/tails"? For what I have tried, dealing with the explicit summation will not give the first term $\color{red}1$ as a whole, which instead arises only from a complicated summation.

Thanks.

Answer 1

Let $(X_j)_{j \in \mathbb{N}}$ be a sequence of independent identically distributed random variables such that $$\mathbb{P}(X_j = 1) = \mathbb{P}(X_j = -1) = 1/2.$$ We interpret $X_j=1$ as "$j$-th flip is head" and $X_j=-1$ as "$j$-th flip is tails". The random variable

$$N_1 := \inf\{j \in \mathbb{N}; X_j = 1\}$$

is the first time which we observe "head". Clearly,

$$N_1 = \begin{cases} 1, & \text{if} \, \, X_1 = 1, \\ 1+ \inf\{j \geq 1; X_{j+1} = 1\}, &\text{if} \, \, X_1 = -1. \end{cases}$$

If we set $Z_j := X_{j+1}$, then this shows

$$N_1 = \begin{cases} 1, & \text{if} \, \, X_1 = 1, \\ 1+ \inf\{j \geq 1; Z_j = 1\}, & \text{if} \, \, X_1 = -1 \end{cases}$$

and so

$$N_1 = \begin{cases} 1, & \text{if} \, \, X_1 = 1, \\ 1+ \tilde{N}_1, & \text{if} \, \, X_1 = -1 \end{cases} \tag{1}$$

where

$$\tilde{N}_1 := \inf\{j \geq 1; Z_j = 1\}.$$

Since $(X_j)_{j \in \mathbb{N}}$ and $(Z_j)_{j \in \mathbb{N}}$ are equal in distribution, it follows that $N_1 = \tilde{N}_1$ in distribution; in particular, $$\mathbb{E}(N_1) = \mathbb{E}(\tilde{N}_1). \tag{2}$$

Moreover, it follows easily from the independence of the random variables $X_j$, $j \geq 1$, that $X_1$ and $\tilde{N}_1$ are independent. Combining this with $(1)$ we get

$$\begin{align*} \mathbb{E}(N_1) &\stackrel{(1)}{=} \mathbb{E}(1 \cdot 1_{\{X_1=1\}}) + \mathbb{E}((1+\tilde{N}_1) 1_{\{X_1 = -1\}}) \\ &= \mathbb{P}(X_1 = 1) + \mathbb{E}(1+\tilde{N}_1) \mathbb{P}(X_1=-1) \\ &= \frac{1}{2} + \frac{1}{2} (1+\underbrace{\mathbb{E}(\tilde{N}_1)}_{\stackrel{(2)}{=} \mathbb{E}(N_1)}) = 1+\frac{1}{2} \mathbb{E}(N_1). \end{align*}$$

Answer 2

Here I'll provide an answer using the so-called "first step analysis" trick, which is essentially in the same spirit as @saz's accepted answer but might be easier to follow for readers with only introductory level knowledge of probability.

The first flip has two outcomes: heads or tails, each with probability 1/2. So, letting $X_1$ be the first flip (0 for tails and 1 for heads), we can decompose the total expectation using the law of total expectation: $$\begin{align} \Bbb E(N_1) &= \Bbb E(\Bbb E(N_1\mid X_1))\\ &=\Bbb P(X_1 = 0)\Bbb E(N_1\mid X_1=0)+\Bbb P(X_1 = 1)\Bbb E(N_1\mid X_1=1)\\ &=\frac12 \Bbb E(N_1\mid X_1=0) + \frac12\Bbb E(N_1\mid X_1=1)\\ &=\frac12 \Bbb E(N_1\mid X_1=0) + \frac12\cdot 1\\ &=\frac12 (1 + \Bbb E((N_1-1)\mid X_1=0)) + \frac12\cdot 1 \end{align}$$ And note that $\Bbb E((N_1-1)\mid X_1=0)$ means the expectation of how many more flips you'll need after the first flip turns out tails, which you can just treat as though the game starts over and we "recount" a "new" $N_1$, so $\Bbb E((N_1-1)\mid X_1=0) = \Bbb E(N_1)$.