# Why is an unbiased random walk non-ergodic?

Wikipedia says "An unbiased random walk is non-ergodic."

Let's look at a simple random walk. It's defined as: take independent random variables $$Z_{1},Z_{2}$$, where each variable is either $$1$$ or $$−1,$$ with a 50% probability for either value, and set $$S_{0}=0\,\!$$ and $$S_{n}=\sum _{j=1}^{n}Z_{j}$$.

If we calculate (let's say) the mean mean for an ensemble of size $$N$$ it will be $$(\sum _{j=1}^{n}Z_{j})/N$$ and the mean for a single realisation of length $$N$$ will be exactly the same $$(\sum _{j=1}^{n}Z_{j})/N.$$

So, why is it non-ergodic?

That Wikipedia article writes,

The process $$X(t)$$ is said to be mean-ergodic or mean-square ergodic in the first moment if the time average estimate $${\hat {\mu }}_{X}={\frac {1}{T}}\int _{0}^{T}X(t)\,\mathrm{d}t$$ converges in squared mean to the ensemble average $$\mu _{X}$$ as $$T\rightarrow \infty.$$

The problem is that $$\hat\mu$$ becomes more and more variable as $$T$$ increases. This becomes apparent when $$X(t)$$ is the discrete Binomial random walk described in the question, because the time average is

$$\hat\mu(X) = \frac{1}{T} \sum_{i=1}^T X(t) = \frac{1}{T} \sum_{i=1}^T \sum_{j=1}^i Z(i) = Z(1) + \frac{T-1}{T}Z(2) + \cdots + \frac{1}{T}Z(T).$$

Notice how the early terms persist: $$Z(1)$$ appears with coefficient $$1$$ and the coefficients of the subsequent $$Z(i)$$ converge to $$1$$ as $$T$$ grows. Their contributions to the time average therefore do not get averaged out and consequently the time average cannot converge to a constant.

In the context and notation of the Wikipedia article, let's prove this result by finding the mean and variance of the time average.

The expectation of $$\hat{\mu}_X$$ is

$$\mathbb{E}(\hat{\mu}_X) = {\frac {1}{T}}\int _{0}^{T}\mathbb{E}(X(t))\,\mathrm{d}t = \frac{1}{T}\int_0^T 0\, \mathrm{d}t = 0.$$

Therefore its variance is the expectation of its square,

\eqalign{ \operatorname{Var}(\hat{\mu}_X) &= \mathbb{E}\left(\hat{\mu}_X^2\right)\\ &= \mathbb{E}\left({\frac {1}{T}}\int _{0}^{T}\mathbb{E}(X(t))\,\mathrm{d}t \ {\frac {1}{T}}\int _{0}^{T}\mathbb{E}(X(s))\,\mathrm{d}s \right) \\ &= \left(\frac {1}{T}\right)^2 \int_0^T \int_0^T \mathbb{E}(X(t)X(s))\,\mathrm{d}t \mathrm{d}s \\ &= \left(\frac {1}{T}\right)^2 \int_0^T \int_0^T \min(s,t)\,\mathrm{d}t \mathrm{d}s \\ &= \left(\frac {1}{T}\right)^2 \int_0^T \left(\int_0^s t\,\mathrm{d}t + \int_s^T s\,\mathrm{d}t\right)\mathrm{d}s \\ &= \left(\frac {1}{T}\right)^2 \int_0^T \left(\frac{s^2}{2} + (T-s)s\right)\mathrm{d}s \\ &= \left(\frac {1}{T}\right)^2 \frac{T^3}{3} \\ &= \frac{T}{3}. }

Because this grows ever larger as $$T$$ grows, $$\hat\mu_X$$ cannot possibly converge to a constant as required by the definition of ergodicity--even though it has a constant average of zero. Whence Wikipedia writes (to quote the passage fully),

An unbiased random walk is non-ergodic. Its expectation value is zero at all times, whereas its time average is a random variable with divergent variance.

• The analysis for the discrete (Binomial) random walk described in the question is identical: merely replace the integrals by sums.
– whuber
Dec 19, 2019 at 17:04
• Can you please explain how we get $\int \int \Bbb{E}(X(t)X(s)) dt ds = \int \int \min(t,s) dt ds$ Dec 19, 2019 at 17:54
• Thanks. One thing is still unclear to me. If we consider each step as +1$ or -1$ (dollars, money). The average or expected value will be defined slightly different, no? For ensemble it will be the average over the ensemble, but for single realisation it will be just the final value X(N) (we don't care about the process, only how much money we have in the end) - and the calculations for both will be the same sum(X_i, 1..N)/N? And the process will be ergodic, no? Dec 19, 2019 at 17:57
• It don't follow that, Alexey (aka Alex Craft), because the definition of the expectation isn't at issue and applies to any random variable whatsoever. In a single realization there is no such thing as an expectation, but there is a time average.
– whuber
Dec 19, 2019 at 18:24
• @kasa (aka honeybadger) This is a basic property of Brownian motion. Part of the definition of Brownian motion is that the increment $X(t)-X(s)$ (for $t\gt s$) is independent of $X(s).$ It follows immediately that the covariance of $X(s)$ and $X(t)$ equals the variance of $X(s).$ Another defining property of Brownian motion is that the variance of $X(s)$ equals $s.$ The result follows.
– whuber
Dec 19, 2019 at 18:26