Consider an infinite connected graph with uniformly bounded vertex degrees. Define , where if and only if and there exists such that Determine whether the simple random walk on is recurrent or transient, and prove your conclusion.

Probability Theory Solution – Problem 20: Determine whether the simple random walk on is recurrent or transient, and prove your conclusion

Question

Consider an infinite connected graph $G=(V,E)$ with uniformly bounded vertex degrees. Define $G^{3}=(V^{3},\mathcal{E})$ , where $\left(\left(v_{1},v_{2},v_{3}\right),\left(u_{1},u_{2},u_{3}\right)\right)\in\mathcal{E}$ if and only if $u_{1},u_{2},u_{3},v_{1},v_{2},v_{3}\in V$ and there exists $i\in\{1,2,3\}$ such that

$u_j = v_j \text{ for } j \ne i,\quad (u_i,v_i)\in E.$

Determine whether the simple random walk on $G^{3}$ is recurrent or transient, and prove your conclusion.

Step-by-step solution

Step 1. Consider an infinite connected graph $G=(V,E)$ with uniformly bounded vertex degrees; write $M = \sup_{v \in V} \deg(v) < \infty$ . The graph $G^3$ is the threefold Cartesian product of $G$ . In $G^3$ , every vertex $\mathbf{v} = (v_1, v_2, v_3)$ has degree $\deg_{G^3}(\mathbf{v}) = \deg_G(v_1) + \deg_G(v_2) + \deg_G(v_3)$ . Since the degrees in $G$ are uniformly bounded, $\deg_{G^3}(\mathbf{v}) \le 3M$ . Recurrence of the simple random walk on a graph is intimately connected with the electrical resistance network properties of the graph. By the Nash-Williams criterion or Rayleigh's monotonicity principle, if one can contract or embed the graph into a structure of known recurrence or transience type, this aids the determination. Step 2. For the $d$ -dimensional integer lattice $\mathbb{Z}^d$ , the simple random walk is transient when $d \ge 3$ . Since $G$ is an infinite connected graph, it necessarily contains an infinite simple path or some other infinite structure. Because $G$ is infinite and connected, starting from any vertex there exists at least one infinite self-avoiding path $P = \{x_0, x_1, x_2, \dots\} \subseteq V$ with $(x_k, x_{k+1}) \in E$ . Step 3. Consider the subgraph $H = P^3 \subseteq G^3$ . The path $P$ is isomorphic to the one-dimensional integer lattice $\mathbb{Z}$ (or its half-line $\mathbb{N}$ ). Therefore the structure of $H$ is isomorphic to (a portion of) the three-dimensional lattice $\mathbb{Z}^3$ (or $\mathbb{N}^3$ ). For the electrical resistance network on $G^3$ , assign resistance $1$ to every edge. By Rayleigh's monotonicity principle, removing edges from a graph (i.e., increasing resistances) can only increase the effective resistance. If a subgraph is transient, then the original graph is also transient. Step 4. Specifically, examine the subgraph $H$ of $G^3$ generated by the path $P$ . The vertex set of $H$ is $V_P = P \times P \times P$ , and its edge set consists only of edges corresponding to adjacent vertices in $P$ . In fact, $H$ is isomorphic to the three-dimensional lattice graph $\mathbb{N}^3$ (if $P$ is one-sided) or $\mathbb{Z}^3$ (if $P$ is two-sided). It is well known that the simple random walk on the three-dimensional lattice $\mathbb{Z}^3$ is transient. The same holds for the half-space or octant version $\mathbb{N}^3$ . Step 5. Since $H$ is a subgraph of $G^3$ and the simple random walk on $H$ is transient, the effective resistance from the origin to infinity is finite. By the comparison theorem, the additional edges in $G^3$ only decrease the effective resistance, thereby increasing the escape probability from the origin to infinity. Therefore the simple random walk on $G^3$ is also transient.

Final answer

Transient. QED.

Marking scheme

Based on the official solution provided, the following is the grading rubric for this problem.

1. Checkpoints (max 7 pts total)

Score exactly one chain | take the maximum subtotal among chains; do not add points across chains.

Chain A: Subgraph Embedding / Rayleigh Monotonicity Principle (Official Solution Idea)

[Step 1] State or argue: since $G$ is an infinite connected graph, $G$ contains an infinite simple path (or self-avoiding path) $P$ , and $P$ is isomorphic to $\mathbb{N}$ (or $\mathbb{Z}$ ). [1 pt]
*Note: If the student merely mentions that $G$ has infinitely many vertices without addressing the path structure, no credit is awarded.*
[Step 2] Construct or identify the subgraph $H = P^3$ (i.e., $P \times P \times P$ ) in $G^3$ , and observe that this subgraph is isomorphic to the three-dimensional lattice graph $\mathbb{N}^3$ (or $\mathbb{Z}^3$ ). [2 pts]
*Note: If the student identifies the subgraph $P^3$ but does not explicitly connect it to the structure of $\mathbb{N}^3$ or $\mathbb{Z}^3$ , award 1 pt.*
[Step 3] Cite the known result: the simple random walk on the three-dimensional lattice $\mathbb{N}^3$ (or $\mathbb{Z}^3$ ) is transient. [1 pt]
[Step 4] Apply Rayleigh's Monotonicity Principle or the resistance network comparison theorem to argue: [2 pts]
Observe that $G^3$ is a supergraph of $H$ , i.e., $G^3$ has more edges than $H$ (equivalently, smaller effective resistance). (1 pt)
Argue that "a graph containing a transient subgraph is itself transient" (i.e., $R_{\text{eff}}(G^3) \le R_{\text{eff}}(H) < \infty$ ). (1 pt)
[Step 5] State the final conclusion: the simple random walk on $G^3$ is transient. [1 pt]
*Note: The conclusion must be supported by the preceding argument; if the reasoning contains logical errors, this point is not awarded.*

Total (max 7)

2. Zero-credit items

Stating only the conclusion "transient" without any valid mathematical argument or justification.
Stating only "because the dimension is 3" without defining the dimension of the graph or proving the specific relationship between volume growth rate and recurrence (this is a heuristic observation, not a rigorous proof).
Proving the result only for the special case $G=\mathbb{Z}$ without generalizing to the general case or invoking the subgraph comparison principle.
Merely copying the problem definitions (such as the definition of $G^3$ ) or listing known conditions (such as "uniformly bounded degrees").

3. Deductions

−1 (Logic Gap): Reversing the direction in the comparison principle (e.g., erroneously claiming "since the subgraph is recurrent, the supergraph is recurrent," or confusing the relationship between resistance magnitude and recurrence).
−1 (Conclusion): Confusing terminology by writing "recurrent" instead of "transient," even though the derivation implies finite resistance.
−2 (Major Concept): Attempting to use a criterion designed for establishing recurrence (such as Nash-Williams' $\sum \frac{1}{|\partial B_n|} = \infty$ ) to force a proof of transience, resulting in a logical contradiction.
Cap at 3/7: Attempting a volume growth argument claiming $V(n) \ge cn^3$ implies transience, without citing a specific theorem applicable to general bounded-degree graphs (note: volume growth alone is insufficient for general graphs; typically an isoperimetric inequality is also needed, whereas the lattice embedding method is the most direct and rigorous approach).

Probability Theory – Problem 20: Determine whether the simple random walk on is recurrent or transient, and prove your conclusion