RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1996 Volume 41, Issue 4, Pages 854–868 (Mi tvp3239)

This article is cited in 17 papers

Cutpoints and exchangeable events for random walks

N. Jamesa, Y. Peresb

a Department of Mathematics, University of California, Berkeley, CA, USA
b Department of Statistics, University of California, Berkeley, CA, USA

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.

Received: 11.10.1995

Language: English

DOI: 10.4213/tvp3239


 English version:
Theory of Probability and its Applications, 1997, 41:4, 666–677

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024