Uniformity of the late points of random walk on Z_n^d for d >= 3

Abstract

Suppose that $X$ is a simple random walk on $\Z_n^d$ for $d \geq 3$ and, for each $t$, we let $\U(t)$ consist of those $x \in \Z_n^d$ which have not been visited by $X$ by time $t$. Let $\tcov$ be the expected amount of time that it takes for $X$ to visit every site of $\Z_n^d$. We show that there exists $0 < α_0(d) \leq α_1(d) < 1$ and a time $t_* = \tcov(1+o(1))$ as $n \to \infty$ such that the following is true. For $α> α_1(d)$ (resp.\ $α< α_0(d)$), the total variation distance between the law of $\U(αt_*)$ and the law of i.i.d.\ Bernoulli random variables indexed by $\Z_n^d$ with success probability~$n^{-αd}$ tends to~$0$ (resp.\ $1$) as $n \to \infty$. Let $τ_α$ be the first time $t$ that $|\U(t)| = n^{d-αd}$. We also show that the total variation distance between the law of $\U(τ_α)$ and the law of a uniformly chosen set from $\Z_n^d$ with size $n^{d-αd}$ tends to $0$ (resp.\ $1$) for $α> α_1(d)$ (resp.\ $α< α_0(d)$) as $n \to \infty$.

50 pages, 2 figures