Abstract:
For a Markov chain $\{S_n\}$, call $S_k$ a cutpoint, and $K$ a cut-epoch, if there is no possible transition from $S_i$ to $S_j$ whenever $i<k<j$. We show that a transient random walk of bounded stepsize on an integer lattice has infinitely many cutpoints almost surely. For simple random walk on $\mathbf{Z}^d$, $d \ge 4$, this is due to Lawler. Furthermore, let $G$ be a finitely generated group of growth at least polynomial of degree 5; then for any symmetric random walk on $G$ such that the steps have a bounded support that generates $G$, the cut-epochs have positive density.
We also show that for any Markov chain which has infinitely many cutpoints almost surely, the eventual occupation numbers generate the exchangeable $\sigma$-field. Combining these results answers a question posed by Kaimanovich, and partially resolves a conjecture of Diaconis and Freedman.
Keywords:cutpoint, exchangeable, Markov chain, Poisson boundary, random walks on groups.