Random Walks

Think of the random walk as a game, where the player starts at the origin (i.e. all coordinates equal \(0\)) and at each move, he is required to make one step on an arbitrarily chosen axis. For example, in two dimensions, the player would step forwards, backwards, left, or right. The choice is to be made randomly, determined, for instance, by the toss of a fair coin. This is related to many other random events such as Brownian motion, and combination of error in measurements.

Expected Progress in One Dimension

Basic probability would tell you that the expected deviation from the origin in the long run ought to be zero. But one must have the feeling that as \(N\), the number of steps taken increases, he is more likely to have strayed farther away from the origin, \(x=0\). So, we might ask, what is the average of \(D_{N}^{2}\), where \(D_{N}\) is the net distance (from the origin) traveled in \(N\) steps.

After one step, the value of \(D_{1}^{2}=1\). The expected value of \(D_{N}^{2}\), for \(N>1\), can be obtained from \(D_{N-1}\), as \(D_{N}=D_{N-1}\pm1.\)

\(\therefore\quad D_{N}^{2}=D_{N-1}^{2}\pm2D_{N-1}+1\), and because we expect to reach each one of the values half the time, the average of \(D_{N}^{2}\) is just going to be\(D_{N-1}^{2}+1\).

\(Now,\quad as\quad D_{1}^{2}=1\Rightarrow\quad D_{N}^{2}=N\Rightarrow \quad D_{N}=\pm\sqrt{N}\)

\(|D_{N}|=\sqrt N\) is also called root mean squared (rms) deviation and in similar situations to ours, we can expect the absolute value of the deviation of an observed value from the mean, in our case the position x=0, to be less than or equal to the rms.

Example Question 1

---

What would be the width of the range into which the experimental probability should fall so that the coin tossed can be considered a fair one?

\(Let\quad { n }_{ H }\quad and\quad { n }_{ T }\quad be\quad the\quad number\quad of\quad heads\\ and\quad the\quad number\quad of\quad tails\quad that\quad showed\quad up\quad in\quad \\ the\quad experiment,\quad so\quad that\quad { n }_{ H }+{ n }_{ T }=n.\quad So,\quad the\quad \\ deviation\quad D,\quad from\quad equal\quad number\quad of\quad heads\quad and\quad \\ tails\quad would\quad be\quad |{ n }_{ H }-{ n }_{ T }|=|2{ n }_{ H }-n|.\\ \Rightarrow \quad ({ n }_{ H }-n/2)_{ rms }=\quad D_{ rms }/2\quad =\quad \sqrt { n } /2.\\ Note\quad that\quad D_{ rms }\quad is\quad analogous\quad to\quad D_{ N }.\\ \\ The\quad fraction\quad \left< { n }_{ H } \right> /n\quad is\quad equal\quad to\quad 0.5\quad \\ for\quad a\quad fair\quad coin,\quad and\quad we\quad know\quad that\quad the\quad expected\quad \\ difference\quad \quad in\quad the\quad number\quad of\quad heads\quad is\quad going\quad to\quad be\quad \\ either\quad +\sqrt { n } /2\quad or\quad -\sqrt { n } /2\quad from\quad { n }_{ H },\quad so\quad the\quad probability\quad \\ should\quad be\quad in\quad the\quad range\quad of\quad \quad \frac { \left< { n }_{ H } \right> \pm \sqrt { n } /2) }{ n } ,\quad and\quad we\quad \\ can\quad expect\quad an\quad error\quad of\quad \frac { 1 }{ 2\sqrt { n } } \quad either\quad way\quad from\quad 0.5.\\So,\quad the\quad width\quad of\quad the\quad range\quad would\quad be\quad \boxed { \frac { 1 }{ \sqrt { n } } } \)

Examples in one dimension:

A frog, namely, Sally, is jumping about the vertices of a hexagon, \(ABCDEF\) , each time jumping to one of the adjacent vertices with equal probability. Let Sally start her daily workout in \(A\), and a mine be located in \(D\). Every second Sally must make her random jump (as described above). What is Sally's expected lifespan, in minutes, in this system?

As a bonus, can you generalise for \(n\) jumps?

This problem is a part of my froggy, soggy set.

Submit your answer

A man is standing on an infinite ladder. In one move, he can either go up (with probability \(0.4\)), down (with probability \(0.5\)) or stay where he is (with probability \(0.1\)).

Find the probability that after \(11\) moves he is one step away from his initial position.

Inspired by this problem.

Submit your answer

Here, we apply the Random Walk in \(3\)- dimensional space.

A drunkard walks out of a bar at midnight. He is in 3-dimensional space of an infinite size. The probability of his stepping 1 step forward, backward, left, right, up or down is equal. Calculate the probability (to two decimal places) of his (eventually) returning to the bar.

Details and Assumptions:

• Assume the bar is a point particle at the origin.

• We require the probability that he will, at any point in time, return to the bar.

• Do not try this at home.

Submit your answer