Polygonal Interpolation of Random Walk Paths

From Discrete Steps to Continuous Paths

A random walk is naturally recorded at integer times, but questions about convergence to Brownian motion concern paths over an interval of continuous time. A standard way to bridge these descriptions is to connect successive scaled walk values by straight line segments. This polygonal interpolation produces a continuous path without changing any of the walk's values at the time grid. Its usefulness depends on how much it changes the original step path, so we will compute that difference exactly.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(\xi_k)_{k\ge1}$ be real-valued random variables and define the partial sums $S_0=0$ and $S_k=\sum_{j=1}^k \xi_j$ for $k\ge1$. For an integer $n\ge1$, the diffusively scaled step path is $W_n(t)=S_{\lfloor nt\rfloor}/\sqrt n$, for $t\ge0$. Its steps occur at times $k/n$. The associated polygonal path is denoted by $\widetilde W_n$.

Definition: For $k=\lfloor nt\rfloor$ and $r=nt-k$, define $\widetilde W_n(t)=\bigl(S_k+r\xi_{k+1}\bigr)/\sqrt n$. At a grid point $t=k/n$, we have $r=0$, so $\widetilde W_n(k/n)=W_n(k/n)=S_k/\sqrt n$. Between consecutive grid points, $\widetilde W_n$ is the linear function joining these shared endpoint values.

The two paths agree on the grid, but generally differ between grid points. On a fixed interval $[0,T]$, the uniform distance between two functions $f$ and $g$ is $d_T(f,g)=\sup_{0\le t\le T}|f(t)-g(t)|$. The interpolated path is continuous, so it belongs to $C[0,T]$, the space of continuous real-valued functions on $[0,T]$. The step path generally has jumps, so it is not itself an element of $C[0,T]$. Its distance from the interpolation can still be measured by the same supremum.

The Exact Interpolation Error

Proposition: Let $T\ge0$, $m=\lfloor nT\rfloor$, and $\theta=nT-m$. Then $$ d_T(W_n,\widetilde W_n)=\frac{1}{\sqrt n}\max\left(\{|\xi_j|:1\le j\le m\}\cup\{\theta|\xi_{m+1}|\text{ if }\theta>0\}\right), $$ where the maximum of an empty set of contributions is defined to be $0$. In particular, if $nT$ is an integer, the distance is $\max_{1\le j\le m}|\xi_j|/\sqrt n$, with value $0$ when $m=0$.

Proof. On the grid interval from $k/n$ up to but not including $(k+1)/n$, write $r=nt-k$. Then $0\le r<1$, $W_n(t)=S_k/\sqrt n$, and $\widetilde W_n(t)=(S_k+r\xi_{k+1})/\sqrt n$. Their absolute difference is $r|\xi_{k+1}|/\sqrt n$. For each complete grid interval contained in $[0,T]$, namely $k=0,\ldots,m-1$, the supremum of this difference over the interval is $|\xi_{k+1}|/\sqrt n$: as $r$ increases towards $1$, the difference approaches this value. At the right endpoint the paths agree again, but that does not change the supremum. If $\theta>0$, the remaining partial interval has $k=m$ and $0\le r\le\theta$, so its largest difference is $\theta|\xi_{m+1}|/\sqrt n$, attained at $t=T$. If $\theta=0$, there is no partial interval. Taking the largest contribution gives the stated formula. When $T=0$, there are no intervals and the distance is $0$, as the empty-set convention specifies. $\square$

This formula distinguishes a complete interval from a truncated one. On a complete interval, the supremum captures the full increment, even though the paths meet at the right endpoint. On a final partial interval, only the corresponding fraction of the increment has been traversed. Thus the simple upper bound by the largest increment encountered is valid, but it need not be an equality if the final interval is partial.

Worked Example: A Fractional Final Interval

Take $n=2$, $T=5/4$, and a sample path with increments $(\xi_1,\xi_2,\xi_3)=(0,0,1)$. Here $nT=2(5/4)=5/2$, so $m=2$ and $\theta=5/2-2=1/2$. The two complete intervals contribute $|\xi_1|=0$ and $|\xi_2|=0$; the partial interval contributes $\theta|\xi_3|=(1/2)(1)=1/2$. Therefore

d_T(W_2,\widetilde W_2)=\frac{1}{\sqrt2}\max(0,0,1/2)=\frac{1}{2\sqrt2}.

To check directly, $S_2=0$, so $W_2(5/4)=0$. At $T=5/4$, the interpolation has traversed the fraction $2T-2=1/2$ of the third increment, giving $\widetilde W_2(5/4)=(0+(1/2)(1))/\sqrt2=1/(2\sqrt2)$. On the earlier two intervals both paths are zero. The direct supremum therefore agrees with the formula.

Worked Example: A Complete Time Interval

Let $n=3$, $T=1$, and take increments $(\xi_1,\xi_2,\xi_3)=(1,-1,1)$. The partial sums are $S_0=0$, $S_1=1$, $S_2=1-1=0$, and $S_3=0+1=1$. Since $nT=3$, there are three complete intervals and no partial one. The proposition gives

d_1(W_3,\widetilde W_3)=\frac{\max(|1|,|-1|,|1|)}{\sqrt3}=\frac{1}{\sqrt3}.

For a direct check, on the first interval $0\le t<1/3$ the step path is $0$ and the interpolation is $3t/\sqrt3$, whose supremum difference is $1/\sqrt3$. On the second interval, writing $r=3t-1$, the step value is $1/\sqrt3$ and the interpolated value is $(1-r)/\sqrt3$, so the difference is $r/\sqrt3$, with supremum $1/\sqrt3$. On the third interval the step value is $0$, and the interpolation is $r/\sqrt3$, again with supremum $1/\sqrt3$. At $t=1$ the paths agree. The largest of these three suprema is exactly $1/\sqrt3$.

When the Error Vanishes

The exact formula reduces a pathwise comparison to a maximum of increments. A useful probabilistic conclusion follows when the increments are independent and identically distributed with mean $0$ and variance $1$, as in the standard diffusive scaling. The same argument works for any finite variance, though the normalization for a Brownian limit is usually chosen to give variance $1$.

Theorem: Suppose $(\xi_k)_{k\ge1}$ are independent and identically distributed, with $\mathbb{E}\xi_1=0$ and $\mathbb{E}\xi_1^2=1$. For every fixed $T\ge0$ and every $\varepsilon>0$, $$ \mathbb{P}\bigl(d_T(W_n,\widetilde W_n)>\varepsilon\bigr)\longrightarrow 0 \quad\text{as }n\to\infty. $$

Proof. Set $m=\lfloor nT\rfloor$ and $\theta=nT-m$. By the exact formula and $0\le\theta<1$, the event $d_T(W_n,\widetilde W_n)>\varepsilon$ is contained in the event $\max_{1\le j\le m+1}|\xi_j|>\varepsilon\sqrt n$. This also gives a valid bound when $\theta=0$, since including the unused increment $\xi_{m+1}$ can only enlarge the event. The union bound and identical distributions yield $$ \mathbb{P}\bigl(d_T(W_n,\widetilde W_n)>\varepsilon\bigr) \le (m+1)\mathbb{P}(|\xi_1|>\varepsilon\sqrt n) \le (nT+1)\mathbb{P}(|\xi_1|>\varepsilon\sqrt n). $$ On the event $\{|\xi_1|>\varepsilon\sqrt n\}$, we have $1<\xi_1^2/(\varepsilon^2 n)$. Hence $$ (nT+1)\mathbb{P}(|\xi_1|>\varepsilon\sqrt n) \le \frac{T+1/n}{\varepsilon^2}\, \mathbb{E}\!\left[\xi_1^2\mathbf{1}_{\{|\xi_1|>\varepsilon\sqrt n\}}\right]. $$ Because $\mathbb{E}\xi_1^2=1<\infty$, the expectation on the right tends to zero: its integrand is bounded by the integrable random variable $\xi_1^2$ and tends pointwise to zero. Also $T+1/n$ is bounded as $n$ grows. The displayed probability therefore tends to zero, proving the assertion. $\square$

The conclusion is convergence in probability of the uniform interpolation error on each fixed interval. It is not a claim that the paths agree exactly, nor that the error is uniformly small over every possible time horizon. The fixed value of $T$ matters: the number of increments being compared grows with $nT$.

Worked Example: Bounded Increments Give a Deterministic Bound

Suppose the increments are independent and each takes the values $1$ and $-1$ with probability $1/2$. Their mean is $(1)(1/2)+(-1)(1/2)=0$, and their variance is $(1^2)(1/2)+((-1)^2)(1/2)=1$. For every sample path, $|\xi_j|=1$. On $[0,1]$, take $n=4$. There are four complete intervals, so the exact formula gives

d_1(W_4,\widetilde W_4)=\frac{\max(1,1,1,1)}{\sqrt4}=\frac12.

This is also checked interval by interval: the difference on interval $j$ has magnitude $r|\xi_j|/\sqrt4=r/2$, where $0\le r<1$, so its supremum is $1/2$. More generally, for these bounded increments and any fixed $T$, every contribution in the exact formula is at most $1/\sqrt n$, so $d_T(W_n,\widetilde W_n)\le1/\sqrt n$ for every sample path. This bound tends to zero without taking probabilities.

Why Interpolation Helps with Path Convergence

The earlier material on convergence at finitely many time points concerns vectors such as $(W_n(t_1),\ldots,W_n(t_q))$, where $q$ is fixed. Polygonal interpolation preserves the walk values at the grid points $k/n$, and the exact error calculation shows that it also changes the path by a quantity tending to zero in probability on each fixed $[0,T]$ under the finite-variance assumptions above. These facts make interpolation a useful step when studying whole paths: it provides continuous functions and a natural uniform metric, rather than only a collection of finite-dimensional vectors.

There is an important logical distinction. Convergence at each finite set of times does not by itself control the supremum over all times in an interval. The interpolation comparison addresses one specific issue—the difference between the step path and its continuous polygonal version. Additional control is needed to establish convergence of the polygonal paths themselves in the uniform path metric; the interpolation error alone does not supply that control.

Common pitfall: treating a partial interval as complete. In the first example, a careless calculation might take the largest increment among the first $\lceil nT\rceil=3$ increments and claim an error of $1/\sqrt2$. That treats the third increment as if the full third grid interval were included. But $nT=5/2$, so the path reaches only the fraction $1/2$ of that interval. The actual contribution is $(1/2)|\xi_3|/\sqrt2=1/(2\sqrt2)$, not $1/\sqrt2$. The exact formula keeps the fractional endpoint visible and prevents this overestimate from being mistaken for equality.

The finite second moment is also substantive for the probability conclusion. To see what can fail without it, let the increments be independent and symmetric, with $\mathbb{P}(|\xi_1|>x)=x^{-3/2}$ for $x\ge1$. For $T=1$, there are $n$ complete intervals and the exact error is $\max_{1\le j\le n}|\xi_j|/\sqrt n$. For fixed $\varepsilon>0$ and sufficiently large $n$, independence gives

\mathbb{P}\bigl(d_1(W_n,\widetilde W_n)>\varepsilon\bigr) =1-\left(1-\varepsilon^{-3/2}n^{-3/4}\right)^n.

The quantity $n\varepsilon^{-3/2}n^{-3/4}=\varepsilon^{-3/2}n^{1/4}$ tends to infinity, and $(1-p)^n\le e^{-np}$ for $0\le p\le1$. Thus the displayed probability tends to $1$, not $0$. In this example the finite-variance assumption fails, and the largest scaled increment does not become negligible.

Check Your Understanding

Use the exact error formula, keeping complete intervals and a possible partial interval separate.

For $n=4$, $T=3/4$, and increments $(2,-1,0)$, compute $m$, $\theta$, and $d_T(W_n,\widetilde W_n)$.
Why can a complete interval contribute $|\xi_j|/\sqrt n$ to a supremum even though the paths agree at both grid endpoints?
For a fixed $T$, explain which assumption in the theorem is used to make the tail expectation tend to zero.
For $nT$ an integer, write the exact interpolation-error formula and state what it gives when $T=0$.
Why does convergence of the interpolation error to zero in probability not, by itself, prove convergence of the interpolated paths in the uniform path metric?

Polygonal Interpolation of Random Walk Paths

What You'll Learn