Suppose there is a match between two teams where the first team to win a certain number of games wins the match. The match is handicapped, with Teams A needing to win $H_A$ games and Team B needing $H_B$ games. Without loss of generality, let $H_A \le H_B$. The odds of each game are different; let $p_i$ be the probability that Team A wins game $i$, where $1 \le i < H_A + H_B$. What is the probability that Team A wins the match (i.e. wins exactly $H_A$ games and loses fewer than $H_B$)?
I believe the chance of Team A winning is
$$\sum_{n=H_A}^{H_A+H_B-1} \Pr(X_{n-1}=H_A-1) \cdot p_n$$
where $X_n$ is a Poisson binomial distribution over $n$ trials and $\Pr(X_n=k)$ is the probability of $k$ successes. Explanation:
- If A wins, there must be at least $n = H_A$ games (A wins every game) and at most $H_A+H_B-1$ games (A wins $H_A$, B wins $H_B-1$).
- The winner always wins the last game, thus the $p_n$ term.
- In the previous $n-1$ games, A must have won $H_A-1$ times.
Questions:
- Is the formula above correct?
- How can I compute this efficiently? In my case, $H_A + H_B < 32$, and I need to compute this for a large number of sets of $\{p_i\}$. I saw something about using an FFT but haven't seen a simple explanation.
See also: How can I efficiently model the sum of Bernoulli random variables?