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

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?

• The probability is always $1,$ because the scenario will almost surely terminate. The only situation in which any calculation is needed occurs when $P=1/2.$ (Where you write "X = 0.48" you must mean $P=0.48,$ right?)
– whuber
Nov 29, 2022 at 19:16
• Yes. I understand that the scenario will always terminate but I am looking for the probability that it will terminate with X winning versus Y. Nov 30, 2022 at 14:26

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)
}


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