Hard | Probability |

You are initially located at origin in the x-axis. You start a random walk with equal probability of moving left or right one step at a time. What is the probability that you will reach point a before reaching point -b? What is the expected number of steps to reach either a or -b? (a,b are natural numbers)

Answer

b/(a+b) and ab

Solution

If you try markov chain approach, this question will never end! For this problem, we will use Martingales.

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Source: Top Quant Interview

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |