How many steps are needed to reach 12 from 0 in a probabilistic sequence?

[MATHias1]

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.

 

[HOI]

You could, of course, go from 0 directly to 12 in exactly 12 steps! The probability of that is $$(1/2)^{11}$$. 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 $$(1/2)^{13}$$. 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 $$(1/2)^{15}$$. 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 $$(1/2)^{2n+1}$$. The expected value is given by the infinite sum $$\sum_{n= 0}^\infty(2n+1)(1/2)^{2n+1}$$. To sum that factor out a 1/2 so it becomes $$\frac{1}{2}\sum_{n=0}^\infty (2n+1)(1/2)^{2n}$$. Notice that $$(2n+1)x^{2n}$$ is the derivative of $$x^{2n+1}$$ so we can do $$\sum_{n=0}^\inf (2n+1)x^{2n}$$ as the derivative of $$\sum_{n=0}^\infty x^{2n+ 1}= x\sum_{n=0}^\infty (x^2)^n$$. That last sum is a geometric sum which has a simple closed form: $$x\frac{1}{1- x^2}$$ as long as |x|< 1. Here x= 1/2 so that formula applies and the derivative is $$\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}$$. For x= 1/2 that is $$\frac{1+ 1/4}{(1- 1/4)^2}= \frac{\frac{3}{4}}{\frac{9}{16}}= \frac{3}{4}\frac{16}{9}= \frac{4}{3}$$.

 

[Opalg]

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!).

 

[MATHias1]

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. :)