Random Walk Expected Hitting Time

Problem

Expected hitting time of 0 for a random walk on nonnegative integers.

Starting from k, each step moves up with probability p and down with probability 1 - p, and 0 is absorbing. Return k * k when p = 0.5, k / (1 - 2p) when p < 0.5, -1.0 when p > 0.5, and 0.0 for k <= 0.

Hint

Solve E_k = 1 + p * E_(k+1) + (1 - p) * E_(k-1) with E_0 = 0.

Test cases

case 1

in: [1,0.5]

expected: 1

case 2

in: [3,0.5]

expected: 9

case 3

in: [4,0.25]

expected: 8

case 4

in: [2,0.75]

expected: -1

case 5

in: [0,0.5]

expected: 0

Starter codePython

def random_walk_expected_hitting_time(k, p):
    # Your code here
    pass

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