One Step at a Time on the Integer Lattice
A nearest-neighbor walk moves by one lattice unit at each step. Its rule is local, but the state records the full position, so repeated steps can carry the walk far from its starting point. A key distinction is already present at time zero: a walk started at the origin is there with probability one, but this is not a return. A return requires at least one step away in time.
Fix a positive integer \(d\). The state space is \(\mathbb{Z}^d\), the set of integer vectors with \(d\) coordinates. Let \(e_r\) be the vector whose \(r\)th coordinate is \(1\) and whose other coordinates are \(0\), for \(r=1,\ldots,d\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), take independent random vectors \((\xi_n)_{n\ge1}\), each uniformly distributed over the \(2d\) vectors \(e_1,-e_1,\ldots,e_d,-e_d\). For a fixed starting state \(x\in\mathbb{Z}^d\), define \(X_0=x\) and \(X_n=x+\sum_{k=1}^n \xi_k\) for \(n\ge1\). The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\).
The word “symmetric” refers to the equal probabilities of a step and its opposite. It does not mean that the coordinates move independently at a given step. In fact, exactly one coordinate changes at each step. The increments are independent across different times, but the coordinate components of a single increment are dependent.
Coordinate Increments and the Transition Rule
Write \(\xi_{n,r}\) for coordinate \(r\) of increment \(\xi_n\). For each fixed \(r\), this coordinate is \(1\) with probability \(1/(2d)\), \(-1\) with probability \(1/(2d)\), and \(0\) with probability \((d-1)/d\). The last probability accounts for all steps in the other \(d-1\) coordinate directions. Thus \(X_{n,r}=x_r+\sum_{k=1}^n \xi_{k,r}\).
Proof. Given \(\mathcal{F}_n\), the position \(X_n\) is known, while \(\xi_{n+1}\) is independent of \(\xi_1,\ldots,\xi_n\) and hence independent of \(\mathcal{F}_n\). Since \(X_{n+1}=X_n+\xi_{n+1}\), if \(X_n=x\), then \(X_{n+1}=y\) exactly when \(\xi_{n+1}=y-x\). This event has probability \(1/(2d)\) when \(y-x\) is one of the \(2d\) allowed increments and probability \(0\) otherwise. The resulting conditional distribution depends only on the current state \(x\), which is the Markov property, and the formula is independent of \(n\), which gives time homogeneity. For each fixed \(x\), there are exactly \(2d\) distinct neighbors, each with probability \(1/(2d)\); all other states have probability zero. Therefore \(\sum_{y\in\mathbb{Z}^d}p_{xy}=2d\cdot 1/(2d)=1\). \(\square\)
The coordinate increments have a useful moment description. Their means are zero because the probabilities of \(1\) and \(-1\) agree. Each coordinate has variance \(1/d\), since its squared value is \(1\) for either of the two steps along that coordinate and \(0\) otherwise. Distinct coordinate increments have covariance zero: they cannot both be nonzero in the same step, and each has mean zero. Zero covariance here does not imply independence.
Proof. For a fixed coordinate \(r\), its distribution gives \(\mathbb{E}[\xi_{n,r}]=1\cdot(1/(2d))+(-1)\cdot(1/(2d))+0\cdot((d-1)/d)=0\). Also, \(\mathbb{E}[\xi_{n,r}^2]=1\cdot(1/(2d))+1\cdot(1/(2d))=1/d\). The variance is this second moment minus the square of the mean, so \(\operatorname{Var}(\xi_{n,r})=1/d\). If \(r\ne s\), then \(\xi_{n,r}\xi_{n,s}=0\) for every possible increment, because only one coordinate can be nonzero. Consequently, \(\operatorname{Cov}(\xi_{n,r},\xi_{n,s})=\mathbb{E}[\xi_{n,r}\xi_{n,s}]-\mathbb{E}[\xi_{n,r}]\mathbb{E}[\xi_{n,s}]=0-0=0\). Finally, increments at distinct times are independent by their construction. \(\square\)
Worked Example: The One-Dimensional Walk
Take \(d=1\) and start at \(X_0=0\). The two allowed increments are \(+1\) and \(-1\), each with probability \(1/2\). The only states reachable in one step are \(1\) and \(-1\), with transition probabilities \(p_{0,1}=1/2\) and \(p_{0,-1}=1/2\). Their probabilities sum to \(1/2+1/2=1\).
The increment has mean \((1)(1/2)+(-1)(1/2)=0\), and variance \((1^2)(1/2)+((-1)^2)(1/2)-0^2=1\). In two steps, a return to \(0\) occurs if the first step is \(+1\) and the second is \(-1\), or if the first is \(-1\) and the second is \(+1\). These disjoint possibilities each have probability \((1/2)(1/2)=1/4\), so the probability of a return in exactly two steps is \(1/4+1/4=1/2\).
Check: The two return paths have total probability \(2(1/4)=1/2\). The other two possible two-step increment sequences, \((+1,+1)\) and \((-1,-1)\), end at \(2\) and \(-2\), respectively, so they do not return to \(0\).
Worked Example: Coordinate Dependence in Two Dimensions
Take \(d=2\). The four increments \((1,0),(-1,0),(0,1),(0,-1)\) each have probability \(1/4\), so the total probability is \(4(1/4)=1\). For the first coordinate, the probabilities of \(1,-1,0\) are \(1/4,1/4,1/2\), respectively. Its mean is \(1(1/4)-1(1/4)+0(1/2)=0\), and its variance is \(1^2(1/4)+(-1)^2(1/4)-0^2=1/2\). The second coordinate has the same distribution and variance.
Let \(A\) be the event that the first coordinate increment is nonzero, and \(B\) the event that the second coordinate increment is nonzero. Then \(\mathbb{P}(A)=1/2\), \(\mathbb{P}(B)=1/2\), and \(\mathbb{P}(A\cap B)=0\), because one step cannot change both coordinates. If the coordinates were independent, the intersection probability would be \(\mathbb{P}(A)\mathbb{P}(B)=(1/2)(1/2)=1/4\), which is not zero. They are therefore dependent, despite having covariance zero.
Check: The product of the two coordinate increments is zero for all four possible steps, so its expectation is \(0\). Since both coordinate means are \(0\), their covariance is \(0-0\cdot0=0\), consistent with the proposition and not a claim of independence.
The Return Time Is a Positive-Time Quantity
For a walk started at the origin, \(\mathbb{P}_0(X_0=0)=1\) by definition of its starting state. That fact is not a return. Define the first positive-time return to the origin by \(T_0^+=\inf\{n\ge1:X_n=0\}\), with \(\inf\varnothing=\infty\). This random time is \(+\infty\) on paths that never return. In contrast, the first time in the set \(\{0\}\) under the convention \(T_{\{0\}}=\inf\{n\ge0:X_n=0\}\) is \(0\) when \(X_0=0\).
Proof. Every allowed increment is a nonzero vector, so \(X_1=\xi_1\ne0\) with probability one. Thus the walk cannot return at time \(1\). For a return at time \(2\), the second increment must be the negative of the first: \(X_2=\xi_1+\xi_2=0\) exactly when \(\xi_2=-\xi_1\). For each of the \(2d\) possible values of \(\xi_1\), the independent increment \(\xi_2\) equals its negative with probability \(1/(2d)\). Summing over the possible first increments gives \(\mathbb{P}_0(X_2=0)=\sum_{v\in\{\pm e_1,\ldots,\pm e_d\}}\mathbb{P}(\xi_1=v)\mathbb{P}(\xi_2=-v)=2d\cdot(1/(2d))\cdot(1/(2d))=1/(2d)\). Since there is no return at time \(1\), being at \(0\) at time \(2\) is exactly the event \(T_0^+=2\). \(\square\)
Worked Example: The First Two Steps in Three Dimensions
Take \(d=3\), start at \(0\), and consider the six possible increments \(\pm e_1,\pm e_2,\pm e_3\). Each has probability \(1/6\), and the total probability is \(6(1/6)=1\). A return at time \(1\) is impossible because none of these increments is zero.
For each of the six choices of the first increment, exactly one of the six equally likely second increments reverses it. Each ordered pair consisting of a first increment and its reversal has probability \((1/6)(1/6)=1/36\). There are six such pairs, so \(\mathbb{P}_0(T_0^+=2)=6(1/36)=1/6\). For instance, the path \(0,e_1,0\) has probability \(1/36\), and the same probability applies to each of the other five reversing paths.
Check: The six reversing pairs are disjoint events, so their probabilities add to \(6/36=1/6\), agreeing with \(1/(2d)=1/(2\cdot3)=1/6\). The walk's presence at the origin at time zero still has probability \(1\); it is a separate event from a positive-time return.
Common Mistake: Counting Time Zero as a Return
A tempting but incorrect calculation is to define the return time as \(\inf\{n\ge0:X_n=0\}\) for a walk started at \(0\), then conclude that the return time is \(0\) with probability one. The calculation is correct for the first hitting time under that definition, but that quantity records the initial visit, not a return. The correction is to impose \(n\ge1\) in the return-time definition: \(T_0^+=\inf\{n\ge1:X_n=0\}\). For example, in the three-dimensional walk, \(\mathbb{P}_0(X_0=0)=1\), whereas \(\mathbb{P}_0(T_0^+=2)=1/6\) and \(\mathbb{P}_0(T_0^+=1)=0\). These probabilities answer different questions and must not be interchanged.
The return time is a random variable that can take the value \(\infty\); the two-step calculation does not by itself determine whether the walk eventually returns. It gives one specific part of the return-time distribution. Higher-time return probabilities require accounting for more possible sequences of increments, a separate calculation from the one-step transition rule. Keeping the definitions distinct makes it possible to ask those later questions without mistaking the certain initial position for evidence of a return.
Check Your Understanding
Use the increment definition and the positive-time return convention in each question.
- For \(d=4\), what is the probability of each one-step move, and what is the sum of the probabilities of all allowed moves?
- For a single coordinate of a walk on \(\mathbb{Z}^d\), calculate the probabilities of increments \(1,-1,0\).
- Why can coordinate increments at the same time have covariance zero without being independent?
- Starting at the origin, what are \(\mathbb{P}_0(X_0=0)\) and \(\mathbb{P}_0(T_0^+=1)\)? Explain why they differ.
- Use the two-step return formula to find \(\mathbb{P}_0(T_0^+=2)\) when \(d=5\), and verify it by counting the possible first increments and their reversals.