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?
 A: 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.
A: 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.
