Two players toss a coin; probability game doesn't end in 100 tosses?

Question

Player A and B alternate when flipping a coin. If the number of heads is K more than the number of tails, A wins, if the number of tails is K more than heads, B wins. What is the probability that the game is not over after 100 coin tosses?

I started by considering simpler cases like winning if there are 2 more heads/tails than tails/heads in 100 tosses and it is clear the the game finishes at most on the 3rd toss with probability 1, hence it makes sense that with 50 more heads/tails than tails/heads in 100 tosses the game finishes in at most 99 tosses? For more than that I would need to compute the permutations of the different scenarios for winnings and divide by the total number of posibilities for each K, not feasible. I was thinking maybe I could solve it via recursion or some sort of conditioning

Need help with ideas, hints and/or intuition please!

Also how would that change if the players toss the coins (no alternation) separately and the one to have k more heads/tails than the other wins?

Answer 1

Let $H_n$ be a random variable for the number of heads that occur within the first $n$ coin tosses. It has the distribution $\text{Binomial}(n, \frac{1}{2})$, with a mean of $\frac{n}{2}$ and standard deviation of $\frac{\sqrt{n}}{2}$.

Let $D_n$ be the difference $\text{heads} - \text{tails} = H_n - (n - H_n) = 2H_n - n$. This variable has a mean of $0$ and a standard deviation of $\sqrt{n}$.

For sufficiently large $n$, you can approximate $D_n$'s distribution with a Normal distribution, where the probability that the game doesn't end is $P(|D_n| < K) = P(|z| < \frac{K}{\sqrt{n}})$.

This, however, only considers the situation if the game lasts for $n$ flips, and not if it ends earlier.

Answer 2

Let $X_n = 1$ if the $n$-th coin toss is heads, $X_n = -1$ if the $n$-th coin toss is tails, and $S_n := \sum_{k=1}^n X_n$. Then the game ends at the first time $|S_n| \ge K$, which we denote by $\tau := \min\{n : |S_n| \ge K\}$.

Note that the process $M_n := \cosh(\lambda S_n)e^{c n}$ where $c := \ln\left(\frac{1}{\cosh(\lambda)}\right) < 0$ is a martingale, and $|M_{n\wedge \tau}| \le \cosh(\lambda K) e^{c \tau} < \cosh(\lambda K) < \infty$. Since $M_{n \wedge \tau}$ is bounded, we can apply the optional stopping theorem to conclude $\mathbb{E}[M_{\tau}] = M_0 = 1$. Note that $M_\tau = \cosh(\lambda S_\tau)e^{c \tau} = \cosh(\lambda K) e^{c \tau}$, and so we have \begin{align*} 1 &= \mathbb{E}[M_{\tau}] = \cosh(\lambda K) \mathbb{E}[e^{c \tau}] \\ \Longrightarrow \frac{1}{\cosh(\lambda K)} &= \mathbb{E}[e^{c \tau}] \end{align*} Since we can choose $\lambda$ such that $c$ takes on any value in $(-\infty,0]$, we have identified the distribution of $\tau$ through its moment generating function.