From a Return Event to an Integral
A return probability asks whether the sum of a sequence of random integer-valued increments is exactly zero. Fourier inversion turns that exact lattice constraint into an integral: oscillating exponentials cancel at every nonzero lattice point and contribute one at the origin. Once this cancellation is established, independence makes the integrand a power of a single function, the characteristic function of one increment.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Fix an integer dimension \(d\ge1\), and let \((Y_k)_{k\ge1}\) be independent, identically distributed random vectors taking values in the state space \(S=\mathbb{Z}^d\). Write \(\nu(x)=\mathbb{P}(Y_1=x)\), so \(\nu(x)\ge0\) and \(\sum_{x\in\mathbb{Z}^d}\nu(x)=1\). Define the discrete-time walk by \(X_0=0\) and \(X_n=\sum_{k=1}^nY_k\) for \(n\ge1\). Its transition probabilities are \(p_{xy}=\nu(y-x)\); for each \(x\), \(\sum_{y\in\mathbb{Z}^d}p_{xy}=\sum_{z\in\mathbb{Z}^d}\nu(z)=1\). The \(n\)-step return probability is \(p_n(0)=\mathbb{P}(X_n=0)\), with \(p_0(0)=1\).
For \(\theta=(\theta_1,\ldots,\theta_d)\in[-\pi,\pi]^d\) and \(x=(x_1,\ldots,x_d)\in\mathbb{Z}^d\), write \(\theta\cdot x=\sum_{r=1}^d\theta_rx_r\). The characteristic function of one increment, in the convention used here, is \(\phi(\theta)=\mathbb{E}[e^{i\theta\cdot Y_1}]\). It is defined for every \(\theta\), since the integrand has absolute value one.
Proof. For an integer \(m\), the one-dimensional integral is \(1\) after division by \(2\pi\) when \(m=0\). When \(m\ne0\), direct integration gives $$ \frac{1}{2\pi}\int_{-\pi}^{\pi}e^{im\theta}\,d\theta =\frac{e^{im\pi}-e^{-im\pi}}{2\pi im}=0, $$ because \(e^{im\pi}=e^{-im\pi}=(-1)^m\). The \(d\)-dimensional integrand factors as \(\prod_{r=1}^d e^{i\theta_rx_r}\), and the cube is a product of the \(d\) intervals. The integral therefore factors into the product of the one-dimensional integrals. That product equals one if every coordinate \(x_r\) is zero and equals zero otherwise, which is exactly \(\mathbf{1}_{\{0\}}(x)\). \(\square\)
The Fourier Inversion Formula for Returns
Proof. Apply the lattice orthogonality identity to the random vector \(X_n\). For every outcome, the indicator of \(X_n=0\) equals the normalized integral of \(e^{i\theta\cdot X_n}\). Taking expectations gives $$ \mathbb{P}(X_n=0) =\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d} \mathbb{E}[e^{i\theta\cdot X_n}]\,d\theta. $$ The interchange of expectation and integration is valid: the absolute value of the integrand \(e^{i\theta\cdot X_n}\) is one, and the frequency cube has finite volume \((2\pi)^d\), so the integrand is absolutely integrable on the product of probability space and cube. For \(n\ge1\), the increments are independent and identically distributed, and \(X_n=Y_1+\cdots+Y_n\). Thus $$ \mathbb{E}[e^{i\theta\cdot X_n}] =\mathbb{E}\!\left[\prod_{k=1}^n e^{i\theta\cdot Y_k}\right] =\prod_{k=1}^n\mathbb{E}[e^{i\theta\cdot Y_k}] =\phi(\theta)^n. $$ For \(n=0\), \(X_0=0\), so the expectation in the integral is \(1\), which agrees with \(\phi^0\). Substitution proves the formula for every \(n\ge0\). \(\square\)
The formula needs no finite-support assumption, symmetry assumption, or moment assumption on the increments. The probability law only needs to be supported on \(\mathbb{Z}^d\), and the increments must be independent with the same distribution for the power \(\phi^n\) to follow. If increments are independent but have different laws, the same argument instead gives the product of their characteristic functions. The integral is normalized by the volume factor \((2\pi)^d\); this factor is part of the inversion identity, not an optional convention.
Worked Applications
Worked Example: A Lazy One-Dimensional Walk at Time Two
Let \(d=1\) and let one increment be \(+1\) with probability \(\tfrac14\), \(0\) with probability \(\tfrac12\), and \(-1\) with probability \(\tfrac14\). These probabilities sum to \(\tfrac14+\tfrac12+\tfrac14=1\), so the translation-invariant transition probabilities \(p_{xy}=\nu(y-x)\) sum to one in every row. Find \(p_2(0)\) directly and by Fourier inversion.
For a direct calculation, the two increments sum to zero either when both are zero or when they are opposite nonzero steps. The all-zero pair has probability \(\tfrac12\cdot\tfrac12=\tfrac14\). The ordered pairs \((+1,-1)\) and \((-1,+1)\) each have probability \(\tfrac14\cdot\tfrac14=\tfrac1{16}\). Hence $$ p_2(0)=\frac14+\frac1{16}+\frac1{16}=\frac38. $$ The one-step characteristic function is $$ \phi(\theta)=\frac14e^{i\theta}+\frac12+\frac14e^{-i\theta}. $$ In \(\phi(\theta)^2\), the constant terms come from multiplying exponentials whose exponents cancel. The product of the two constant terms contributes \((\tfrac12)^2=\tfrac14\). The two ordered products using \(e^{i\theta}\) and \(e^{-i\theta}\) contribute \(2(\tfrac14)(\tfrac14)=\tfrac18\). Every other term has a nonzero integer exponent and integrates to zero by lattice orthogonality. Therefore $$ \frac1{2\pi}\int_{-\pi}^{\pi}\phi(\theta)^2\,d\theta =\frac14+\frac18=\frac38. $$ This agrees with the direct path calculation.
Worked Example: A Two-Dimensional Walk with Unequal Step Probabilities
Let \(d=2\). At each step the walk moves by \((1,0)\) with probability \(\tfrac12\), by \((-1,0)\) with probability \(\tfrac14\), or by \((0,1)\) with probability \(\tfrac14\). The probabilities sum to \(\tfrac12+\tfrac14+\tfrac14=1\), and translation invariance gives a transition kernel whose rows each sum to one. Compute the probability of returning to the origin in two steps.
To return in two steps, the increments must be opposites. The only opposite pair in the support is \((1,0),(-1,0)\), in either order. Each ordered pair has probability \(\tfrac12\cdot\tfrac14=\tfrac18\), so $$ p_2(0)=\frac18+\frac18=\frac14. $$ The characteristic function is $$ \phi(\theta_1,\theta_2) =\frac12e^{i\theta_1}+\frac14e^{-i\theta_1} +\frac14e^{i\theta_2}. $$ In its square, the only terms with zero exponent in both coordinates are the two products pairing \(e^{i\theta_1}\) with \(e^{-i\theta_1}\). Their combined coefficient is \(2(\tfrac12)(\tfrac14)=\tfrac14\). All other terms integrate to zero: each has a nonzero integer exponent in at least one coordinate. Thus the normalized integral of \(\phi^2\) is \(\tfrac14\), again matching the path calculation.
Worked Example: A One-Sided Walk at Time Three
Let \(d=1\), with an increment equal to \(0\) with probability \(\tfrac23\) and \(+1\) with probability \(\tfrac13\). The probabilities sum to \(\tfrac23+\tfrac13=1\), so each row of the translation-invariant transition kernel sums to one. Find the probability of being at the origin after three steps.
All increments are nonnegative. Their sum is zero exactly when all three increments are zero, an event of probability $$ p_3(0)=\left(\frac23\right)^3=\frac8{27}. $$ Here \(\phi(\theta)=\tfrac23+\tfrac13e^{i\theta}\). Expanding its third power, a term with exponent zero occurs only by choosing the constant \(\tfrac23\) from all three factors. Its coefficient is \((\tfrac23)^3=\tfrac8{27}\); every other term is a multiple of \(e^{ik\theta}\) for an integer \(k\ge1\), and its normalized integral is zero. Hence Fourier inversion gives $$ \frac1{2\pi}\int_{-\pi}^{\pi} \left(\frac23+\frac13e^{i\theta}\right)^3\,d\theta =\frac8{27}, $$ which verifies the direct answer.
What the Formula Does—and Does Not—Say
The inversion step extracts the coefficient corresponding to displacement zero. More generally, applying the same orthogonality identity to \(X_n=x\) gives the exact point-probability formula $$ \mathbb{P}(X_n=x) =\frac{1}{(2\pi)^d}\int_{[-\pi,\pi]^d} e^{-i\theta\cdot x}\phi(\theta)^n\,d\theta, \qquad x\in\mathbb{Z}^d. $$ Indeed, the indicator of \(X_n=x\) is the normalized integral of \(e^{i\theta\cdot(X_n-x)}\), and independence again gives the factor \(\phi^n\). Setting \(x=0\) recovers the return formula. The sign in the extra exponential depends on the stated convention \(\phi(\theta)=\mathbb{E}[e^{i\theta\cdot Y_1}]\); at \(x=0\) there is no extra factor.
This exact representation is useful because it replaces a sum over all possible paths by an integral of a power. In later analysis, the behavior of \(\phi\) near particular frequencies can help explain the size of return probabilities. The inversion formula itself, however, is an identity for each fixed \(n\); it does not by itself assert an asymptotic approximation or a recurrence classification.
Common mistake: omitting the normalization. In the lazy-walk example, the constant term of \(\phi^2\) is \(\tfrac38\), and therefore $$ \int_{-\pi}^{\pi}\phi(\theta)^2\,d\theta =2\pi\left(\frac38\right)=\frac{3\pi}{4}. $$ A wrong calculation that identifies this unnormalized integral with \(p_2(0)\) would give \(\tfrac{3\pi}{4}\), not a valid probability. The correction is to divide by the interval length \(2\pi\), giving \(\tfrac{3\pi/4}{2\pi}=\tfrac38\). In dimension \(d\), the corresponding volume is \((2\pi)^d\), so the normalization is \((2\pi)^{-d}\).
Check Your Understanding
Use the stated convention for \(\phi\), and distinguish the increment law from the distribution of the position after several steps.
- For \(d=1\), suppose an increment is \(+1\) with probability \(\tfrac13\) and \(-1\) with probability \(\tfrac23\). Write \(\phi(\theta)\) and use the inversion formula to find \(p_2(0)\).
- Why does the proof require independent increments to replace \(\mathbb{E}[e^{i\theta\cdot X_n}]\) by \(\phi(\theta)^n\)?
- For a walk on \(\mathbb{Z}^2\), what is the value of the normalized integral of \(e^{i(2\theta_1-\theta_2)}\) over \([-\pi,\pi]^2\)?
- For the one-sided walk in the third worked example, what is \(p_2(0)\), and which terms of \(\phi(\theta)^2\) contribute to its integral?
- State the normalization factor in the inversion formula for a walk on \(\mathbb{Z}^d\), and explain what error results from omitting it.