The Fourier Symbol of a Simple Symmetric Walk

The One-Step Fourier Symbol

A nearest-neighbor walk on the integer lattice has a simple frequency description: each possible step contributes a complex exponential, and opposite steps combine into cosine terms. The resulting function is the walk’s Fourier symbol. It records how the one-step transition operator acts on oscillating functions of the state. Here we derive the symbol and determine precisely which frequencies make its value equal to one.

Fix an integer $d\ge1$. Let $e_1,\ldots,e_d$ denote the standard coordinate vectors in $\mathbb{Z}^d$. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $Z_1,Z_2,\ldots$ be independent random vectors, each taking each of the $2d$ values $e_1,-e_1,\ldots,e_d,-e_d$ with probability $1/(2d)$. Define the discrete-time process $X_n=\sum_{r=1}^n Z_r$ for $n\ge1$, with $X_0=0$. Its state space is $S=\mathbb{Z}^d$. From any state, there are $2d$ possible next states, each with probability $1/(2d)$, so each transition row sums to $2d\cdot 1/(2d)=1$.

Definition: For a frequency vector $\theta=(\theta_1,\ldots,\theta_d)\in\mathbb{R}^d$, the Fourier symbol of this walk is the characteristic function of one step, $$ \phi(\theta)=\mathbb{E}\!\left[e^{i\theta\cdot Z_1}\right], $$ where $\theta\cdot z=\sum_{j=1}^d\theta_jz_j$. Frequencies that differ by a vector in $(2\pi\mathbb{Z})^d$ give the same value, so one can also regard $\phi$ as a function on the frequency torus $\mathbb{R}^d/(2\pi\mathbb{Z})^d$.

The characteristic function can be calculated by summing over all possible steps. The contributions from $e_j$ and $-e_j$ are $e^{i\theta_j}$ and $e^{-i\theta_j}$. Their sum is $2\cos(\theta_j)$. Thus the symbol is real-valued even though it is defined using complex exponentials.

\begin{aligned} \phi(\theta) &=\frac{1}{2d}\sum_{j=1}^d\left(e^{i\theta_j}+e^{-i\theta_j}\right)\\ &=\frac{1}{2d}\sum_{j=1}^d 2\cos(\theta_j) =\frac{1}{d}\sum_{j=1}^d\cos(\theta_j). \end{aligned}

This calculation proves the formula for every integer $d\ge1$ and every $\theta\in\mathbb{R}^d$: each of the $2d$ possible steps has probability $1/(2d)$, and the terms for each coordinate pair combine as shown. Since each cosine lies in $[-1,1]$, the average satisfies $-1\le\phi(\theta)\le1$.

Why the Symbol Acts Like an Eigenvalue

For a function $f:\mathbb{Z}^d\to\mathbb{C}$, the one-step transition operator is defined by averaging the function over the possible next states: $$ (Pf)(x)=\frac{1}{2d}\sum_{j=1}^d\bigl(f(x+e_j)+f(x-e_j)\bigr). $$ $$ $$

For each frequency $\theta$, define the plane wave $f_\theta(x)=e^{i\theta\cdot x}$. Substituting this function into the transition operator gives a precise connection between the symbol and the walk.

Proposition: For every $x\in\mathbb{Z}^d$ and $\theta\in\mathbb{R}^d$, $Pf_\theta(x)=\phi(\theta)f_\theta(x)$. Thus the Fourier symbol is the eigenvalue of the transition operator associated with the plane wave $f_\theta$.

Proof. For each coordinate $j$, $f_\theta(x+e_j)=e^{i\theta\cdot x}e^{i\theta_j}$ and $f_\theta(x-e_j)=e^{i\theta\cdot x}e^{-i\theta_j}$. Consequently, $$ \begin{aligned} (Pf_\theta)(x) &=\frac{1}{2d}\sum_{j=1}^d e^{i\theta\cdot x} \left(e^{i\theta_j}+e^{-i\theta_j}\right)\\ &=e^{i\theta\cdot x}\frac{1}{d}\sum_{j=1}^d\cos(\theta_j) =f_\theta(x)\phi(\theta), \end{aligned} $$ using the formula for $\phi$. This is the claimed eigenvalue identity. $\square$

The same one-step calculation describes the characteristic function of the position after $n$ steps. Independence of the increments gives $\mathbb{E}[e^{i\theta\cdot X_n}]=\prod_{r=1}^n\mathbb{E}[e^{i\theta\cdot Z_r}]$, and each factor equals $\phi(\theta)$. Therefore $$ \mathbb{E}[e^{i\theta\cdot X_n}]=\phi(\theta)^n. $$ This identity uses independent increments; it is not an assertion that the one-step symbol is itself a distribution of the position at every time.

Worked Example: Evaluating the Symbol in Two Dimensions

Take $d=2$ and $\theta=(0,\pi/2)$. The chain has four possible next states from each state, each with probability $1/4$, and the transition row sums to $4\cdot1/4=1$. The formula gives $$ \phi(0,\pi/2)=\frac{\cos(0)+\cos(\pi/2)}{2} =\frac{1+0}{2}=\frac12. $$ The intermediate cosine values are $\cos(0)=1$ and $\cos(\pi/2)=0$. As an eigenvalue check, the plane wave $f_\theta(x)=e^{i\theta\cdot x}$ satisfies $Pf_\theta(x)=\tfrac12 f_\theta(x)$ at every $x$, by the proposition.

Check: Directly summing the four one-step exponential contributions gives $\tfrac14(1+1+i-i)=\tfrac12$, the same value. The two contributions $i$ and $-i$ cancel.

Exactly Where the Symbol Equals One

Theorem: For $\theta\in\mathbb{R}^d$, $$ \phi(\theta)=1 \quad\Longleftrightarrow\quad \theta_j\in2\pi\mathbb{Z}\ \text{for every }j=1,\ldots,d. $$ Equivalently, on the frequency torus $\mathbb{R}^d/(2\pi\mathbb{Z})^d$, the symbol equals one only at the class of the zero vector.

Proof. By the formula for the symbol, $$ 1-\phi(\theta)=\frac{1}{d}\sum_{j=1}^d\bigl(1-\cos(\theta_j)\bigr). $$ Every summand is nonnegative because $\cos(\theta_j)\le1$. If $\phi(\theta)=1$, the sum of these nonnegative terms is zero. Each term must therefore be zero: if any one were positive, the whole sum would be positive. Hence $\cos(\theta_j)=1$ for every $j$. The identity $1-\cos(u)=2\sin^2(u/2)$ shows that $\cos(u)=1$ exactly when $u/2\in\pi\mathbb{Z}$, or $u\in2\pi\mathbb{Z}$. This proves the forward implication. Conversely, if every $\theta_j\in2\pi\mathbb{Z}$, then every cosine is one, so their average is one. The torus statement follows because vectors differing coordinatewise by multiples of $2\pi$ represent the same frequency. $\square$

The nonnegativity argument is important: it rules out the possibility that one coordinate’s cosine being below one is “balanced” by another coordinate. No cosine can exceed one, so such compensation cannot occur. The conclusion concerns equality with $1$; it does not say that other special values, such as $-1$, have the same set of frequencies.

Worked Example: Testing a Frequency in Three Dimensions

Take $d=3$ and $\theta=(2\pi,-4\pi,0)$. From every state there are six possible next states, each with probability $1/6$; the row sum is $6\cdot1/6=1$. Evaluate each term separately: $$ \cos(2\pi)=1,\qquad \cos(-4\pi)=1,\qquad \cos(0)=1. $$ Therefore $$ \phi(2\pi,-4\pi,0)=\frac{1+1+1}{3}=1. $$ Each coordinate is an integer multiple of $2\pi$, as required by the theorem.

Check: The plane wave is constant on the lattice at this frequency: for $x\in\mathbb{Z}^3$, $f_\theta(x)=e^{i(2\pi x_1-4\pi x_2)}=1$. Averaging a constant over the six possible next states leaves it unchanged, so $Pf_\theta=f_\theta$, consistent with eigenvalue one.

Worked Example: A Frequency That Does Not Give One

Take $d=4$ and $\theta=(\pi,0,\pi/3,2\pi/3)$. From each state there are eight next states, each with probability $1/8$, and $8\cdot1/8=1$. Evaluate the four cosines: $$ \cos(\pi)=-1,\qquad \cos(0)=1,\qquad \cos(\pi/3)=\frac12,\qquad \cos(2\pi/3)=-\frac12. $$ Their sum is $-1+1+\tfrac12-\tfrac12=0$, so $$ \phi(\pi,0,\pi/3,2\pi/3)=\frac{0}{4}=0. $$ In particular, this frequency does not satisfy the equality condition: its first coordinate is $\pi$, not an integer multiple of $2\pi$.

Check: The four paired contributions in the exponential formula sum to $2(-1+1+\tfrac12-\tfrac12)=0$. Dividing by $2d=8$ gives zero again.

Worked Example: Equality on a Fundamental Frequency Box

Use the representative box $[-\pi,\pi]^2$ for frequencies in two dimensions. From each lattice state, the four transitions have probabilities $1/4$, whose sum is one. The theorem says that equality with one requires both coordinates to be in $2\pi\mathbb{Z}$. The only such coordinate in the interval $[-\pi,\pi]$ is $0$. Thus within this box the only point with $\phi(\theta)=1$ is $(0,0)$.

At that point, $\cos(0)=1$ in both coordinates, and $\phi(0,0)=(1+1)/2=1$. At the boundary point $(\pi,0)$, the coordinate cosines are $\cos(\pi)=-1$ and $\cos(0)=1$, giving $\phi(\pi,0)=(-1+1)/2=0$, not one. Although the box’s opposite boundary faces represent the same torus frequencies, neither boundary coordinate $\pi$ nor $-\pi$ represents zero modulo $2\pi$.

Check: The sole candidate $(0,0)$ satisfies the condition coordinatewise, and the explicitly evaluated boundary point does not. The result is an exact characterization, not just a test of these two points.

Reading the Equality Condition Correctly

The equality set can be understood in two equivalent ways. In $\mathbb{R}^d$, it is the lattice of frequency vectors $(2\pi k_1,\ldots,2\pi k_d)$ with integers $k_1,\ldots,k_d$. When frequencies are identified modulo $2\pi$ in each coordinate, all those vectors are a single point: the zero frequency on the torus. This distinction matters when plotting or integrating the symbol, since a frequency box may use different representatives for the same torus point.

There is also a direct operator interpretation. At a frequency where $\phi(\theta)=1$, the plane wave is unchanged by one application of the transition operator: $Pf_\theta=f_\theta$. Conversely, the theorem identifies exactly which plane waves have eigenvalue one. In particular, the constant function corresponds to the zero frequency and is unchanged by averaging over the possible next states.

Common mistake. It is incorrect to infer that an average of cosines equals one merely because some of its terms equal one. For instance, in dimension two at $\theta=(\pi,0)$, one cosine is $1$, but the other is $-1$, so the average is $(-1+1)/2=0$, not $1$. The correct test is that every coordinate cosine must equal one. The proof works because each deficit $1-\cos(\theta_j)$ is nonnegative and their sum can vanish only if every deficit vanishes.

Check Your Understanding

For each question, use the exact symbol formula and distinguish frequencies in $\mathbb{R}^d$ from their torus classes.

Derive the symbol in dimension $d=1$ directly from the two possible steps.
Evaluate $\phi(\pi,0)$ for $d=2$, showing each cosine and the final average.
In dimension $d=3$, determine whether $\theta=(0,2\pi,\pi)$ gives $\phi(\theta)=1$. Justify your answer using the equality theorem.
Why can no coordinate with cosine strictly less than one be offset by another coordinate when testing whether $\phi(\theta)=1$?
Explain why $(2\pi,0)$ and $(0,0)$ are distinct vectors in $\mathbb{R}^2$ but represent the same frequency on the torus.