/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtilpublicimportFormalConjectures.ErdosProblems.«1165»
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference
"Paul Erdős and his mathematics", Budapest, July 1999 (1999).
[ErTa60] Erdős, P. and Taylor, S. J., Some problems concerning the structure of random walk
paths. Acta Math. Acad. Sci. Hungar. 11 (1960), 137--162.
PDF
[Re90] Révész, P., Random walk in random and non-random environments. World Scientific,
Singapore (1990).
[DPRZ04] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O., Cover times for Brownian motion and
random walks in two dimensions. Ann. of Math. (2) 160 (2004), 433--464.
arXiv:math/0107191
The sites x = (a, b) of $\mathbb{Z}^2$ with Euclidean norm $\lVert x\rVert\leq r$. The
condition is written without a square root as $a^2+b^2\leq r^2$.
coveringRadius X n ω is the largest integer r such that, by time n, the walk has visited
every site x with $\lVert x\rVert\leq r$. This is the radius $R_n$ of the problem, which depends
on the walk ω.
The set of such r contains 0, since the origin is visited at time 0. It is bounded: the
sites $(j,0)$ with $\lvert j\rvert\leq r$ are $2r+1$ different sites visited at times at most
n, so $2r\leq n$. Hence sSup is a maximum and there is no junk value.
Let $R_n$ be the maximal integer such that almost every random walk from the origin in
$\mathbb{Z}^2$ visits every $x\in\mathbb{Z}^2$ with $\lVert x\rVert\leq R_n$ in at most $n$ steps.
Is it true that
$$\log R_n \asymp \sqrt{\log n}?$$
A problem of Erdős and Taylor, see [ErTa60, p. 153] and [Va99, 6.76]. This is true, as proved
independently by Révész [Re90] and Kesten, see [DPRZ04, Section 1.3], which reports that they
proved the following. The probability that the disc of radius $n$ is covered by time
$e^{t(\log n)^2}$ has $\liminf_{n\to\infty}$ at least $e^{-b/t}$ and $\limsup_{n\to\infty}$ at
most $e^{-a/t}$ for every $t>0$, where $0<a<b<\infty$ are constants. The exact limit is in
erdos_1164.variants.dembo_peres_rosen_zeitouni.
We take the simple random walk (IsSimpleRandomWalkSteps). Read literally, $R_n$ would be $0$:
for every $n$ some walk misses a neighbour of the origin, and such walks have positive
probability. So $R_n=R_n(\omega)$ is the random variable coveringRadius, and
$\log R_n\asymp\sqrt{\log n}$ means tightness: for every $\varepsilon>0$ there are constants
$c>0$ and $C$ such that $c\sqrt{\log n}\leq\log R_n\leq C\sqrt{\log n}$ with probability at least
$1-\varepsilon$ for all large $n$. This is the sense of the results above and of
erdos_1164.variants.dembo_peres_rosen_zeitouni, which are about probabilities, not almost sure
bounds. [ErTa60, p. 153] asks an almost sure question about the time needed to cover the disc of
radius $n$; we follow the results in probability reported in [DPRZ04, Section 1.3].
Dembo, Peres, Rosen and Zeitouni [DPRZ04, Theorem 1.4] proved a conjecture of Kesten and Révész:
if $T_n$ is the time it takes the simple random walk in $\mathbb{Z}^2$ to cover the disc of
radius $n$, then
$$\lim_{n\to\infty}\mathbb{P}\left(\log T_n\leq t(\log n)^2\right)=e^{-4/t}$$
for every $t>0$.
The disc is $D_n=D(0,n)\cap\mathbb{Z}^2$ (openDisc). Since $T_n$ is an integer,
$\log T_n\leq t(\log n)^2$ holds if and only if $T_n\leq\lfloor e^{t(\log n)^2}\rfloor$, that is,
if the disc is covered by that time.