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. :)
 
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Back
Top