Underdog leading at least once in an infinite series of games

Question

We are observing a tournament where 2 players play a series of games. Exactly one player wins each game. So we can keep count and 5:3 might be the standing after 8 games.

The first player is the favorite and will win a game with probability $p > 1 - p$.

What is the probability that the underdog will lead the standing at least once at some point in an infinite series of games? Or maybe more important than the specific value: Is it $1$ or not?

Somehow I think that it should be $1$, independent of $p$, but I am not sure how much my intuition is worth here. Maybe I can take it to the infinite case with a hint about finite series of $k$ games.

Answer 1

In order for the weaker player to go ahead on the $(2k+1)$-st game, the score must be tied after $2k$ games, and the weaker player must never have been ahead. Each string of $2k$ results in which the weaker player never leads and the final score is tied corresponds to a Dyck word of length $2k$, and there are $C_k$ such words, where $C_k$ is the $k$-th Catalan number. The probability of any such string of results is $p^k(1-p)^k$, so the probability that the weaker player first goes ahead on the $(2k+1)$-st game is $C_kp^k(1-p)^{k+1}$, and the probability that the weaker player leads at some point is

$$\sum_{k\ge 0}C_kp^k(1-p)^{k+1}=(1-p)\sum_{k\ge 0}C_k\big(p(1-p)\big)^k\;.$$

The Catalan numbers have the generating function

$$c(x)=\sum_{k\ge 0}C_kx^k=\frac{1-\sqrt{1-4x}}{2x}\;,$$

so the desired probability is

$$\begin{align*} (1-p)c\big(p(1-p)\big)&=\frac{(1-p)\left(1-\sqrt{1-4p(1-p)}\right)}{2p(1-p)}\\ &=\frac{1-\sqrt{1-4p+4p^2}}{2p}\\ &=\frac{1-(2p-1)}{2p}\\ &=\frac{1-p}{p}\;. \end{align*}$$

(This calculation does assume that $p<1$, but the result clearly holds for $p=1$ as well.)

Answer 2

Let $Y_n$ be difference of scores at time $n$ - first minus second ($Y_0=0$). Let $$m_k=P(\min_{i\geq 0}{Y_i}=-k)$$ for $k\geq0$. Then $$m_k=pm_{k+1}+(1-p)m_{k-1}$$ Solving it subject to constraint $\sum_{k\geq 0}m_k=1$ (since $Y_n\to\infty$ with probability $1$) yeilds $$m_k=(1-\alpha)\alpha^k$$ where $\alpha=\frac {1-p}p<1$. We are interested in $$P(\min_{i\geq 0}{Y_i}\leq-1)=\sum_{k\geq 1}m_k=\alpha=\frac{1-p}p$$

Answer 3

A variant of Bertrand's ballot theorem says that in an election where candidate A receives $a$ votes and candidate B receives $b$ votes with $a \gt b$, the probability that A will be equal to or ahead of B throughout the count is $\dfrac{a+1-b}{a+1}$, so the probability B is ever strictly ahead is $\dfrac{b}{a+1}$.

The law of large numbers implies that here $\dfrac{a}{a+b} \to p$ and thus $\dfrac{b}{a+1} \to \dfrac{1-p}{p}$.