interpretation of question on simple random walk on lattice

Question

Exercise 1.17 here is:

Let $S_n$ denote a $d$-dimensional simple random walk and let $R_n^1,\ldots,R_n^d$ denote the number of steps taken in each of the $d$ components. Show that for all $n>0$, the probability that $R_{2n}^1,\ldots,R_{2n}^d$ are all even is $2^{−(d−1)}$.

Is this a counterexample? Let $d=3,n=1,$ i.e., $2$ steps on the simple random walk on a 3-d lattice. For the event in question to hold, both steps must be on the same component, $x$ or $y$ or $z,$ which can happen in 3 ways. There are a total of $3^2=9$ ways to choose a component in two steps. Giving a probability of $1/3.$

Answer 1

You are right. The statement is not true if the random walk is started at $0$. For instance, when $d = 3$ the corresponding probability for $n = 1, 2, 3, \cdots$ are given by

\begin{array}{|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \frac{1}{3} & \frac{7}{27} & \frac{61}{243} & \frac{547}{2187} & \frac{4921}{19683} & \frac{44287}{177147} & \frac{398581}{1594323} \\ \hline \end{array}

But wait, if we compute numerical values of these probabilities, then we get

\begin{array}{|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0.3333 & 0.2593 & 0.2510 & 0.2501 & 0.2500 & 0.2500 & 0.2500 \\ \hline \end{array}

Thus one possible correction of the statement is as follows:

$$\lim_{n\to\infty}\mathbb{P}\left[ R_{2n}^1, \cdots, R_{2n}^d \text{ are all even} \right] = 2^{-(d-1)}. $$

Here is an explanation of this claim: Define

$$\tilde{R}_n = (R_n^1 \text{ mod } 2, \cdots, R_n^d \text{ mod } 2 )$$

and notice that $(\tilde{R}_{2n})_{n\geq 0}$ is an irreducible Markov chain over

$$S = \{ (x_1, \cdots, x_d) \in (\mathbb{Z}/2\mathbb{Z})^d : x_1 + \cdots + x_d \equiv 0 \text{ (mod 2)} \}. $$

So this chain has a unique invariant distribution $\pi$. Moreover, it is easy to check that, by virtue of translation invariance, $\pi$ is the uniform distribution over $S$. Since $|S| = 2^{d-1}$, this implies that $\pi \equiv 2^{-(d-1)}$ and hence

$$ \mathbb{P} [ R_{2n}^1, \cdots, R_{2n}^d \text{ are all even} ] = \mathbb{P} [ \tilde{R}_{2n} = \mathbf{0} ] \xrightarrow[n\to\infty]{} \pi(\mathbf{0}) = 2^{-(d-1)}. $$

---

Addendum. The exact value turns out to be

\begin{align*} \mathbb{P} [ R_{2n}^1, \cdots, R_{2n}^d \text{ are all even} ] &= \sum_{\substack{k_1+\cdots+k_d=n \\ k_i \geq 0 }} \frac{(2n)!}{(2k_1)!\cdots(2k_d)!} \frac{1}{d^{2n}} \\ &=\frac{1}{2^d} \sum_{(x_1,\cdots,x_d)\in\{-1,1\}^d} \left( \frac{x_1 + \cdots + x_d}{d} \right)^{2n} \\ &= \frac{1}{2^{d-1}} \sum_{k=0}^{\lfloor d/2\rfloor} \binom{d}{k}\left(1 - \frac{2k}{d}\right)^{2n}. \end{align*}