Gambler's Ruin

Problem

Gambler's ruin probability of reaching the target before losing everything.

Starting with start units, each round wins one unit with probability p. Return P(hit target) = (1 - r^start) / (1 - r^target) with r = (1 - p) / p when p is not 0.5, and start / target when p = 0.5. Return 0.0 for start <= 0 and 1.0 for start >= target.

Hint

Set up the recurrence h_i = p * h_(i+1) + q * h_(i-1) with absorbing boundaries.

Test cases

case 1

in: [1,3,0.5]

expected: 0.3333333333333333

case 2

in: [2,3,0.5]

expected: 0.6666666666666666

case 3

in: [1,3,0.75]

expected: 0.6923076923076923

case 4

in: [1,3,0.25]

expected: 0.07692307692307693

case 5

in: [0,5,0.5]

expected: 0

case 6

in: [5,5,0.5]

expected: 1

Starter codePython

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

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