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

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?

• With any K greater than 1, it's possible the game never ends - no matter how many turns are played, you never hit probability 1 that one player or the other has won. An alternating sequence of heads and tails means that the difference between the number of heads and the number of tails is always 0 or 1. If K>1, we can't guarantee that the game ends at any point. I don't see the relevance of alternating or separate coin flips, who flips the coin has no bearing on the total count of heads and tails. Jun 9, 2022 at 20:32
• I think it's important to point out that the probability the game never ends is $0$, so the game will almost surely end. Jun 9, 2022 at 23:25
• I think this can be rephrased as "What's the probability that a one-dimensional (unbiased) random walk stays with the bound $[-K, K]$ after $100$ steps". I think this is related. Jun 10, 2022 at 10:07

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.

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.

• shouldnt var(Dn)=4var(Hn)=n, hence its sd=sqrt(n)? Jun 9, 2022 at 22:40
• @Redwind: You are correct; I just fixed it.
– Dan
Jun 9, 2022 at 23:17