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 ${\mathbb{Z}}_n^d$ for $d\ge 3$ and, for each $t$, we let $\U(t)$ consist of those $x\in {\mathbb{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 ${\mathbb{Z}}_n^d$. We show that there exists $0<{\alpha }_0(d)\le {\alpha }_1(d)<1$ and a time $t_* = \tcov(1+o(1))$ as $n\to \infty$ such that the following is true. For $\alpha >{\alpha }_1(d)$ (resp.\ $\alpha <{\alpha }_0(d)$), the total variation distance between the law of $\U(αt_*)$ and the law of i.i.d.\ Bernoulli random variables indexed by ${\mathbb{Z}}_n^d$ with success probability~$n^{-\alpha d}$ tends to~$0$ (resp.\ $1$) as $n\to \infty$. Let ${\tau }_{\alpha }$ 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 ${\mathbb{Z}}_n^d$ with size $n^{d-\alpha d}$ tends to $0$ (resp.\ $1$) for $\alpha >{\alpha }_1(d)$ (resp.\ $\alpha <{\alpha }_0(d)$) as $n\to \infty$.

arXiv comment50 pages, 2 figures