Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 1166

claims/: The 2 claim pages of Problem 1166, one per claimant's result; the problem's standing derives from them.

Statement. 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$ ?

Formulation. The random walk is discrete-time symmetric nearest-neighbor simple random walk, with independent increments uniform on $(\pm1,0),(0,\pm1)$ , as in every result below. The poser's statement, Some of Paul's favorite problems (1999), Problem 6.78, printed p. 12, takes the walk from the setup on printed p. 11, which says only "a random walk on $\mathbb{Z}^2$ ".

Status. PROVED, the site's label. Almost surely the union has size $O((\log n)^2)$ ; the cited estimates give the more precise upper limit

\limsup_{n\to\infty} \frac{\left|\bigcup_{0\le k\le n}F(k)\right|}{(\log n)^2} \le\frac3\pi.

The constant is a consequence of those estimates, not a claim of a sharp asymptotic for the union. The derived standing is claimed and proved, not solved: the pending claim is the favorite-count bound of Hao, Li, Okada and Zheng with the Erdős–Taylor estimate, two refereed theorems; the site's page states their combination itself and credits the eventual bound through Problem 1165 to Tóth, a misattribution (Hao–Li–Okada–Zheng Theorem 1.1 supplies it), so no review credits the deduction, and the claim stays claimed although both of its inputs are refereed. An independent Lean proof of the deduction is a second pending claim, on its own claim page.

Source. erdosproblems.com/1166, accessed 2026-09-05. Cite as: T. F. Bloom, Erdős Problem #1166, https://www.erdosproblems.com/1166.

References.

[Va99] Various contributors, Some of Paul's favorite problems, July 1999, Problem 6.78, printed p. 12.
[ErTa60] Erdős, P. and Taylor, S. J., Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar. (1960), 137-162.
C. Hao, X. Li, I. Okada, and Y. Zheng, Favorite sites for simple random walk in two and more dimensions. arXiv:2409.00995v2 (12 November 2025), Theorem 1.1; Probability Theory and Related Fields 195 (2026), 1765–1822.

Formalization. No statement file for the problem exists in formal-conjectures (none on main on 2026-10-07; the site's page lists no formalized statement and the community database records the problem unformalized). A Lean proof of the deduction in Boris Alexeev's lean-proofs repository, which names no author and imports that repository's formalization of Problem 1165, is recorded on its own claim page; it was not built or audited here.

Current assessment

The recorded favorite-union deduction combines the eventual favorite-count bound from Hao–Li–Okada–Zheng with the Erdős–Taylor maximum-local-time upper bound. The corollary and essential Hao chain are written in full; no independent review has examined the deduction. On 2026-09-05 the site's discussion and proof-claims pages carried no comments or proof claims. The stronger printed display (4.35) remains uncertified and is not assumed by the recorded proof.

Progress

The original Erdős–Révész question appears as Problem 6.78 in the July 1999 booklet Some of Paul's favorite problems ([Va99]). It explicitly asks for a fixed exponent and an almost-sure eventual bound. Its union starts at $k=1$ ; including $F(0)$ changes the count by at most one and does not affect the conclusion. The site's page attributes the deduction to the eventual favorite-count bound in Problem 1165 and the maximum-local-time upper bound of Erdős and Taylor.

The underlying modern input is Hao–Li–Okada–Zheng, Theorem 1.1, for the precise simple-walk law stated above. The 1960 maximum-local-time conjecture is a different statement from this question about the union of favorite sets.

Known Results

The complete favorite-union deduction uses that favorites can only accumulate while the maximum local time stays at one fixed level. Once their count is eventually at most three, at most three sites can appear at each late level. Therefore the union through time $n$ has size at most a finite random constant plus $3T_n$ , where $T_n=\max_x f_n(x)$ .

The Erdős–Taylor upper bound gives $\limsup T_n/(\log n)^2\le1/\pi$ almost surely, proving the claim. The corollary and the essential same-paper chain for the Hao input are written in full. The latter uses the proved parity-specific, favorite-location-weighted screening estimate; it does not assume the stronger printed conditional display (4.35), which remains uncertified as explained in the linked source results.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (42)

Problem 1165 A Lean proof of the favorite-union bound in Alexeev's repository problems/analysis/E1166/claims Analysis Analysis Theorem 1.2 (p. 2): the largest disc of planar simple random walk covered at least α(log n)^2/π times by step n has radius n^{(1-√α)/4+o(1)} almost surely analysis/erdos_1960_problems_concerning_structure_random_walk_paths Equation (2.5) — the planar no-return probability The planar upper bound for maximum local time analysis/hao_2024_favorite_sites_simple_random_walk_two Local screening for the two striped domino pairings Corollary: the number of sites ever favorite by time n Lemma 2.1: planar hitting estimates Lemma 2.3: negative-binomial local estimate Lemma 2.4: moderate deviations of geometric sums Lemma 2.5: one-site upper tails Lemma 2.6: an upper tail for favorite-site record times Lemma 2.7: occupancy at the highest occupied urn Lemma 2.8: screening a narrow band of urns Lemma 4.1: producing the second and third favorite Lemma 4.10: a nearby new favorite has a small deficit Lemma 4.11: slice-by-slice wide-band screening Lemma 4.12: comparable local masses within a screening interval Lemma A.2: excursion decoupling Lemma A.4: the probability of a successful point Lemma A.6: excursion counts and upcrossings Lemma A.8: Gaussian block confinement Erasing two-step excursions and decomposing local time Proposition 1.3: lower deviations of planar maximum local time Propositions 4.2 and 4.2′: holding times given the shortened path Propositions 4.3 and 4.3′: holding times at a favorite record Proposition 4.4: a first bound on near-maximal external local times Proposition 4.5: balanced external local times near a favorite Proposition 4.7: summable probabilities for four favorites Proposition 4.8: the wide-band screening estimate Proposition 4.9: narrow-band screening Proposition A.3: first and second moments of thick successful points Proposition A.7: the constrained upcrossing sum Record levels and simultaneous favorite sites Theorem 1.1: three planar favorite sites infinitely often Some of Paul's favorite problems (1999)Problem 6.78: union of earlier favorite sites

Graph