Underdog leading at least once in an infinite series of games

Solution 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.)

Solution 2:

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}$.