A Random Walk

Probability Level 5

Brilli the ant decides to have a walk along an infinitely long 1D line. For each step he takes, he would either walk forward or backwards by a distance of 1 with equal probability. Given that the expected displacement Brilli the ant would travel after k k steps is E k E_k , find

lim ⁡ k → ∞ 2 k E k 2 \lim _{ k\to\infty }{ \frac{2k}{E_k^2} }


The answer is 3.14159265.

View wiki
Julian Poon by Julian Poon , 20, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Julian Poon
Dec 22, 2015

Consider this table:

The 0 in the first row represents the starting position of Brilli the Ant.

The numbers in the boxes represent the number of ways to that Brilli the Ant can land in that spot after a number of steps. The numbers in each row total to 2 n 2^{n} , where n n is the number if steps taken.

Using this way to calculate, you can see that what I'm doing is basically: Where there's a 0, add the previous 2 2 numbers adjacent to it. For example:

This is very similar to the Pascal's triangle , whose coefficients for each row is ( n k ) , { 0 ≥ k ≥ n } \left( \begin{matrix} n \\ k \end{matrix} \right) ,\left\{ 0\ge k\ge n \right\} .

Now,

E n = ∑ ( Distance from starting point ) ( Number of ways to get to that distance away ) 2 n E_n=\frac { \sum (\text{Distance from starting point})({\text{Number of ways to get to that distance away}}) }{ { 2 }^{ n } }

This is where I would split E n E_n into 2 different cases, where n is even and where n is odd.

So when n = 2 k n=2k is even,

E 2 k = 2 ∑ j = 1 k ( 2 j ) ( 2 k k + j ) 2 2 k = ∑ j = 1 k j ( 2 k k + j ) 2 2 k − 2 = 1 2 k ( 2 k k ) 2 2 k − 2 (*) E_{2k}=\frac { 2\sum _{ j=1 }^{ k } \left( 2j \right) \left( \begin{matrix} 2k \\ k+j \end{matrix} \right) }{ 2^{ 2k } }=\frac { \sum _{ j=1 }^{ k } j\left( \begin{matrix} 2k \\ k+j \end{matrix} \right) }{ 2^{ 2k-2 } } \tag{*} \\=\frac { \frac { 1 }{ 2 } k\left( \begin{matrix} 2k \\ k \end{matrix} \right) }{ 2^{ 2k-2 } }

As k → ∞ k\to\infty , we can use Stirling's Approximation to get:

E 2 k = 2 k π , E k = 2 k π E_{2k}=2\sqrt{\frac{k}{\pi }}, E_k=\sqrt{\frac{2k}{\pi }}

A similar method can be used to show that when n n is odd, E n E_n can also be approximated as such.

Hence, the answer to this problem is:

2 k E k 2 = π \frac{2k}{E_k^2}=\pi

Feel free to ask any questions if this solution is vague.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

( ∗ ) (*)

∑ j = 1 k j ( 2 k k + j ) = ( 2 k ) ! ∑ j = 1 k j ( k + j ) ! ⋅ ( k − j ) ! = S 2 S = ( 2 k ) ! ∑ j = 1 k ( j + k ) − ( k − j ) ( k + j ) ! ⋅ ( k − j ) ! = ( 2 k ) ! ∑ j = 1 k j + k ( k + j ) ! ⋅ ( k − j ) ! − k − j ( k + j ) ! ⋅ ( k − j ) ! = ( 2 k ) ! ∑ j = 1 k 1 ( k + j − 1 ) ! ⋅ ( k − j ) ! − 1 ( k + j ) ! ⋅ ( k − j − 1 ) ! = ( 2 k ) ∑ j = 1 k ( 2 k − 1 k + j − 1 ) − ( 2 k − 1 k + j ) \sum _{ j=1 }^{ k } j\left( \begin{matrix} 2k \\ k+j \end{matrix} \right) =\left( 2k \right) !\sum _{ j=1 }^{ k } \frac { j }{ \left( k+j \right) !\cdot \left( k-j \right) ! } =S \\ 2S=\left( 2k \right) !\sum _{ j=1 }^{ k } \frac { \left( j+k \right) -\left( k-j \right) }{ \left( k+j \right) !\cdot \left( k-j \right) ! } =\left( 2k \right) !\sum _{ j=1 }^{ k } \frac { j+k }{ \left( k+j \right) !\cdot \left( k-j \right) ! } -\frac { k-j }{ \left( k+j \right) !\cdot \left( k-j \right) ! } \\ =\left( 2k \right) !\sum _{ j=1 }^{ k } \frac { 1 }{ \left( k+j-1 \right) !\cdot \left( k-j \right) ! } -\frac { 1 }{ \left( k+j \right) !\cdot \left( k-j-1 \right) ! } =\left( 2k \right) \sum _{ j=1 }^{ k } \left( \begin{matrix} 2k-1 \\ k+j-1 \end{matrix} \right) -\left( \begin{matrix} 2k-1 \\ k+j \end{matrix} \right)

The last sum is a telescoping series which gives

2 S = k ( 2 k k ) 2S=k\left( \begin{matrix} 2k \\ k \end{matrix} \right)

Credit: Jack D'Aurizio

Julian Poon - 5 years, 5 months ago

Log in to reply

There is a much easier approach in understanding the expected value.

Claim: E 2 n + 1 = E 2 n + ( 2 n n ) E_{2n+1} = E_{2n} + { 2n \choose n } and E 2 n + 2 = E 2 n + 1 E_{2n+2} = E_{2n+1} . This follow directly by considering that the average displacement doesn't change from one step to the next unless you are at the origin.

(Note: Ignore the n = 0 n= 0 case. To me, there is 1 way of being at 0, instead of 0 ways. Still, E 0 = 0 E_0 = 0 so that doesn't make a difference.)

Calvin Lin Staff - 5 years, 5 months ago

Log in to reply

Wow, thanks!

Julian Poon - 5 years, 5 months ago

Log in to reply

@Julian Poon – You mug math every day

but Calvin mugs math twice daily

Lee Isaac - 5 years, 5 months ago

The ant wouldn't have gotten far because I would have sprayed it with pesticide.

Lee Isaac - 5 years, 5 months ago

Log in to reply

Wow, you would kill one of your kind.

Julian Poon - 5 years, 5 months ago

Log in to reply

I wouldn't kill a human, but I'd willingly spray your superior (the ant) with pesticide. Like at least when you double an ant's IQ it increases right?

Lee Isaac - 5 years, 5 months ago

Log in to reply

@Lee Isaac – Hi Lee, please be respectful of the community. Negative behavior will not be tolerated.

Calvin Lin Staff - 5 years, 5 months ago

@Lee Isaac – Hey, actually I have to admit, that was a good one.

Julian Poon - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...