/-
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.
-/
module
public import FormalConjecturesUtilErdős Problem 1165
References:
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).
[HLOZ24] Hao, C., Li, X., Okada, I. and Zheng, Y., Favorite sites for simple random walk in two and more dimensions. arXiv:2409.00995 (2024).
[To01] Tóth, B., No more than three favorite sites for simple random walk. Ann. Probab. 29 (2001), 484--503.
@[expose] public sectionopen MeasureTheory Filteropen scoped ProbabilityTheory ENNRealnamespace Erdos1165The four unit steps $(\pm 1, 0)$ and $(0, \pm 1)$ of the simple random walk on $\mathbb{Z}^2$.
def steps : Set (ℤ × ℤ) := {(1, 0), (-1, 0), (0, 1), (0, -1)}
X k is the $k$-th step of a simple random walk on $\mathbb{Z}^2$, on the probability space
Ω: the steps are random variables, they are independent, and each is uniformly distributed on
steps.
structure IsSimpleRandomWalkSteps {Ω : Type*} [MeasureSpace Ω] (X : ℕ → Ω → ℤ × ℤ) : Prop whereEach step is a random variable.
measurable (k : ℕ) : Measurable (X k)The steps are independent.
indep : ProbabilityTheory.iIndepFun X ℙ
Each step is uniform on steps.
isUniform (k : ℕ) : MeasureTheory.pdf.IsUniform (X k) steps ℙ Measure.countThe position $s_n = \sum_{k<n} X_k$ of the walk after $n$ steps, so that $s_0 = 0$.
def position {Ω : Type*} (X : ℕ → Ω → ℤ × ℤ) (n : ℕ) (ω : Ω) : ℤ × ℤ :=
∑ k ∈ Finset.range n, X k ω
The local time $f_n(x)=#{0\le k\le n : s_k=x}$ of the site x at time n.
def localTime {Ω : Type*} (X : ℕ → Ω → ℤ × ℤ) (n : ℕ) (ω : Ω) (x : ℤ × ℤ) : ℕ :=
((Finset.range (n + 1)).filter fun k ↦ position X k ω = x).card
The set $F(n)={x : f_n(x)=\max_y f_n(y)}$ of favourite sites at time n. It is the set of
sites whose local time is at least that of every site. The local time is $0$ outside the finite
set of visited sites, so the maximum exists and F(n) is finite and non-empty.
def favouriteSites {Ω : Type*} (X : ℕ → Ω → ℤ × ℤ) (n : ℕ) (ω : Ω) : Set (ℤ × ℤ) :=
{x | ∀ y, localTime X n ω y ≤ localTime X n ω x}The walk starts at the origin.
@[category API, AMS 60]
theorem position_zero {Ω : Type*} (X : ℕ → Ω → ℤ × ℤ) (ω : Ω) : position X 0 ω = 0 := Ω:Type u_1X:ℕ → Ω → ℤ × ℤω:Ω⊢ position X 0 ω = 0
All goals completed! 🐙The walk moves by the next step.
@[category API, AMS 60]
theorem position_succ {Ω : Type*} (X : ℕ → Ω → ℤ × ℤ) (n : ℕ) (ω : Ω) :
position X (n + 1) ω = position X n ω + X n ω := Ω:Type u_1X:ℕ → Ω → ℤ × ℤn:ℕω:Ω⊢ position X (n + 1) ω = position X n ω + X n ω
All goals completed! 🐙def erdos_1165.answer (r : ℕ) : ℝ≥0∞ := if r = 3 then 1 else 0Given 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$.
A problem of Erdős and Révész [Va99, 6.77]. We take the simple random walk, on any probability
space (IsSimpleRandomWalkSteps). Hao, Li, Okada and Zheng [HLOZ24, Theorem 1.1] showed that the
probability is $1$ for $r=3$ and $0$ for $r\geq 4$, see erdos_1165.variants.hao_li_okada_zheng.
The value of erdos_1165.answer for $r<3$ is not used.
@[category research solved, question value, AMS 60]
theorem erdos_1165 {Ω : Type*} [MeasureSpace Ω] [IsProbabilityMeasure (ℙ : Measure Ω)]
{X : ℕ → Ω → ℤ × ℤ} (hX : IsSimpleRandomWalkSteps X) (r : ℕ) (hr : 3 ≤ r) :
ℙ {ω | ∃ᶠ n in atTop, (favouriteSites X n ω).encard = (r : ℕ∞)} = erdos_1165.answer r := Ω:Type u_1inst✝¹:MeasureSpace Ωinst✝:IsProbabilityMeasure ℙX:ℕ → Ω → ℤ × ℤhX:IsSimpleRandomWalkSteps Xr:ℕhr:3 ≤ r⊢ ℙ {ω | ∃ᶠ (n : ℕ) in atTop, (favouriteSites X n ω).encard = ↑r} = erdos_1165.answer r
All goals completed! 🐙Hao, Li, Okada and Zheng [HLOZ24, Theorem 1.1] proved that, for the simple random walk on $\mathbb{Z}^2$, almost surely $$\limsup_{n\to\infty} #K^{(2)}(n) = 3,$$ where $K^{(2)}(n)$ is the set of favourite sites at time $n$. The cardinalities are natural numbers, so almost surely there are eventually at most three favourite sites, and exactly three infinitely often. Tóth [To01] proved the corresponding bound for the one-dimensional walk, see [HLOZ24, Section 1].
@[category research solved, AMS 60]
theorem erdos_1165.variants.hao_li_okada_zheng {Ω : Type*} [MeasureSpace Ω]
[IsProbabilityMeasure (ℙ : Measure Ω)] {X : ℕ → Ω → ℤ × ℤ} (hX : IsSimpleRandomWalkSteps X) :
∀ᵐ ω, limsup (fun n ↦ (favouriteSites X n ω).encard) atTop = 3 := Ω:Type u_1inst✝¹:MeasureSpace Ωinst✝:IsProbabilityMeasure ℙX:ℕ → Ω → ℤ × ℤhX:IsSimpleRandomWalkSteps X⊢ ∀ᵐ (ω : Ω), limsup (fun n ↦ (favouriteSites X n ω).encard) atTop = 3
All goals completed! 🐙end Erdos1165