You start with start dollars and bet $1 per round. Each round you win $1 with probability p and lose $1 otherwise, independently. You stop as soon as you have target dollars (success) or 0 dollars (ruin).
Write gamblers_ruin(start: int, target: int, p: Fraction) -> Fraction that returns the exact probability of reaching target before 0.
gamblers_ruin(3, 10, Fraction(1, 2)) # Fraction(3, 10)
gamblers_ruin(1, 2, Fraction(2, 3)) # Fraction(2, 3) one round decides it
gamblers_ruin(0, 5, Fraction(1, 3)) # Fraction(0, 1) already ruined
gamblers_ruin(5, 5, Fraction(1, 3)) # Fraction(1, 1) already there
Constraints: 1 <= target <= 1000, 0 <= start <= target, 0 < p < 1 given as a Fraction.
Let P[i] be the success probability from i dollars. Then P[0] = 0, P[target] = 1 and P[i] = p·P[i+1] + q·P[i-1] with q = 1 - p. Simulation is not exact, and a general O(n³) solve of this system with Fractions is too slow at target = 1000.
Show hint
Rearrange the recurrence to get a relation between consecutive differences P[i+1] - P[i]. They form a geometric sequence with ratio r = q / p; sum it, and watch out for r = 1.