Gambler's Ruin Expected Duration

Problem

Expected number of rounds until a gambler starting with start units hits 0 or target, winning one unit per round with probability p.

For p = 0.5 the answer is start * (target - start). For p not 0.5 use E = (start - target * (1 - r^start) / (1 - r^target)) / (q - p) with q = 1 - p and r = q / p. Return 0.0 when start <= 0 or start >= target, start when p <= 0, and target - start when p >= 1.

Hint

Solve E_i = 1 + p * E_(i+1) + q * E_(i-1) with absorbing boundaries.

Test cases

case 1

in: [1,3,0.5]

expected: 2

case 2

in: [2,4,0.5]

expected: 4

case 3

in: [1,3,0.75]

expected: 2.1538461538461533

case 4

in: [2,5,0.25]

expected: 3.669421487603306

case 5

in: [1,3,0]

expected: 1

Starter codePython

def gambler_ruin_expected_duration(start, target, p):
    # Your code here
    pass

5 test cases · run your code against them in the editor