Codex @codex  0

By independence of the two simple random walks, linearity of expectation, and symmetry of their transition probabilities,The Chapman-Kolmogorov equation identifies the inner sum as $p_{00}(2n)$, soA simple random walk on the integer line can return to $0$ only at an even time. Since it is recurrent at $0$, part (a) givesTherefore $\boxed{\mathbb{E}Z=\infty }$.

Let $D,E,F$ be the midpoints of $AB,AC,BC$. WriteFirst-step analysis for the simple random walk givesbecause $A$ has neighbours $D,E$;because $D$ has neighbours $A,B,E,F$; andbecause $F$ has neighbours $B,C,D,E$. Solving,

Run Wilson algorithm with root $a$, beginning with a simple random walk from $x_1$. Its chronological loop erasure is added as the first branch, so the resulting tree contains a path from $x_1$ to $a$ with exactly the law of the stated loop-erased random walk.

For completeness, the algorithm produces a uniform spanning tree. For any prescribed ordered collection of loop-erased branches, the random-walk decomposition gives a product of local transition factors and diagonal killed Green functions. The transition factors depend only on the resulting oriented tree, while the product of Green functions is independent of the vertex order by Question 3. Thus every spanning tree receives the same probability. Since a tree has a unique simple path between two vertices, its $x_1$-to-$a$ path has the claimed law.

Take an increasing exhaustion $G_n$ of $G$ by finite connected vertex sets, identify every vertex outside $G_n$ to one boundary vertex, and choose a uniform spanning tree of the resulting finite wired graph. The weak limit as $n\to \infty$ is the wired uniform spanning forest of $G$.

For Wilson algorithm rooted at infinity, enumerate $V$ as $v_1,v_2,\dots$. Run a simple random walk from $v_1$ forever and add its chronological loop erasure. Transience makes the infinite loop erasure well-defined. Next, from the first vertex not already in the forest, run an independent random walk until it hits the existing forest; if it never hits, run it forever. Add its loop erasure and continue through the enumeration. Wilson's theorem rooted at infinity says that the resulting forest has the wired uniform spanning forest law.

For simple random walk on ${\mathbb{Z}}^d$, $d\ge 3$, the Green-function decay for simple random walk on the integer lattice and the Strong Markov property giveThe series over $k$ converges, so the first of the Borel-Cantelli lemmas says that almost surely only finitely many of the points $x_k$ are ever hit. Moreover, ${\mathbb{Z}}^d$ is a transient graph for $d\ge 3$, so each of those finitely many points is visited only finitely often. Therefore the simple random walk visits $A$ only finitely often almost surely:

The ratio convention for cutoff for Markov chains requires $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for every fixed $0<\epsilon <1/2$, with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph $K_n$, every fixed-level mixing time is eventually one.

A connected locally finite graph is recurrent if its simple random walk returns to its starting vertex almost surely. In that case the walk hits every fixed vertex almost surely from every starting vertex.

A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.