| 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 |