Can You Make an Incredible Comeback?

This Week's Fiddler

Observations:

1. Having equal wins and losses means a 50% chance of winning.

2. Because of (1), having two wins prevents you from having a disadvantage possibility for the remainder of the game; at each step, the opponent either ties the game up, loses, or wins on the fifth game.

3. L (a loss) is an insufficient starting sequence for "25% eligibility": We need to win three or four of the remaining four games, which is 5 ways to win out of 16 games possibilities—slightly higher than 25%.

4. Because of (2), WW and WLW are not a valid starting sequences.
5. Because of (2) and (3), LWW is not a valid starting sequence.

6. Because of (4) and (5), the only eligible starting sequences are WLL, LWL, and LL.

In each eligible starting sequence, there is exactly one way for us to win, making a total of 3 winning sequences. There are $2^2+2^2+2^3=16$ eligible sequences in total, making a $\frac{3}{16}$ chance of winning after hitting a 25% win chance or worse at some point.

Answer: 3/16

Extra Credit

We can use dynamic programming to extend the logic we have above. Two dynamically programmed functions can be sufficient: one to calculate the chance of winning despite being disadvantaged at any point, and one to calculate the chance of being disadvantaged. We can then use Bayes' Theorem to find the chance of winning given being disadvantaged at any point.

import math
from fractions import Fraction
from functools import cache


@cache
def binomcdf_right(n: int, p: Fraction, x: int) -> Fraction:
    if x > n:
        return Fraction(0)
    if x < 0:
        return binomcdf_right(n, p, 0)
    return math.comb(n, x) * p**x * (1 - p) ** (n - x) + binomcdf_right(n, p, x + 1)


@cache
def prob_disadvantaged_yet_won(
    games_left: int, wins_needed: int, low: Fraction
) -> Fraction:
    if games_left == 0 or games_left < wins_needed:
        return Fraction(0)
    p = binomcdf_right(games_left, Fraction(1, 2), wins_needed)
    if p <= low:
        return p
    return (
        prob_disadvantaged_yet_won(games_left - 1, wins_needed - 1, low)
        + prob_disadvantaged_yet_won(games_left - 1, wins_needed, low)
    ) / 2


@cache
def prob_disadvantaged(games_left: int, wins_needed: int, low: Fraction) -> Fraction:
    if games_left == 0:
        return Fraction(0)
    p = binomcdf_right(games_left, Fraction(1, 2), wins_needed)
    if p <= low:
        return Fraction(1)
    return (
        prob_disadvantaged(games_left - 1, wins_needed - 1, low)
        + prob_disadvantaged(games_left - 1, wins_needed, low)
    ) / 2


def prob_won_given_disadvantaged(games: int, low: Fraction) -> Fraction:
    wins_needed = games // 2 + 1
    return prob_disadvantaged_yet_won(games, wins_needed, low) / prob_disadvantaged(
        games, wins_needed, low
    )


print(prob_won_given_disadvantaged(5, Fraction(1, 4)))
print(prob_won_given_disadvantaged(101, Fraction(1, 10)))

Answer: 12618868259541820091527436203/162992616172566784661300820527 (about 7.7420%)