3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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?) $\endgroup$
    – whuber
    Nov 29, 2022 at 19:16
  • $\begingroup$ 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. $\endgroup$
    – icelorch
    Nov 30, 2022 at 14:26

2 Answers 2

2
$\begingroup$

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

Plot of curves for i = -3 to i = 3

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)
}
$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.