Expected length of 2-coin tossing game until player's ruin

Question

Player $A$ and player $B$ are playing coin tossing game. Player $A$ has $n$ coins, player B has $m$ coins. If two head or tails turn up then player $A$ takes both coins. Otherwise player $B$ takes them.

I'm thinking this way:

Let us define $F_{n,m}$ - expected game length if $A$ has $n$ coins and $B$ has $m$. Probability of winning in a single round for both players is equal.

Then one has $$F_{n,m} = 1 + 1/2F_{n-1,m} + 1/2 F_{n,m-1}$$

Obviously $F_{0, m} = 0$ and $F_{n,0} = 0$.

How do I solve this reccurence relation? Or should I went differently about this problem?

Answer 1

Let $X_t$ be the number of coins player $A$ has at time $t$. Then $0\leqslant X_t\leqslant n+m$ a.s. so $X_t$ is integrable, and $$\mathbb E[X_{t+1}\mid \mathcal F_t] = \frac12(X_t+1)+\frac12(X_t-1)=X_t, $$so $\{X_t\}$ is a martingale. Let $$\tau = \inf\{t>0:X_t\in\{0,n+m\}\}. $$ Since $\tau$ is the absorption time of a birth-death Markov chain with finitely many states, $\mathbb E[\tau]<\infty$. Moreover, we have $$\mathbb E[|X_{t+1}-X_t|\mid\mathcal F_t]\leqslant 1, $$ and so by optional stopping, $$\mathbb E[X_\tau] = \mathbb E[X_0]. $$ It follows that $$\mathbb E[X_\tau\mid X_\tau=0]\mathbb P(X_\tau=0)+\mathbb E[X_\tau\mid X_\tau=n+m]\mathbb P(X_\tau=n+m)=n, $$ from which the probability of player A winning is $$ p_A:=\mathbb P(X_\tau=n+m) = \frac n{n+m}. $$

Let $W_t$ denote the winnings of player $A$ at time $t$. Then $$X_t = X_0 + \sum_{i=1}^t W_i, $$ and where the $W_i$ are i.i.d. with $$\mathbb P(W_1=1)=\mathbb P(W_1=-1)=\frac12. $$ Since $\mathbb E[W_1]=0$ and $\mathbb E[W_1^2]=1$, Wald's second identity yields $$\mathbb E\left[\left(\sum_{t=1}^\tau W_t\right)^2\right] = \mathbb E[\tau].$$ Since $$\sum_{t=1}^\tau W_t = X_t-X_0, $$ it follows that \begin{align} \mathbb E[\tau] &= \mathbb E[(X_\tau-X_0)^2]\\ &= \mathbb E[(X_\tau-X_0)^2\mid X_\tau=0]\mathbb P(X_\tau=0)+E[(X_\tau-X_0)^2\mid X_\tau=n+m]\mathbb P(X_\tau=n+m)\\ &= (0-n)^2(1-p_a) + (n+m-n)^2p_a\\ &= \frac{n^2m}{n+m} + \frac{nm^2}{n+m}\\ &= nm. \end{align} Intuitively this makes sense because for a given $N=n+m$, the expected length is maximized when $n=m$ (for even $N$) or $|n-m|=1$ (for odd $N$).

Answer 2

Its just a non-homogeneous linear recurrence. You can solve it by generating functions or whatever.

Alternatively, you can model it as a MC on state space {0,...,n+m} (with the state being the number of coins A has) and look at the expected hitting time of the set {0,n+m}. The transition matrix of this MC will be $i\to i+1$ with probability 1/2 and $i\to i-1$ with probability 1/2 for $i \neq 0,n+m$ and $0\to 0$ with probability $1$ and $n+m \to n+m$ with probability $1$. You can then set up the equivalent system of equations for expected hitting times as in Theorem 1.3.5 in Norris' Markov Chains (linked here), which says that the expected hitting time of set $A$ starting from state $i$ is zero if $i \in A$, and is given by $1+ \sum_{j \notin A} p_{ij} (\text{ hitting time starting from state j to A})$ and $p_{ij}$ is the probability of $i \to j$'s minimal non-negative solution for the hitting times.