Show that the number of heads from the first coin minus the number of heads from the second coin is a null recurrent Markov chain

Question

Two fair coins are tossed repeatedly. Let Xn denote (Total Number of Heads from Coin 1)-(Total Number of Heads from Coin 2) after n tosses. Thus the state space is {0, ±1, ±2, .... }. Show that the zero state, where the total number of heads is the same for each coin, is null recurrent.

Answer 1

This is a Markov chain with transitions $x\to x+1$ with probability $\frac14$ (coin 1 = heads, coin 2 = tails), $x\to x-1$ with probability $\frac14$ (coin 1 = tails, coin 2 = heads), and $x\to x$ with probability $\frac12$ (coin 1 = coin 2), for every $x$. The steps of this random walk have mean zero hence the chain is (null) recurrent. This means that every state is visited infinitely often almost surely and that the return time to any given state, while almost surely finite, is not integrable.

A reduction to a known case is based on the fact that the successive different positions of this Markov chain perform a standard random walk on $\mathbb Z$, which is recurrent.

In formulas, let $t(0)=0$ and $t(k+1)=\inf\{n\geqslant t(k)\mid X_n\ne X_{t(k)}\}$ for every $k\geqslant0$. Each random time $t(k)$ is almost surely finite hence one can define $Y_k=X_{t(k)}$. Then $(Y_k)$ is a Markov chain on $\mathbb Z$ with transitions $x\to x+1$ with probability $\frac12$ and $x\to x-1$ with probability $\frac12$, for every integer $x$. In particular, $(Y_k)$ returns almost surely to zero, that is, $Y_k=0$ for some (random finite) time $k\geqslant1$, that is, $X_{t(k)}=0$, which proves that $(X_n)$ is recurrent.

Answer 2

Your initial state is $X_0=0$. When tossing the two coins you can have the following results $\{HH, HT, TH, TT \}$ with probabilities $1/4$ each. Then in each step there are the possible transitions $$X_{n+1}=\begin{cases} X_n+1, & \text{with probability } \frac14 \{HT\} \\ X_n+0=X_n, & \text{with probability } \frac12 \{HH, TT\}\\ X_n-1, & \text{with probability } \frac14 \{TH\} \end{cases}$$

Denote with $T_0$ the number of visits to state $0$. Now, in order to get back to $0$ in $m$ steps, you have to make equal number of $+1$'s and $-1$'s (and then the rest - if any - can be $0$'s). Therefore denote m as $2n+k$, so that the probability to return to $0$ in $2n+k$ steps is $$\dbinom{2n+k}{n}\dbinom{n+k}{k}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k=\frac{(2n+k)!}{n!n!k!}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k$$ (multinomial distribution, with three possible results). Thus $$E[T_0]=E\left(\sum_{n=0}^\infty 1_{(X_n=0)}\right)=\sum_{n=0}^\infty p_{0,0}(n)=\sum_{2n+k\in \mathbb N} \frac{(2n+k)!}{n!n!k!}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k=\infty$$ so that the state $0$ is null recurrent.

---

The last equation can be justified as follows $$\begin{align*}\sum_{2n+k\in \mathbb N} \frac{(2n+k)!}{n!n!k!}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k&=\sum_{n\in \mathbb N}\sum_{k\in \mathbb N}\frac{(2n+k)!}{n!n!k!}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k\ge\\&\ge \sum_{n\in \mathbb N}\sum_{k=2n}\frac{(2n+k)!}{n!n!k!}\left(\frac14\right)^n\left(\frac14\right)^n\left(\frac12\right)^k=\\&=\sum_{n\in \mathbb N}\frac{(4n)!}{n!n!(2n)!}\left(\frac{1}{4}\right)^{3n} \sim A\sum_{n=1}^{\infty}\frac{1}{n}=\infty\end{align*}$$ where the RHS is the divergent harmonic series. The congruence is due to Stirling's formula, which yields $$\frac{(4n)!}{n!n!(2n)!}\left(\frac{1}{4}\right)^{3n} \sim A\frac{1}{n}$$ where $A>1$ denotes a constant. The sign $\sim$ means that two terms have the same behaviour as $n\to \infty$.