A simulation can estimate the chance of a winning streak, but the commentator wants the exact value. A coin shows heads with probability p = (a, b), that is a / b, and it is tossed n times independently. What is the probability that somewhere in the n tosses there are at least r heads in a row?
Write streak_chance(n, r, p) that returns the exact probability as a tuple (numerator, denominator) in lowest terms ((0, 1) for probability 0 and (1, 1) for probability 1).
For a fair coin all 2**n sequences of tosses are equally likely, but with n in the hundreds there are far too many of them to list one by one.
Examples
Input: n = 4, r = 2, p = (1, 2)
Output: (1, 2)
Explanation: 8 of the 16 equally likely sequences contain HH somewhere. The other 8 are
TTTT TTTH TTHT THTT HTTT THTH HTHT HTTH.
Input: n = 3, r = 2, p = (1, 3)
Output: (5, 27)
Explanation: the sequences with HH are HHT, THH (each 1/3 · 1/3 · 2/3 = 2/27) and HHH (1/27).
Input: n = 10, r = 3, p = (1, 2)
Output: (65, 128)
Constraints
1 <= r <= n <= 5000 <= a <= b <= 12,b >= 1
Goals
- Compute a probability exactly when there are far too many outcomes to list
- Count the complement (no streak) by remembering only the length of the current run
- Weight the outcomes of a biased coin with exact integer arithmetic