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:

Here, we apply the Random Walk in $3$- dimensional space.