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:
As a bonus, can you generalise for \(n\) jumps?
This problem is a part of my froggy, soggy set.
An ant starts a random walk on the real number line at \(0\). At each step, the ant moves by \(+1\) or \(-1\) with equal probability. After \(6\) moves, the probability that the ant is on a positive number can be expressed as \(\dfrac{a}{b},\) where \(a\) and \(b\) are positive coprime integers. What is the value of \(a+b?\)
This problem is posed by Michael T.
Here, we apply the Random Walk in \(3\)- dimensional space.
Daniel is standing on the origin in the coordinate space. He walks either up, down, left, right, forwards, or backwards one unit each second, each with equal probability. After 6 seconds, the probability he is back on the origin can be expressed as \(\dfrac{p}{q}\) for positive coprime integers \(p,q\). Find \(p\).
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.