Welcome to our community

Be a part of something great, join today!

[SOLVED] Expected value of steps

MATHias

New member
Oct 10, 2018
2
Hello,

I would like to ask, if I am right with my computation.

Let´s have a set of integers from 0 to 12. We start at 0 and we can go to 1 with the probability 1. From 1 we can go to 1 or back to 0, both with probability 0.5. When we start at zero, how many steps (exp. number of them) do we need to go until 12?

My way of solving:

We start at 0 ... there is only one possibity - to go to the 1 with probability 1
From 1, we can go to the 0 (P=$\frac{1}{2}$) or to the 2 (P=$\frac{1}{2}$)
From 2, we can go back to the 1(P=$\frac{1}{2}$), or forwards to the 3(P=$\frac{1}{2}$) ... but when we start at 0, there is the probability to reach 3(P=${\frac{1}{2}}^{2}$).
etc.

So, I created a binomial distribution:
From 0 to 1: 1 step; prob. 1 ... 1*1
From 0 to 2: 2 steps; prob. ${12 \choose 1}*\frac{1}{2}^{1}*{\frac{1}{2}}^{11}$
From 0 to 3: 3 steps; prob. ${12 \choose 2}*{\frac{1}{2}}^{2}*{\frac{1}{2}}^{10}$
...
From 0 to 11: 11 steps; prob. ${12 \choose 10}*{\frac{1}{2}}^{10}*{\frac{1}{2}}^{2}$
From 0 to 12: 12 steps; prob. ${12 \choose 11}*{\frac{1}{2}}^{11}*{\frac{1}{2}}^{1}$

And now, to get the whole expected value, I need to sum all the expected values:
$1*1+12*2(steps)*\frac{1}{2048}+66*3\frac{1}{2048}+220*4\frac{1}{2048}+495*5\frac{1}{2048}+792*6*\frac{1}{2048}+924*7*\frac{1}{2048}+792*8*\frac{1}{2048}+495*9*\frac{1}{2048}+220*10*\frac{1}{2048}+66*11*\frac{1}{2048}+12*12*\frac{1}{2048}$.

The sum is 15353/1024 = 14.9932 steps. I think it is too low number. Can I ask, where I am not doing right?

Thank you a lot.

Have a nice day.
 
Last edited:

Country Boy

Well-known member
MHB Math Helper
Jan 30, 2018
371
You could, of course, go from 0 directly to 12 in exactly 12 steps! The probability of that is [tex](1/2)^{11}[/tex]. Or, you could, exactly once, go a step back. In that case, ignoring the first step from 0 to 1, you would have 13 steps, "x" steps up to that point, then one step back, then one step to get back to that point, then the remaining 13- x steps for a total x+ 2+ 13- x= 13 steps. The probability of that is [tex](1/2)^{13}[/tex]. Now do the same if we go back twice: either at two different steps or twice at the same step. Each step backwards adds 2 steps to the total so going back twice gives a total of 15 steps. And those steps have probability 1/2 so the probability is [tex](1/2)^{15}[/tex].


In general, there can be any even number of steps or, ignoring the first step, any odd number of steps. For 2n+ 1 steps The probability is [tex](1/2)^{2n+1}[/tex]. The expected value is given by the infinite sum [tex]\sum_{n= 0}^\infty(2n+1)(1/2)^{2n+1}[/tex]. To sum that factor out a 1/2 so it becomes [tex]\frac{1}{2}\sum_{n=0}^\infty (2n+1)(1/2)^{2n}[/tex]. Notice that [tex](2n+1)x^{2n}[/tex] is the derivative of [tex]x^{2n+1}[/tex] so we can do [tex]\sum_{n=0}^\inf (2n+1)x^{2n}[/tex] as the derivative of [tex]\sum_{n=0}^\infty x^{2n+ 1}= x\sum_{n=0}^\infty (x^2)^n[/tex]. That last sum is a geometric sum which has a simple closed form: [tex]x\frac{1}{1- x^2}[/tex] as long as |x|< 1. Here x= 1/2 so that formula applies and the derivative is [tex]\left(\frac{x}{1- x^2}\right)'= \frac{(1- x^2)- (-2x^2)}{1- x^2)^2}= \frac{1+ x^2}{(1- x^2)^2}[/tex]. For x= 1/2 that is [tex]\frac{1+ 1/4}{(1- 1/4)^2}= \frac{\frac{3}{4}}{\frac{9}{16}}= \frac{3}{4}\frac{16}{9}= \frac{4}{3}[/tex].
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
This is an example of an absorbing Markov chain. By calculating the fundamental matrix for this problem, I found that in order to reach level 12 you have to spend an average of 2 steps at level 11, an average of 4 steps at level 10, 6 steps at level 9 and so on (two extra steps for each level as you go down) till you get to 20 steps at level 2, 22 steps at level 1 and 12 steps at level 0 (12 rather than 24 because from level 0 you have to go back to level 1). Therefore the expected total number of steps to reach level 12 is \[2+4+6+8 + \ldots + 22 + 12 = 144\] (considerably more than 14.9932!).
 
Last edited:

MATHias

New member
Oct 10, 2018
2
Yeah, I see. I had expected more complicated theory in that. Sometimes, it is just easier to draw a graphics to see that. :) Thanks a lot to both of you. :)