1

Assuming steps are $+1/-1$ with a $50/50$ probability. What is the expected step count for reaching step 10 for the first time?

Probability1
  • 89
  • 1
    Try it for reaching $1$ first. See how it relates to the Catalan Numbers. Then generalise to $10$. – Donald Splutterwit Nov 19 '19 at 16:18
  • Reaching step 1 for the first time is $\frac{1}{2}$ because you can either go +1 with $\frac{1}{2}$ probability or go -1 with $\frac{1}{2}$ with probablity, how can I generalize to reaching step 10 for the first time? – Probability1 Nov 19 '19 at 16:32
  • What about going $-1$ and then $2$ $+1$'s ... etc ... – Donald Splutterwit Nov 19 '19 at 16:34
  • https://math.stackexchange.com/questions/306467/expected-number-of-steps-for-reaching-k-in-a-random-walk?rq=1 –  Nov 19 '19 at 17:01
  • 1
    By linearity of expectation, the expected time to reach $10$ is $10$ times the expected time to reach $1$, since you have to "reach" $1$ ten times to get to $10$. Using the same linearity, the expected time $E$ to reach 1 satisfies $E = 1/2(1) + 1/2(1+2E)$ since $1/2$ the time you get there in $1$ step and $1/2$ the time after $1$ step you must reach a point $2$ beyond where you are in $1$ step. Solving for $E$ ... – Ned Nov 19 '19 at 22:08
  • 1
    @Ned - nice argument that 1 = 0. – Paul Sinclair Nov 19 '19 at 22:24
  • @PaulSinclair not quite, what else might it be telling you about $E$? – Ned Nov 19 '19 at 23:10
  • @Ned - indeed. When you get a contradiction, it is time to re-examine your assumptions. – Paul Sinclair Nov 19 '19 at 23:45
  • You can think the problem as expected stopping time for gambler's ruin problem since the probability is symmetric – Yohanes Alfredo Nov 20 '19 at 06:26

0 Answers0