random walk with renewal riddle

The Riddler of this week had a rather straightforward puzzle, which can be summarised as finding the expectation of the number of steps needed for a random walk on {1,2,…,N} to reach state 1 when starting at N, if it moves by -1 with probability p and back to N with probability (1-p). Since the return to N is a renewal, the number of steps M is equal to N-1 with probability p^N-1 and to i+1+M’ with probability pⁱ(1-p) for 0≤i≤N-2, M and M’ being iid. Hence a point fixe equation

$E=(N-1)p^{N-1}+\sum_{i=0}^{N-2}(i+1+E)p^i(1-p))$

leading to

$E=\frac{1-p^{N-1}}{p^{N-1}(1-p)}$

which correctly returns p⁻¹ when N=2.

This entry was posted on February 19, 2023 at 12:23 am and is filed under Books, Kids, Statistics with tags fixed-point equation, random walk, renewal process, The Riddler. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Xi'an's Og