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

Updated Oct 8

Problem 1165

claims/: The 1 claim page of Problem 1165, 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_n(x)$ count the number of $0\leq k\leq n$ such that $s_k=x$ .

Let

F(n)=\{ x: f_n(x) = \max_y f_n(y)\}

be the set of 'favourite values'. Find

\mathbb{P}(\lvert F(n)\rvert=r\textrm{ infinitely often})

for $r\geq 3$ .

Statement (precise). Given a simple random walk $s_0,s_1,\ldots$ in $\mathbb{Z}^2$ , starting at the origin, let $f_n(x)$ count the number of $0\leq k\leq n$ such that $s_k=x$ .

Let

F(n)=\{ x: f_n(x) = \max_y f_n(y)\}

be the set of 'favourite values'. Find

\mathbb{P}(\lvert F(n)\rvert=r\textrm{ infinitely often})

for $r\geq 3$ .

Notes. The site's wording does not say which random walk is meant, and the answer depends on the law: for the walk whose steps are $(1,0)$ and $(0,1)$ with probability $1/2$ each, no site is visited twice, so $\lvert F(n)\rvert=n+1$ equals $r$ only at $n=r-1$ and the probability is $0$ for every $r\ge3$ , while for the simple random walk it is $1$ at $r=3$ . The poser's own text leaves the law open as well: the setup of Section 6.1 of [Va99], printed p. 11, which precedes Erdős and Révész's item 6.77 on printed p. 12, says only "a random walk on $\mathbb{Z}^2$ ", so the ambiguity is already in the poser's text and the site's wording copies it. The change inserts "simple" before "random walk", the walk whose independent increments are uniform on $(\pm1,0),(0,\pm1)$ ; nothing else changes, and the time-zero visit is counted as the site counts it. The evidence is the literature's statement of the question as Erdős and Révész's. Hao, Li, Okada and Zheng [HLOZ24], Section 1, display (1.2), state it for discrete-time simple random walk on $\mathbb{Z}^d$ for every $d\ge1$ , apart from their theorem's range $d\ge2$ . Tóth [To01], Section 1, printed pp. 484–485, independently states Erdős and Révész's favorite-site question for simple symmetric random walk on $\mathbb{Z}$ . The site credits both papers, each about simple random walk, with the answer. The correction does not rest on the texts in which Erdős and Révész raised the question (1984, 1987 and 1991, cited by both papers). No result about any other law is recorded. The standing judges this precise Statement.

Status. Solved, on the site's label, which credits the value $0$ for $r\ge4$ to Tóth [To01] and the value $1$ for $r=3$ to Hao, Li, Okada and Zheng [HLOZ24]: the probability is $1$ for $r=3$ and $0$ for every integer $r\ge4$ . Hao–Li–Okada–Zheng, Theorem 1.1 proves almost surely $\limsup_n|F(n)|=3$ , which gives both values; it is recorded as an accepted claim. Tóth's paper concerns the walk on $\mathbb Z$ , as the assessment below explains, and has no claim page.

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

References.

[Va99] Various contributors, Some of Paul's favorite problems, July 1999, Problem 6.77, printed p. 12.
[HLOZ24] 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); Probability Theory and Related Fields 195 (2026), 1765–1822, DOI 10.1007/s00440-025-01441-1.
[To01] Tóth, Bálint, No more than three favorite sites for simple random walk. Ann. Probab. 29 (2001), no. 1, 484–503, DOI 10.1214/aop/1008956341.

Formalization. No statement file for the problem exists in formal-conjectures (none on main on 2026-10-07). A Lean formalization of the answer in Boris Alexeev's lean-proofs repository, added on 2026-08-22, names Hao, Li, Okada and Zheng as informal authors and Codex and GPT-5.6 Sol as formal authors; the Lean proof linked for Problem 1166 imports it. It is linked on the claim page; it was not built or audited here, and the standing does not rest on it.

Current assessment

The original Erdős–Révész question appears as Problem 6.77 in the July 1999 booklet Some of Paul's favorite problems ([Va99]). It asks about exactly $r$ simultaneous favorites infinitely often. The 2024 preprint of Hao, Li, Okada, and Zheng resolved both planar bounds. The library's result pages cite their 44-page arXiv v2 of November 2025, not the pagination of the 58-page journal version in Probability Theory and Related Fields.

The site attributes the $r\ge4$ upper bound to Tóth (2001). Tóth's paper starts with a walk on $\mathbb Z$ , not $\mathbb Z^2$ (printed p. 484). It supplies the one-dimensional result (Theorem 1). The planar upper bound used here is Hao–Li–Okada–Zheng's Theorem 1.1, so the site's credit to Tóth for the planar $r\ge4$ value is recorded as a misattribution rather than as a claim. The site's discussion contains a January 2026 correction clarifying the event $|F(n)|=r$ infinitely often, already reflected in the statement; the proof-claims page carried no submitted claims.

The literature check covered the arXiv history, publisher record, author pages, and web searches for later papers and indexed X announcements. No replacement of the planar result or distinct accepted planar proof was located. The source digest records the search limits and version qualifications.

The reconstruction of Proposition 4.9 uses separate parity estimates and a favorite-location-weighted bound. This is sufficient for the four-favorite bound and Theorem 1.1. The stronger conditional display (4.35) printed in the source remains uncertified and is not used; the result page explains the conditioning issue and the proved replacement. Explicitly stated classical probability inputs remain external dependencies.

Known Results

Theorem 1.1 gives the two probability values. Its proof uses record local-time levels, two-point avoidance for the lower bound, and a decomposition of local times with successive candidate screening for the upper bound. The full argument and its essential same-paper lemmas, including all seven Proposition 1.3/Appendix A proof components, are reconstructed.

The eventual bound $|F(n)|\le3$ implies the union-of-favorites result in Problem 1166 when combined with the Erdős–Taylor bound on maximum local time. In contrast, Theorem 1.2 shows that favorite counts in dimensions $d\ge3$ grow on a $\log\log n$ limit-superior scale.

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 (54)

Hao, Li, Okada and Zheng's three favorite sites in the plane problems/analysis/E1165/claims Problem 1166 Three favorites at most bounds the union Analysis Analysis Frequently visited sets for random walks Corollary 1.3 (p. 1505): two nearby sites are not both maximally visited Equation (4.1) (p. 1513): geometric law for the total occupation of two sites 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 Equations (3.6) and (3.11) (pp. 142--143): tails for k(log n)^2 planar returns to the origin Theorem 13: maximum local time in transient dimensions 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.2: late hits of finitely many sites 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 3.1: eventual characterization by late avoidance Lemma 3.2: late-time regularity and separation of thick sites Lemma 3.3: early avoidance after a new favorite appears 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 Theorem 1.2: favorite counts in transient dimensions

Graph