Random walks with local memory

Abstract

We prove a quenched invariance principle for a class of random walks in random environment on ${\mathbb{Z}}^d$, where the walker alters its own environment. The environment consists of an outgoing edge from each vertex. The walker updates the edge $e$ at its current location to a new random edge $e^{\prime }$ (whose law depends on $e$) and then steps to the other endpoint of $e^{\prime }$. We show that a native environment for these walks (i.e., an environment that is stationary in time from the perspective of the walker) consists of the wired uniform spanning forest oriented toward the walker, plus an independent outgoing edge from the walker.

v3 merges several theorems into one theorem (e.g., Theorem 1.1 and Theorem 5.7 in the old version becomes Theorem 1.1). Typesetting is changed to save space. 23 pages, 8 figures

References in corpus (5)

• Equality of Opportunity in Supervised Learning
• An almost sure invariance principle for random walks in a space-time random environment
• Statistical Inference for Cluster Trees
• Interlacements and the Wired Uniform Spanning Forest
• Recurrence of horizontal-vertical walks

Cited by in corpus (2)

• Rotor walks on transient graphs and the wired spanning forest
• Recurrence of horizontal-vertical walks