Random Walks

Here is a set lectures by Sid Redner.

There exists several simple models of random walks. It can be either fixed stepsize but random directions or varying stepsize.

Fixed Stepsize

A simple model is that we assume each step is a step of size $ \epsilon$, but with random directions. The position of this random walker at step $ N$ is the summation of all the steps (vectors),

$$ \vec X = \sum_i^N x_i, $$

where $ x_i$ is the vector that represents step i.

What we want to find out is the places that the random walker explored after $ N$ steps. The corresponding quantity that represents it is $ \sqrt{\langle \vec X^2 \rangle}$.

From the idea of random walk, we know that

$$ \begin{align} \langle \vec x_i \rangle =& 0 \\ \langle \vec x_i \cdot \vec x_j \rangle =& 0. \end{align} $$


$$ \begin{align} \langle \vec X^2 \rangle = & \sum_i \vec x_i\cdot \vec x_i \\ =& N \epsilon^2. \end{align} $$

Then we find out that

$$ \begin{equation} \bar X = \sqrt{\langle \vec X^2 \rangle} = \sqrt{N}\epsilon. \label{eqn-rms-distance} \end{equation} $$

Significance of Dimension

From the root-mean-squared distance Eq. \ref{eqn-rms-distance} we can define the density of points. Suppose we have a continues version of this random walk. After time $ t$, the random walker walked a distance $ vt$. Meanwhile the random walker explored a region of radius $ \sqrt{t}v$, which corresponds to a volume $ V \propto \sqrt{t}v$. The density of walked points is defined as

$$ \rho \propto \frac{t}{\sqrt{t}^d} = t^{1-d/2}, $$

where $ d$ is the dimension of the space.

We spot this critical dimension $ d=2$.

  1. $ d<2$: the density of points at $ t\to\infty$ becomes $ \rho\to \infty$. This called recurrent behavior. We are sure that after infinite time, we are going back to a point that we visited before.
  2. $ d=2$: the density of points at $ t\to\infty$ becomes $ \rho\to \mathrm{Constant}$. This derivation is wrong about this critical case. It should be $ \rho\to \ln t$
  3. $ d>2$: the density of points at $ t\to\infty$ becomes $ \rho\to 0$. This is called transit behavior. We are not sure that we could go back to a point that we visited before.


  1. Sid Redner’s Lectures @ Santa Fe Institute

Planted: by ;

Lei Ma (2020). 'Random Walks', Intelligence, 10 April. Available at: https://intelligence.leima.is/toolbox/stochastic/random-walks/.