Connect all adjacent points (distance 1) in by edges, then delete the set and all edges incident to them. Is the nearest-neighbor random walk on this graph recurrent?

Stochastic Processes Solution – Problem 15: Connect all adjacent points (distance 1) in by edges, then delete the set and all edges…

Question

Connect all adjacent points (distance 1) in $\mathbb{Z}^{3}$ by edges, then delete the set $\{(100m,100n,100k) \mid m,n,k\in\mathbb{Z}\}$ and all edges incident to them. Is the nearest-neighbor random walk on this graph recurrent?

Step-by-step solution

The simple symmetric random walk on $\mathbb{Z}^3$ is transient by Polya's theorem ( $d \ge 3$ ).

The deleted point set $S = 100\mathbb{Z}^3$ is a sparse periodic sub-lattice. Removing these points and their incident edges does not create barriers blocking paths to infinity; the remaining graph $G$ retains large-scale three-dimensional connectivity.

By the Rayleigh monotonicity principle, removing edges can only increase effective resistance. Since $G \subset \mathbb{Z}^3$ , knowing $\mathbb{Z}^3$ is transient does not directly imply $G$ is transient. Instead, we must find a transient subgraph $H \subseteq G$ .

Construct $H$ as the union of axis-parallel lines through junction points $A = \{(100m+1,100n+1,100k+1) : m,n,k \in \mathbb{Z}\}$ . No vertex of $H$ lies in $S$ (at least two coordinates are $\equiv 1 \pmod{100}$ , hence not multiples of 100), so $H \subseteq G$ .

The graph $H$ is the 100-subdivision of $\mathbb{Z}^3$ : each edge of $\mathbb{Z}^3$ is replaced by a path of 100 unit resistors in series. By the series rule, each such path is equivalent to a single resistor of resistance 100. Scaling all resistances by 100 scales effective resistance by 100, so $R_H(o \leftrightarrow \infty) = 100 \cdot R_{\mathbb{Z}^3}(0 \leftrightarrow \infty) < \infty$ .

By Rayleigh monotonicity, $R_G(o \leftrightarrow \infty) \le R_H(o \leftrightarrow \infty) < \infty$ . Therefore the random walk on $G$ is transient (not recurrent).

Final answer

No (the random walk is transient).

Marking scheme

1. Checkpoints (max 7 pts total)

Fundamental judgment and structural analysis (2 pts)

State that the SRW on $\mathbb{Z}^3$ is transient. [1 pt]
Analyze the structure of $G$ : the deleted set $S$ is sparse/periodic, and $G$ retains large-scale 3D connectivity. [1 pt]

Core argument (4 pts) (score one path only)

*Path A: Quasi-isometry invariant [recommended]*

State: for bounded-degree graphs, recurrence/transience is a quasi-isometry invariant. [3 pts]
Show $G$ is quasi-isometric to $\mathbb{Z}^3$ . [1 pt]

*Path B: Resistance network and subgraph comparison*

Correctly cite Rayleigh monotonicity direction: to prove $G$ transient, find $H \subset G$ with $R_{eff}(H)<\infty$ . [1 pt]
Successfully construct such $H$ (e.g., a coarse grid avoiding deleted points, or show $G$ contains a structure isomorphic to $\mathbb{Z}^3$ ). [3 pts]

*Path C: Volume growth / dimension analysis*

Show $G$ has volume growth $V(r) \sim r^3$ (or Hausdorff/spectral dimension = 3). [2 pts]
Cite relevant theorem (Varopoulos-Carne bound or general lattice theory): $d \ge 3$ with suitable geometry implies transience. [2 pts]

Final conclusion (1 pt)

Explicitly answer: the walk is transient (not recurrent). [1 pt]

Total (max 7)

2. Zero-credit items

Merely because $G \subset \mathbb{Z}^3$ and $\mathbb{Z}^3$ is transient, concluding $G$ is transient (false logic: removing edges increases resistance).
Merely because edges are removed and resistance increases, concluding $G$ is recurrent (non-sequitur).

3. Deductions

Answering "recurrent": conclusion point (1 pt) lost, core argument usually 0; total capped at 2/7.
Intuition only ("still looks 3D") without mathematical tools: core argument capped at 1 pt, total capped at 3/7.
Confusing transient/recurrent definitions: -1 pt.

Stochastic Processes – Problem 15: Connect all adjacent points (distance 1) in by edges, then delete the set and all edges…