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

AI Thread Summary
The discussion revolves around calculating the expected number of steps needed to reach the integer 12 from 0 in a probabilistic sequence. The initial computation suggested an expected value of approximately 14.9932 steps, which was deemed too low. Further analysis revealed that the expected total number of steps is significantly higher, around 144 steps, due to the nature of the probabilistic transitions and the potential for backward steps. The conversation highlights the complexity of the problem, emphasizing the use of absorbing Markov chains to derive the correct expected value. Visualizing the problem can simplify understanding the underlying mechanics of the steps involved.
MATHias1
Messages
2
Reaction score
0
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:
Mathematics news on Phys.org
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)&#039;= \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}.
 
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:
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. :)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top