Chen--Stein Method for the Uncovered Set of Random Walk on ${\mathbb{Z}}_n^d$ for $d\ge 3$

Let $X$ be a simple random walk on ${\mathbb{Z}}_n^d$ with $d\ge 3$ and let $t_{\mathrm{c}\mathrm{o}\mathrm{v}}$ be the expected cover time. We consider the set of points ${\mathcal{U}}_{\alpha }$ of ${\mathbb{Z}}_n^d$ that have not been visited by the walk by time $\alpha t_{\mathrm{c}\mathrm{o}\mathrm{v}}$ for $\alpha \in (0,1)$. It was shown in [MS17] that there exists ${\alpha }_1(d)\in (0,1)$ such that for all $\alpha >{\alpha }_1(d)$ the total variation distance between the law of the set ${\mathcal{U}}_{\alpha }$ and an i.i.d. sequence of Bernoulli random variables indexed by ${\mathbb{Z}}_n^d$ with success probability $n^{-\alpha d}$ tends to $0$ as $n \to \infty$\mathrm{.}In[MS17]theconstant$\alpha_1(d)$convergesto$1$as$d\to\infty$. In this short note using the Chen–Stein method and a concentration result for Markov chains of Lezaud we greatly simplify the proof of [MS17] and find a constant ${\alpha }_1(d)$ which converges to $3\mathrm{/}4$ as $d\to \mathrm{\infty }$.