linear_probing_noisy_displacements
Given $n \ge 1$, home slot assignments $h : \text{Fin } n \to \mathbb{Z}/n\mathbb{Z}$, and a noise vector $\xi : \text{Fin } n \to \mathbb{R}$, the noisy displacement vector assigns to each key $i \in \text{Fin } n$ the sum of its linear probing displacement under $h$ and the noise coordinate $\xi(i)$.
Statement
noncomputable def linear_probing_noisy_displacements (n : ℕ) [NeZero n] (p : (Fin n → ZMod n) × (Fin n → ℝ)) : Fin n → ℝ
- Defined in
- knowledgebase, OP-894
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- linear_probing_displacementsGiven a table size n and a sequence of n home slots h in Fin n -> ZMod n, linear_probing_displacements n h i is the number of occupied…
Read back from the Lean
Given a natural number $n$ with hypothesis $[NeZero\ n]$ and a pair $p = (h, \xi) \in (\text{Fin } n \to \mathbb{Z}/n\mathbb{Z}) \times (\text{Fin } n \to \mathbb{R})$, linear_probing_noisy_displacements n p defines the function from $\text{Fin } n$ to $\mathbb{R}$ that maps each index $i \in \text{Fin } n$ to:
$$(linear\_probing\_displacements\ n\ p.1\ i : \mathbb{R}) + p.2(i)$$
that is, the displacement (as a natural number cast to $\mathbb{R}$) of the $i$-th key when keys $0, \dots, i-1$ have been inserted into a hash table of size $n$ via linear probing with hash function $p.1$, plus the noise perturbation $p.2(i)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The displacement vector of linear probing plus continuous uniform noise. -/ noncomputable def linear_probing_noisy_displacements (n : ℕ) [NeZero n] (p : (Fin n → ZMod n) × (Fin n → ℝ)) : Fin n → ℝ := fun i => (linear_probing_displacements n p.1 i : ℝ) + p.2 i