Expected value of two successive heads or tails (stuck on computation)

Question

Problem: This is problem 33 of section 2.6 (conditioning) in Bertsekas, Tsitsiklis intro to probability text.

We are given that a coin has probability of heads equal to p and tails equal to q and it is tossed successively and independently until a head comes twice in a row or a tail comes twice in a row. What isthe expected value of the number of tosses?

Solution:

Let $X$ be a random value that tracks the number of tosses. In addition, let $H_k, T_k$ be the event that a head or tail comes up on the kth flip respectively. The solution I am looking at involves using total expectation theorem.

I outline the following steps in the solution.

We can partition the sample space into $H_1$ and $T_1$, allowing us to invoke the total expectation theorem. Hence,

$E[X] = pE[X|H_1] + qE[X|T_1]$

Again by total expectation theorem, we can utilize another partition to obtain

$E[X|H_1] = pE[X|H_1,H_2] + qE[X|H_1,T_2] = 2p + q(1 + E[X|T_1])$

$E[X|T_1] = qE[X|T_1,T_2] + pE[X|T_1,H_2] = 2q + p(1+E[X|H_1])$

Stuck: The solution follows up by saying that we can combine the above two relations and use the fact that p+q = 1 to obtain

$E[X|T_1] = \frac{2+p^2}{1-pq} , E[X|H_1] = \frac{2+q^2}{1-pq}$

I have been staring at this for a while now, but I cannot seem to see the steps of the computation. I'd be very grateful if someone could fill in the details regarding the computation. Thank you.

Answer 1

Let $x=E(X|H_1)$ and $y=E(X|T_1)$. Then we have the two equations $$x=2p+q+qy\quad\text{ and}\quad y=2q+p+px.$$ Two linear equations in two unknowns.

Solve in any of the familiar ways, for example by substituting $2p+q+px$ for $y$ in the first equation.

Answer 2

We can also solve it using absorbing markov chain:

\begin{align*} A = \left(\begin{array}{cccccc} & \mathrm{I} & \mathrm{H} & \mathrm{T} & \mathrm{HH} & \mathrm{HT}\\ \mathrm{I} & 0 & p & q & 0 & 0 \\ \mathrm{H} & 0 & 0 & q & p & 0 \\ \mathrm{T} & 0 & p & 0 & 0 & q \\ \mathrm{HH} & 0 & 0 & 0 & 1 & 0 \\ \mathrm{HT} & 0 & 0 & 0 & 0 & 1 \end{array}\right) \end{align*}

'I' is the initial state.

To get the expected number of steps to go to the absorbing state:

\begin{align*} Q &= \left(\begin{array}{rrr} 0 & p & q \\ 0 & 0 & q \\ 0 & p & 0 \end{array}\right) \end{align*} and compute $(I-Q)^{-1}$ where $I$ is the identity matrix, and sum the first row, and hence: \begin{align*} \mathbb{E}(X) &= \frac{(1+p)(1+q)}{1-p\, q} \end{align*}

Answer 3

An alternative solution to this problem that avoids using recursion and simultaneous equations is to split all possible terminating sequences into four blocks.

Block 1: Start Heads, ends 2 Heads

Block 2: Start Heads, ends 2 Tails

Block 3: Start Tails, ends 2 Tails

Block 4: Start Tails, end 2 Heads

---

pp

pqpp

pqpqpp

---

pqq

pqpqq

pqpqpqq

---

The other two blocks are the same except it starts with q/tails so qq, qpqq ...

The expectation is the sum of the expectation of each block and so E[X] can the be given by the following sums $$ E[X] = \sum_{x=1}^{\infty}2x\ p^{x+1}q^{x-1} + \sum_{x=1}^{\infty} (2x+1)p^{x}q^{x+1} +\sum_{x=1}^{\infty}2x\ q^{x+1}p^{x-1} + \sum_{x=1}^{\infty} (2x+1)q^{x}p^{x+1} $$

The last two sums are basically the first two sums with p and q reversed. You can compute the infinity sums using the following two formulas. $$\sum_{x=1}^\infty x^k=\frac{x}{x-1}$$ $$\sum_{x=1}^\infty k x^k=\frac{x}{(x-1)^2}$$

Honestly though I cheated and used mathematica to get the following formula. Given $p + q = 1$ $$E[X]=-1 + \frac{3}{1 + (-1 + p) p}$$