[proofplan] We apply the [Recurrence Summability Criterion](/theorems/2211): the walk is recurrent iff $\sum_{n=0}^{\infty} p_{00}(n) = \infty$. Since the walk returns to the origin only at even times, we compute $p_{00}(2n)$ exactly via combinatorics for each dimension. For $d = 1$, a binomial count gives $p_{00}(2n) = \binom{2n}{n} 2^{-2n} \sim (\pi n)^{-1/2}$ by Stirling's approximation, and the series diverges. For $d = 2$, a multinomial count combined with the Vandermonde identity yields $p_{00}(2n) = [\binom{2n}{n} 2^{-2n}]^2 \sim (\pi n)^{-1}$, and the series still diverges. For $d = 3$, an upper bound via the maximum of the trinomial distribution gives $p_{00}(2n) \leq C n^{-3/2}$, and the series converges. The bound extends to all $d \geq 3$ by a monotonicity argument. [/proofplan]

[step:Observe that returns to the origin occur only at even times] The simple random walk on $\mathbb{Z}^d$ takes steps of $\pm 1$ in one coordinate at each time step, so each step changes the $\ell^1$-norm $\|X_n\|_1 = \sum_{k=1}^d |X_n^{(k)}|$ by exactly $\pm 1$. In particular, the parity of $\|X_n\|_1$ alternates at each step. Since $X_0 = 0$ has $\|X_0\|_1 = 0$ (even), the walk can only return to the origin at even times. Hence $p_{00}(2n+1) = 0$ for all $n \geq 0$, and \begin{align*} \sum_{n=0}^{\infty} p_{00}(n) = \sum_{n=0}^{\infty} p_{00}(2n). \end{align*} By the [Recurrence Summability Criterion](/theorems/2211), the walk is recurrent iff this sum diverges. [/step]

[step:Compute $p_{00}(2n)$ for $d = 1$ and show recurrence via Stirling's approximation]In $d = 1$, the walk takes steps $\pm 1$ each with probability $1/2$. To return to $0$ after $2n$ steps, the walk must take exactly $n$ steps in the $+1$ direction and $n$ steps in the $-1$ direction. The number of such paths is $\binom{2n}{n}$ (choosing which $n$ of the $2n$ steps are $+1$), and each path has probability $(1/2)^{2n}$. Therefore \begin{align*} p_{00}(2n) = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n} = \frac{(2n)!}{(n!)^2 \cdot 4^n}. \end{align*} Applying Stirling's approximation $n! \sim \sqrt{2\pi n}\,(n/e)^n$: \begin{align*} \binom{2n}{n} \cdot 4^{-n} = \frac{(2n)!}{(n!)^2 \cdot 4^n} \sim \frac{\sqrt{2\pi \cdot 2n}\,(2n/e)^{2n}}{2\pi n \cdot (n/e)^{2n} \cdot 4^n} = \frac{\sqrt{4\pi n} \cdot 4^n \cdot n^{2n}/e^{2n}}{2\pi n \cdot n^{2n}/e^{2n} \cdot 4^n} = \frac{1}{\sqrt{\pi n}}. \end{align*} Since $\sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \frac{1}{\sqrt{\pi}} \sum_{n=1}^{\infty} n^{-1/2} = \infty$ (the $p$-series with $p = 1/2 < 1$ diverges), we conclude $\sum_{n=0}^{\infty} p_{00}(2n) = \infty$. The one-dimensional walk is recurrent.[/step]

[guided]For the one-dimensional walk, returning to the origin after $2n$ steps requires an equal number of $+1$ and $-1$ steps. There are $\binom{2n}{n}$ ways to arrange $n$ steps of each type among $2n$ total steps, and each arrangement occurs with probability $(1/2)^{2n}$. To determine whether $\sum_n p_{00}(2n)$ diverges, we need the asymptotic behaviour of $\binom{2n}{n} 4^{-n}$. Stirling's formula $n! \sim \sqrt{2\pi n}\,(n/e)^n$ gives \begin{align*} (2n)! &\sim \sqrt{4\pi n}\,(2n/e)^{2n}, \\ (n!)^2 &\sim 2\pi n\,(n/e)^{2n}. \end{align*} Dividing and cancelling $4^n$: \begin{align*} \frac{(2n)!}{(n!)^2 \cdot 4^n} \sim \frac{\sqrt{4\pi n} \cdot (2n)^{2n}/e^{2n}}{2\pi n \cdot n^{2n}/e^{2n} \cdot 4^n} = \frac{\sqrt{4\pi n} \cdot 2^{2n} \cdot n^{2n}}{2\pi n \cdot n^{2n} \cdot 4^n} = \frac{2\sqrt{\pi n}}{2\pi n} = \frac{1}{\sqrt{\pi n}}. \end{align*} The series $\sum_{n=1}^{\infty} n^{-1/2}$ diverges (it is the $p$-series with exponent $p = 1/2 \leq 1$), so $\sum_n p_{00}(2n) = \infty$ and the walk is recurrent.[/guided]

[step:Compute $p_{00}(2n)$ for $d = 2$ using the Vandermonde identity and show recurrence]In $d = 2$, the walk takes steps in one of four directions (right, left, up, down), each with probability $1/4$. After $2n$ steps, let $r$ be the number of right steps, $\ell$ the number of left steps, $u$ the number of up steps, and $d$ the number of down steps, so $r + \ell + u + d = 2n$. Returning to the origin requires $r = \ell$ and $u = d$. Setting $r = \ell = m$ and $u = d = n - m$ (so $m$ ranges from $0$ to $n$): \begin{align*} p_{00}(2n) = \sum_{m=0}^{n} \frac{(2n)!}{m!\, m!\, (n-m)!\, (n-m)!} \cdot \left(\frac{1}{4}\right)^{2n}. \end{align*} We factor the multinomial coefficient. First extract the choice of which $2m$ of the $2n$ steps are horizontal (right or left) versus vertical (up or down): \begin{align*} \frac{(2n)!}{m!\, m!\, (n-m)!\, (n-m)!} = \binom{2n}{2m} \cdot \binom{2m}{m} \cdot \binom{2(n-m)}{n-m}. \end{align*} Therefore \begin{align*} p_{00}(2n) &= \left(\frac{1}{4}\right)^{2n} \sum_{m=0}^{n} \binom{2n}{2m}\, \binom{2m}{m}\, \binom{2(n-m)}{n-m}. \end{align*} We simplify using the identity $\binom{2n}{2m} \cdot \binom{2m}{m} = \binom{2n}{n} \cdot \binom{n}{m} \cdot \frac{(2n-2m)!}{(n-m)!^2} / \binom{2n-2m}{n-m}$. More directly, observe that \begin{align*} \frac{(2n)!}{(m!)^2 ((n-m)!)^2} = \frac{(2n)!}{(n!)^2} \cdot \frac{(n!)^2}{(m!)^2((n-m)!)^2} = \binom{2n}{n} \cdot \binom{n}{m}^2. \end{align*} Substituting: \begin{align*} p_{00}(2n) = \left(\frac{1}{4}\right)^{2n} \binom{2n}{n} \sum_{m=0}^{n} \binom{n}{m}^2. \end{align*} By the Vandermonde identity, $\sum_{m=0}^{n} \binom{n}{m}\binom{n}{n-m} = \binom{2n}{n}$. Since $\binom{n}{n-m} = \binom{n}{m}$, this gives $\sum_{m=0}^{n} \binom{n}{m}^2 = \binom{2n}{n}$. Therefore \begin{align*} p_{00}(2n) = \left(\frac{1}{4}\right)^{2n} \binom{2n}{n}^2 = \left[\binom{2n}{n} \left(\frac{1}{2}\right)^{2n}\right]^2 \sim \frac{1}{\pi n}, \end{align*} where the asymptotic follows from the $d = 1$ result $\binom{2n}{n} 2^{-2n} \sim (\pi n)^{-1/2}$. Since $\sum_{n=1}^{\infty} \frac{1}{\pi n} = \frac{1}{\pi} \sum_{n=1}^{\infty} n^{-1} = \infty$ (the harmonic series diverges), we have $\sum_n p_{00}(2n) = \infty$, and the two-dimensional walk is recurrent.[/step]

[guided]In two dimensions, we must count lattice paths that return to the origin. After $2n$ steps, returning to $(0,0)$ requires equal counts of right/left and up/down steps. Let $m$ be the number of right steps (equals the number of left steps), so there are $n - m$ up steps and $n - m$ down steps. The multinomial coefficient $\frac{(2n)!}{m!\, m!\, (n-m)!\, (n-m)!}$ counts the number of such arrangements. We rewrite it by factoring: \begin{align*} \frac{(2n)!}{(m!)^2 ((n-m)!)^2} = \frac{(2n)!}{(n!)^2} \cdot \frac{(n!)^2}{(m!)^2 ((n-m)!)^2} = \binom{2n}{n} \cdot \binom{n}{m}^2. \end{align*} The first factor $\binom{2n}{n}$ selects which $n$ of the $2n$ steps are "positive" (right or up); the second factor $\binom{n}{m}^2$ distributes among the horizontal and vertical axes. After summing over $m$ and applying the Vandermonde identity $\sum_{m=0}^{n} \binom{n}{m}^2 = \binom{2n}{n}$: \begin{align*} p_{00}(2n) = 4^{-2n} \binom{2n}{n}^2 = \left[\binom{2n}{n} 2^{-2n}\right]^2 \sim \left[\frac{1}{\sqrt{\pi n}}\right]^2 = \frac{1}{\pi n}. \end{align*} The $d = 2$ return probability decays like $1/n$, which is the borderline case: $\sum n^{-1} = \infty$ (harmonic series), so the walk is recurrent. The two-dimensional walk is recurrent, but only barely -- it returns to the origin, but the expected number of steps to do so is infinite (the walk is null recurrent).[/guided]

[step:Bound $p_{00}(2n)$ for $d = 3$ from above and show transience]In $d = 3$, the walk takes steps in one of six directions, each with probability $1/6$. After $2n$ steps, return to the origin requires equal numbers of $+$ and $-$ steps in each coordinate axis. Let $i, j, k \geq 0$ with $i + j + k = n$, where $i$ is the number of $+x$-steps (equal to the number of $-x$-steps), and similarly for $j$ and $k$. The return probability is \begin{align*} p_{00}(2n) = \left(\frac{1}{6}\right)^{2n} \sum_{\substack{i + j + k = n \\ i, j, k \geq 0}} \frac{(2n)!}{(i!)^2 (j!)^2 (k!)^2}. \end{align*} We rewrite the multinomial coefficient by extracting $\binom{2n}{n}$ and the trinomial coefficient: \begin{align*} \frac{(2n)!}{(i!)^2 (j!)^2 (k!)^2} = \binom{2n}{n} \cdot \left(\frac{n!}{i!\, j!\, k!}\right)^2, \end{align*} which can be verified by expanding: $\binom{2n}{n} \cdot (n!/(i!\,j!\,k!))^2 = \frac{(2n)!}{(n!)^2} \cdot \frac{(n!)^2}{(i!)^2(j!)^2(k!)^2} = \frac{(2n)!}{(i!)^2(j!)^2(k!)^2}$. Therefore \begin{align*} p_{00}(2n) = \left(\frac{1}{6}\right)^{2n} \binom{2n}{n} \sum_{i+j+k=n} \left(\frac{n!}{i!\,j!\,k!}\right)^2. \end{align*} Define the trinomial probabilities $q_{i,j,k} := \frac{n!}{3^n\, i!\, j!\, k!}$ for $i + j + k = n$. These satisfy $\sum_{i+j+k=n} q_{i,j,k} = 1$ (the trinomial distribution with equal probabilities $1/3$). Since $3^{2n} = 9^n$ and $6^{2n} = 36^n$, we can write \begin{align*} p_{00}(2n) = \binom{2n}{n} \cdot \frac{3^{2n}}{6^{2n}} \sum_{i+j+k=n} q_{i,j,k}^2 = \binom{2n}{n} \cdot 4^{-n} \cdot \frac{1}{2^n} \cdot 3^{2n} \cdot 6^{-2n} \cdot 3^{2n} \sum q_{i,j,k}^2. \end{align*} More cleanly: since $6^{2n} = 4^n \cdot 9^n$ we have $\binom{2n}{n}/6^{2n} = \binom{2n}{n} 4^{-n} / 9^n$, and \begin{align*} p_{00}(2n) = \binom{2n}{n} \cdot 2^{-2n} \cdot \sum_{i+j+k=n} q_{i,j,k}^2. \end{align*} We bound $\sum q_{i,j,k}^2 \leq \max_{i+j+k=n} q_{i,j,k} \cdot \sum q_{i,j,k} = \max_{i+j+k=n} q_{i,j,k}$. The maximum of the trinomial probability is attained when $i, j, k$ are as equal as possible. For $n$ divisible by $3$, the maximum is at $i = j = k = n/3$: \begin{align*} q_{n/3, n/3, n/3} = \frac{n!}{3^n\, ((n/3)!)^3}. \end{align*} Applying Stirling's approximation: $n! \sim \sqrt{2\pi n}(n/e)^n$ and $((n/3)!)^3 \sim (2\pi n/3)^{3/2}(n/(3e))^n$. Then \begin{align*} \frac{n!}{3^n ((n/3)!)^3} \sim \frac{\sqrt{2\pi n}\, n^n/e^n}{3^n \cdot (2\pi n/3)^{3/2} \cdot n^n/(3^n e^n)} = \frac{\sqrt{2\pi n}}{(2\pi n/3)^{3/2}} = \frac{\sqrt{2\pi n} \cdot 3^{3/2}}{(2\pi n)^{3/2}} = \frac{3\sqrt{3}}{2\pi n}. \end{align*} Combining with $\binom{2n}{n}\, 2^{-2n} \sim (\pi n)^{-1/2}$: \begin{align*} p_{00}(2n) \leq \binom{2n}{n}\, 2^{-2n} \cdot \max q_{i,j,k} \lesssim \frac{1}{\sqrt{\pi n}} \cdot \frac{3\sqrt{3}}{2\pi n} = \frac{3\sqrt{3}}{2\pi^{3/2}} \cdot n^{-3/2}. \end{align*} Therefore there exists a constant $C > 0$ such that $p_{00}(2n) \leq C\, n^{-3/2}$ for all $n \geq 1$. Since $\sum_{n=1}^{\infty} n^{-3/2} < \infty$ (the $p$-series with exponent $3/2 > 1$ converges), we conclude $\sum_n p_{00}(2n) < \infty$. The three-dimensional walk is transient.[/step]

[guided]The three-dimensional case requires an upper bound rather than an exact computation. The strategy is to express $p_{00}(2n)$ in terms of the trinomial distribution and bound the sum of squares by the maximum term. After setting up the multinomial count and extracting $\binom{2n}{n}$, we obtain \begin{align*} p_{00}(2n) = \binom{2n}{n} \cdot 2^{-2n} \cdot \sum_{i+j+k=n} q_{i,j,k}^2, \end{align*} where $q_{i,j,k} = n!/(3^n\, i!\, j!\, k!)$ are the trinomial probabilities (summing to $1$). Why bound $\sum q^2$ by $\max q$? Because $\sum q_{i,j,k}^2 \leq (\max q_{i,j,k}) \cdot \sum q_{i,j,k} = \max q_{i,j,k}$. This is a standard inequality: the $\ell^2$ norm squared of a probability vector is at most the $\ell^\infty$ norm. The maximum trinomial probability occurs at the mode $i \approx j \approx k \approx n/3$. Stirling's formula gives $\max q_{i,j,k} \sim \frac{3\sqrt{3}}{2\pi n}$, which decays like $n^{-1}$. Multiplied by $\binom{2n}{n} 2^{-2n} \sim (\pi n)^{-1/2}$, we get $p_{00}(2n) \lesssim n^{-3/2}$. The exponent $-3/2$ is critical: $\sum n^{-3/2} < \infty$ (convergent $p$-series), so the walk is transient. Compare with $d = 2$ where $p_{00}(2n) \sim n^{-1}$ and the harmonic series diverges -- the passage from recurrence to transience happens between $d = 2$ and $d = 3$.[/guided]

[step:Extend the transience bound to all $d \geq 3$ by comparison] For $d \geq 4$, the walk has $2d$ possible directions at each step, each with probability $1/(2d)$. We bound $p_{00}(2n)$ by comparison with the $d = 3$ case. Consider the projection of the $d$-dimensional walk onto its first three coordinates. Each step of the $d$-dimensional walk either moves in one of the first three coordinate directions (with total probability $6/(2d) = 3/d$) or in one of the remaining $d - 3$ coordinate directions (with total probability $(2d - 6)/(2d) = (d-3)/d$). For the $d$-dimensional walk to return to the origin, the projection onto the first three coordinates must also return to the origin. More directly, a step-by-step comparison gives the bound. After $2n$ steps in $\mathbb{Z}^d$, the return probability is \begin{align*} p_{00}^{(d)}(2n) = (2d)^{-2n} \sum \frac{(2n)!}{\prod_{k=1}^d (i_k!)^2}, \end{align*} where the sum is over $i_1 + \cdots + i_d = n$ with $i_k \geq 0$. By the same argument as in $d = 3$ (bounding $\sum q^2 \leq \max q$ for the multinomial distribution with $d$ categories), we obtain \begin{align*} p_{00}^{(d)}(2n) \leq \binom{2n}{n} 2^{-2n} \cdot \max q \lesssim n^{-1/2} \cdot n^{-(d-1)/2} = n^{-d/2}, \end{align*} where $\max q$ for a $d$-fold uniform multinomial decays as $n^{-(d-1)/2}$ by Stirling. Since $d/2 \geq 3/2 > 1$ for $d \geq 3$, the series $\sum_n n^{-d/2}$ converges, and the walk is transient. [/step]