PROVED
This has been solved in the affirmative.
Given a random walk $s_0,s_1,\ldots$ in $\mathbb{Z}^2$, starting at the origin, let $f_k(x)$ count the number of $0\leq l\leq k$ such that $s_l=x$.
Let\[F(k)=\{ x: f_k(x) = \max_y f_k(y)\}\]be the set of 'favourite values'. Is it true that\[\left\lvert \bigcup_{k\leq n}F(k)\right\rvert \leq (\log n)^{O(1)}\]almost surely, for all but finitely many $n$?
A problem of Erdős and Révész.
This is true: almost surely\[\left\lvert \bigcup_{k\leq n}F(k)\right\rvert \ll (\log n)^{2},\]which follows from the fact that almost surely $\lvert F(n)\rvert \leq 3$ for all large $n$ (see
[1165]) and the result of Erdős and Taylor
[ErTa60] that, if $T_n$ is the maximum number of visits of a random walk by time $n$ to any fixed point then\[T_n \ll (\log n)^2.\]
View the LaTeX source
This page was last edited 23 January 2026.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1166, https://www.erdosproblems.com/1166, accessed 2026-03-01
