Probability of successful scenarios where you run a trial until there are N more successes than failures

Question

How would you calculate the probability of the following scenario being successful or not given the following conditions:

1. You have two variables X and Y, one with probability P and the other 1-P.
2. The goal is to keep running trials until one variable has N more successes than the other. This can be thought of as if X shows up X gets a point and Y loses a point and the vice versa for Y. The scenario ends when one of the variables gets N points, making that variable the winner.
3. How would I calculate the probability of winning in these scenarios?

I understand that for when P(X) = 0.5, the expectation is that half the scenarios will terminate with X winning. But how would one calculate it if the probabilities weren't equal?

Answer 1

Let $p$ be the chance of $X$ winning a point. Fix $N \ge 1$ and for $i$ any integer between $-N$ and $N$ define $f(i)$ to be the chance of $X$ winning the game given $X$ is $i$ points ahead of $Y.$

The rules imply $f(-N)=0,$ $f(N)=1,$ and otherwise the two possible outcomes at this stage, where $X$ will be $i+1$ points ahead with probability $p$ or $i-1$ points ahead with probability $1-p,$ imply

$$f(i) = p f(i+1) + (1-p) f(i-1).\tag{*}$$

This looks very much like the recursion in Pascal's triangle, so we might hope to find some kind of exponential expression for $f(i)$ of the form $f(i) = \alpha x^i$ for some fixed number $x$ (that depends only on $p$ and $N$). Because $f(-N)=0$ this isn't possible, but if we were to add some constant $\beta$ (which clearly satisfies the recursion $(*)$), we might be successful. The conditions imposed thereby on $x,$ $\alpha,$ and $\beta$ are

$$\begin{aligned} 0 &= f(-N) = \beta + \alpha x^{-N}\\ 1 &= f(N) = \beta + \alpha x^N\\ \beta + \alpha x^i &= f(i) = p(\beta+\alpha x^{i+1})+(1-p)(\beta+\alpha x^{i-1}) \end{aligned}$$

Subtracting $\beta$ and dividing the third equation by $\alpha x^i$ gives

$$1 = px + (1-p)x^{-1},$$

equivalent to a quadratic equation in $x$ with solutions

$$x = \frac{1}{2p}\left(1 \pm \sqrt{1 - 4p(1-p)}\right).$$

(This is remarkable because $x$ depends only on $p,$ not on $N:$ given the relative strengths of the players, it's a universal value for all $N.$)

Now the first two equations yield

$$1 - 0 = (\beta + \alpha x^N) - (\beta + \alpha x^{-N}) = \alpha (x^N-x^{-N}),$$

implying

$$\alpha = \frac{1}{x^N - x^{-N}}$$

provided $x \ne 1/x,$ which happens when $p=1/2.$

Finally, the first equation states

$$0 = \beta + \alpha x^{-N} = \beta + \frac{x^{-N}}{x^N - x^{-N}},$$

simplifying to

$$\beta = -\frac{x^{-N}}{x^N - x^{-N}}.$$

Because we found a solution, this method works. It says

$$f(i) = \beta + \alpha x^i = \frac{x^i - x^{-N} }{x^N - x^{-N}}.$$

Finally, the question asks for the chance of winning when the situation is equal; that is, $i=0:$

$$f(0) = \frac{1 -x^{-N} }{x^N - x^{-N}} = \frac{x^N - 1}{x^{2N} - 1} = \frac{1}{x^N + 1} = \frac{(2p)^N}{\left(1 + \sqrt{1 \pm 4p(1-p)}\right)^N + (2p)^N}.$$

When $p\gt 1/2$ this value ought to exceed $1/2,$ because the advantage is to $X,$ and so we must take the negative sign in the formula. When $p\lt 1/2,$ take the positive sign. Finally, when $p=1/2,$ the recursion $(*)$ is easy to solve by inspection: the $f(i)$ must progress arithmetically from $0=f(-N)$ to $1=f(N),$ whence

$$f(i) = \frac{i+N}{2N}$$

for $p=1/2.$ (You could also obtain this solution by taking the limit of $f(i)$ as $x\to 1$ using L'Hopital's Rule.)

---

As an example, this plot shows how $X$'s chances to win with $N=4$ vary with $p:$

The curves must rise as $i$ increases, so the bottom red curve plots the chances for $i=-3$ and the top blue curve plots the chances for $i=3.$ The central black curve plots $f(0).$

The R code to do the calculations and make this plot follows.

f <- Vectorize(function(i, p, n) {
  if (abs(p - 1/2) <= 1e-8) (i + n) / (2 * n) else {
    x <- (1 + ifelse(p > 1/2, -1, 1) * sqrt(1 - 4 * p * (1-p))) / (2 * p)
    (x^i - x^(-n)) / (x^n - x^(-n))
  }
})

N <- 4
curve(f(0, x, N), 0, 1, ylim = 0:1, n = 501,
      main = bquote(paste("Chance to Win by ", .(N), " for ", i==.(1-N), " to ", .(N-1))),
      xlab = "p", ylab = "Probability", lwd = 2)

for (i in setdiff(seq(-N+1, N-1), 0)) {
  curve(f(i, x, N), add = TRUE, lwd = 2, col = hsv((i+N)/(2*N) * 0.75, .9, .8), n = 501)
}

Answer 2

See the formula for $h_i^0$ the bottom of this answer. For your formulation, the probability of $X$ "winning" corresponds to $h_i^0$, $N$ corresponds to $i$, $2N$ corresponds to $N$, and $P$ corresponds to $T$.