Expected Waiting Times¶

Let's find some expectations by conditioning. All of the calculations below involve conditioning on early moves of a random process.

Waiting till H¶

A coin lands heads with chance $p$. Let's call it a $p$-coin for short. Let $X$ be the number of tosses of a $p$-coin till the first head appears.

As you have seen in exercises, $X$ has the geometric $(p)$ distribution on $1, 2, 3, \ldots $. By using the tail sum formula for expectation, you have showed that $E(X) = \frac{1}{p}$. Here is a quicker way to arrive at the same result.

The method is based on representing $X$ as a mixture of two other random variables:

• With probability $p$, $X=1$.
• With the remaining probability $q = 1-p$, the first toss is a tail, and then the process starts over independently of what has happened before. That is, with probability $q$, $X = 1 + X^*$ where $X^*$ is an independent copy of $X$.

Therefore, by averaging conditional expectations,

$$ E(X) = pE(1) ~ + ~ qE(1+X^*) = p + q(1+E(X^*)) = p + q(1+E(X)) $$

Solve for $E(X)$: $$ E(X) = \frac{1}{p} $$

Waiting Till Both Faces Have Appeared¶

Suppose you toss the $p$-coin until both faces have appeared. Let $N$ be the number of tosses.

Question. What is $E(N)$?

Answer. By conditioning on the first toss:

• With probability $p$ the first toss is a head, so $N = 1 + W_T$ where $W_T$ has the geometric $(q)$ distribution.
• With probability $q$ the first toss is a tail, so $N = 1 + W_H$ where $W_H$ has the geometric $(p)$ distribution.

So

$$ E(N) = p\big{(}1 + \frac{1}{q} \big{)} + q\big{(}1 + \frac{1}{p} \big{)} = 1 + \frac{p^2 + q^2}{pq} = \frac{1 - pq}{pq} $$

Waiting till HH¶

In tosses of a $p$-coin, let $W_{HH}$ be the number of tosses till you see two heads in a row.

Question. What is $E(W_{HH})$?

Answer 1. We can find this is several ways. One way is by conditioning on the first two tosses.

• With probability $q$, the first toss is a tail, so $W_{HH} = 1 + W^*$ where $W^*$ is an independent copy of $W_{HH}$.
• With probability $pq$ the first two tosses are HT, and $W_{HH} = 2 + W^{**}$ where $W^{**}$ is an independent copy of $W_{HH}$.
• With probability $p^2$, the first two tosses are heads, and $W_{HH} = 2$.

So if $x = E(W_{HH})$ then $$ x = q(1+x) + pq(2+x) + p^22 $$

So $$ x = \frac{q + 2pq + 2p^2}{1 - q - pq} = \frac{1+p}{p^2} $$ by repeatedly using $p + q = 1$.

Answer 2. Another way is by conditioning on $X$, the number of tosses till the first head. This is the same random variable $X$ as in the previous example. Notice that $W_{HH} = X + Y$ where:

• With probability $p$, the toss after $X$ is a head, so $Y = 1$.
• With probability $q$, the toss after $X$ is a tail, so $Y = 1 + W^*$ where $W^*$ is an independent copy of $W_{HH}$.

So if $x = E(W_{HH})$ then $$ x = E(X) + E(Y) = \frac{1}{p} + p + q(1 + x) $$ So $$ px = \frac{1}{p} + 1 ~~~~ \text{and hence} ~~~~ x = \frac{1+p}{p^2} $$ as before.

Gambler's Ruin: Duration of the Game¶

Let's return to the setting of the gambler's ruin problem with a fair coin. The gambler starts with $\$a$ and bets on a fair coin till he reaches either $\$b$ or $\$0$. Let $T$ be the duration of the game.

Question. What is $E_a(T)$, the expected duration of the game given that the gambler starts with $\$a$?

Answer. Let $E_k(T)$ denote the expected duration of the game given that the gambler starts with $\$k$. Then for $1 \le k \le b-1$,

$$ E_k(T) = 1 + \frac{1}{2}E_{k-1}T + \frac{1}{2} E_{k+1}T $$

where the edge cases are $$ E_0(T) = 0 = E_b(T) $$

You can check that the function $f(k) = k(b-k)$ satisfies this recursion, and hence that $E_a(T) = a(b-a)$.