How to Find the Expected Squared Distance in a Random Walk

“Expected value of the distance square” is not a unique quantity: you must specify what is moving, how distance is measured, and what the distance is measured from. A common graph-theory interpretation is the expected squared graph distance from the starting vertex to the position of a random walker after a fixed number of steps.

For that interpretation, find the probability of ending at each vertex, square its distance from the start, and take the probability-weighted sum. The method also applies to other random processes once you identify their possible outcomes and distances.

Expected squared distance on a graph

Let a random walk start at vertex $u$, and let $X_n$ be its position after $n$ steps. Write $d(u,v)$ for the graph distance between vertices $u$ and $v$: the number of edges in a shortest path. The quantity of interest is

The square applies to the distance for each possible outcome before you take the expectation. In general,

where $D=d(u,X_n)$. In fact, $\mathbb{E}[D^2]=\operatorname{Var}(D)+(\mathbb{E}[D])^2$.

Compute it using a transition matrix

For a finite, time-homogeneous Markov walk, encode the walk in its transition matrix $P$, where $P_{ij}$ is the probability of moving from vertex $i$ to vertex $j$ in one step. If the walk starts at $u$, the probability of being at $v$ after $n$ steps is the $(u,v)$ entry of $P^n$. Therefore,

The matrix-power formula assumes the walk is Markov and its transition probabilities are fixed over time. For a walk whose starting vertex is itself random, let $\alpha$ be its starting probability distribution. The probability distribution after $n$ steps is $\alpha P^n$, so, provided every vertex with positive probability under $\alpha P^n$ is connected to a fixed reference vertex $r$, the expected squared distance from $r$ is

Worked example: a walk on a three-vertex path

Consider the path $0$—$1$—$2$. A simple random walk moves to a uniformly chosen neighbor. Start at vertex $0$ and take two steps.

The first step must go from $0$ to $1$. From $1$, the walk moves to $0$ or $2$, each with probability $1/2$. Thus

The distances from the starting vertex $0$ are $d(0,0)=0$ and $d(0,2)=2$. Squaring and weighting by the probabilities gives

For comparison, the expected distance is $\mathbb{E}[d(0,X_2)]=\frac12(0)+\frac12(2)=1$, whose square is $1$, not $2$. This illustrates why you must square each possible distance before averaging.

Common mistakes

• Squaring the mean instead of taking the mean square. Compute $\sum_v \Pr(X_n=v)d(u,v)^2$, not $\left(\sum_v \Pr(X_n=v)d(u,v)\right)^2$.
• Using the wrong distance. Graph distance counts edges in a shortest path. If vertices have coordinates and you mean straight-line distance, use the Euclidean distance instead; the calculation is still a probability-weighted sum of squared distances.
• Ignoring the reference point or time. Distance after one step can differ from distance after many steps, and distance from the start differs from distance between two independently sampled positions.
• Assuming every edge is equally likely. Uniform choice among a vertex’s neighbors defines the usual simple random walk. Weighted edges or other transition rules require their own transition probabilities.

If the intended quantity is the squared displacement of a one-dimensional or multidimensional walk, use the same expectation rule with the square of the displacement. For example, for a one-dimensional walk with position $S_n$, the squared displacement from the origin is $S_n^2$, so its expected value is $\mathbb{E}[S_n^2]$. The distance convention and the walk’s step distribution determine how to evaluate it.