hash_probe_tail_two_eq_adjacent_mean
The second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.
Statement
theorem hash_probe_tail_two_eq_adjacent_mean (n : ℕ) [NeZero n] (hn : 2 ≤ n)
(r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) :
(n : ℝ) * hash_probe_tail_prob n r t 2 =
(∑ A : Fin t → ZMod n,
(hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) : ℝ)) / (n : ℝ)^t- Source
- Unit-first fixed-offset mean-probe extremality; experiments 11670–11680 and arXiv:2610.31363.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- hash_adjacent_countThe number of occupied slots whose d-successor is also occupied.
- hash_probe_tail_probFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and natural numbers t and k, hash_probe_tail_prob n r t k is…
- hash_probe_tail_countThe number of pairs of an insertion sequence of length t and an additional query slot whose insertion cost under offset sequence r…
- hash_occupied_slotsThe set of occupied slots in Finset (ZMod n) after sequentially inserting a list A : List (ZMod n) into an initially empty hash table of…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
The proof, explained
A probe sequence takes at least two steps if and only if both the initial slot and the second probe slot are occupied; because r 0 = 0, this means both x and x + r 1 are in the table, identifying such starting locations with occupied adjacent pairs. Summing over all t-step hash sequences equates the total probe tail count to the sum of adjacent pair counts across all tables. Dividing by the sample space size n^(t + 1) and multiplying by n cancels one factor of n, showing that n times the tail probability equals the expected number of adjacent occupied pairs divided by n^t.
Membership in {x | ∀ j < 2, x + r j ∈ T} reduces to (∀ j ≤ 1, x + r j ∈ T) ↔ (x ∈ T ∧ x + r 1 ∈ T), with the values of the indices 0 and 1 in Fin n known to be 0 and 1.
By set extensionality, an element x belongs to the filtered set if and only if x + r j ∈ T for all indices j with j < 2. Because j < 2 is equivalent to j ≤ 1 on natural numbers, and n ≥ 2 ensures that the elements 0 and 1 of Fin n have numerical values 0 and 1, the condition becomes (∀ j ≤ 1, x + r j ∈ T).
uses
mem_filter,mem_univ,true_and,Order.lt_two_iff,Fin.val_one',Nat.mod_eq_of_lt,Fin.val_zeroext x simp only [mem_filter, mem_univ, true_and, Order.lt_two_iff] have h1_val : (1 : Fin n).val = 1 := by rw [Fin.val_one'] exact Nat.mod_eq_of_lt (by omega) have h0_val : (0 : Fin n).val = 0 := Fin.val_zero n
If x + r j ∈ T for all j ≤ 1, then x ∈ T and x + r 1 ∈ T.
Specializing the hypothesis to j = 0 (since 0 ≤ 1) and using r 0 = 0 gives x + 0 = x ∈ T. Specializing to j = 1 (since 1 ≤ 1) gives x + r 1 ∈ T.
uses
add_zeroconstructor · intro h have h0 : x ∈ T := by have hj : (0 : Fin n).val ≤ 1 := by rw [h0_val]; decide have h' := h 0 hj rwa [hr0, add_zero] at h' have h1 : x + r 1 ∈ T := by have hj : (1 : Fin n).val ≤ 1 := by rw [h1_val] exact h 1 hj exact ⟨h0, h1⟩
Conversely, if x ∈ T and x + r 1 ∈ T, then x + r j ∈ T for every j ≤ 1, completing the set equality.
For any index j with j ≤ 1, either j.val = 0 or j.val = 1. In the first case, j = 0, so x + r j = x + r 0 = x ∈ T. In the second case, j = 1, so x + r j = x + r 1 ∈ T. Hence the two sets of slots coincide.
uses
Nat.le_one_iff_eq_zero_or_eq_one.mp,add_zero· intro ⟨h0, h1⟩ j hj rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hj with hj0 | hj1 · have : j = 0 := by ext; rw [hj0, h0_val] rw [this, hr0, add_zero] exact h0 · have : j = 1 := by ext; rw [hj1, h1_val] rw [this] exact h1
The total probe tail count for k = 2 equals the sum over all hash sequences A of the number of occupied adjacent pairs in the resulting table.
Unfolding the definition of tail count gives the cardinality of pairs (A, x) where probing at x takes at least 2 steps in table T(A). Rewriting this cardinality as a sum of indicators and splitting over the product type turns it into an outer sum over hash sequences A and an inner sum over starting positions x. For each fixed table, the inner sum counts elements whose first two probe steps lie in T(A), which the set equality lemma equates to the adjacent count {x ∈ T(A) | x + r 1 ∈ T(A)}.
uses
card_filter,Fintype.sum_prod_type,hash_probe_tail_two_eq_adjacent_mean_filter_finsetunfold hash_probe_tail_count simp_rw [card_filter, Fintype.sum_prod_type] congr 1 with A rw [← card_filter] unfold hash_adjacent_count rw [hash_probe_tail_two_eq_adjacent_mean_filter_finset n hn r hr0]
Unfolding the probe tail probability expresses n * ℙ(probe cost ≥ 2) as n * (∑_A adjacent_count(T(A))) / n^(t + 1).
The tail probability is defined as the tail count divided by the total number of choices n^(t + 1). Substituting the tail count formula from the previous lemma and distributing the real coercion over the sum yields n times the sum of adjacent counts divided by n^(t + 1).
uses
hash_probe_tail_two_eq_adjacent_mean_tail_count_equnfold hash_probe_tail_prob rw [hash_probe_tail_two_eq_adjacent_mean_tail_count_eq n hn r hr0 t] push_cast
Cancelling the factor of n in the numerator against one power of n in the denominator leaves the adjacent count sum divided by n^t.
Because n ≠ 0 in ℝ, the denominator factors as n^(t + 1) = n^t * n. Rewriting division by a product as iterated division allows cancelling n with the denominator's n factor via mul_div_cancel₀.
uses
NeZero.ne,pow_succ,div_mul_eq_div_div,mul_div_cancel₀have hn_ne : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ] rw [hpow] rw [div_mul_eq_div_div, mul_div_cancel₀ _ hn_ne]
mem_filter- An element belongs to the filtered finset {x ∈ s | p x} if and only if it belongs to s and satisfies p.
mem_univ- Every element of a finite type belongs to the universal finset univ.
true_and- The conjunction True ∧ p simplifies to p.
Order.lt_two_iff- In a discrete linear order, x < 2 is equivalent to x ≤ 1.
Fin.val_one'- The numerical value of 1 in Fin n is 1 mod n.
Nat.mod_eq_of_lt- If a < b, then a mod b = a.
Fin.val_zero- The numerical value of 0 in Fin n is 0.
add_zero- Adding zero to an element leaves it unchanged (a + 0 = a).
Nat.le_one_iff_eq_zero_or_eq_one.mp- If a natural number is at most 1, it is either 0 or 1.
card_filter- The size of a filtered finset equals the sum of indicator values (1 if the predicate holds, 0 otherwise) over the ambient finset.
Fintype.sum_prod_type- A sum over a product type α₁ × α₂ equals the iterated sum over α₁ and α₂.
hash_probe_tail_two_eq_adjacent_mean_filter_finset- For any set of occupied slots T with table size n ≥ 2 and probe base r 0 = 0, the set of starting locations whose first two probe steps lie in T equals {x ∈ T | x + r 1 ∈ T}.
hash_probe_tail_two_eq_adjacent_mean_tail_count_eq- The total count of probe sequences taking at least 2 steps across all hash sequences of length t equals the sum over all hash sequences of the number of occupied adjacent pairs in the resulting table.
NeZero.ne- An element with a NeZero instance is not equal to zero.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
div_mul_eq_div_div- In division monoids, a / (b * c) = (a / b) / c.
mul_div_cancel₀- In a group with zero, multiplying b by a / b yields a when b ≠ 0.
- The coercion from natural counts to real numbers in the definition of probability is distributed across the sum by `push_cast` as a formal bookkeeping step.
- Small inequality goals on indices, such as $1 < n$ (from $2 \le n$) and $0 \le 1$, are solved automatically by `omega` and `decide`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetprivate lemma hash_probe_tail_two_eq_adjacent_mean_filter_finset (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr0 : r 0 = 0) (T : Finset (ZMod n)) : univ.filter (fun x : ZMod n => ∀ j : Fin n, j.val < 2 → x + r j ∈ T) = {x ∈ T | x + r 1 ∈ T} := by ext x simp only [mem_filter, mem_univ, true_and, Order.lt_two_iff] have h1_val : (1 : Fin n).val = 1 := by rw [Fin.val_one'] exact Nat.mod_eq_of_lt (by omega) have h0_val : (0 : Fin n).val = 0 := Fin.val_zero n constructor · intro h have h0 : x ∈ T := by have hj : (0 : Fin n).val ≤ 1 := by rw [h0_val]; decide have h' := h 0 hj rwa [hr0, add_zero] at h' have h1 : x + r 1 ∈ T := by have hj : (1 : Fin n).val ≤ 1 := by rw [h1_val] exact h 1 hj exact ⟨h0, h1⟩ · intro ⟨h0, h1⟩ j hj rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hj with hj0 | hj1 · have : j = 0 := by ext; rw [hj0, h0_val] rw [this, hr0, add_zero] exact h0 · have : j = 1 := by ext; rw [hj1, h1_val] rw [this] exact h1private lemma hash_probe_tail_two_eq_adjacent_mean_tail_count_eq (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) : hash_probe_tail_count n r t 2 = ∑ A : Fin t → ZMod n, hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) := by unfold hash_probe_tail_count simp_rw [card_filter, Fintype.sum_prod_type] congr 1 with A rw [← card_filter] unfold hash_adjacent_count rw [hash_probe_tail_two_eq_adjacent_mean_filter_finset n hn r hr0]theorem hash_probe_tail_two_eq_adjacent_mean (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr0 : r 0 = 0) (t : ℕ) : (n : ℝ) * hash_probe_tail_prob n r t 2 = (∑ A : Fin t → ZMod n, (hash_adjacent_count n (r 1) (hash_occupied_slots n r (List.ofFn A)) : ℝ)) / (n : ℝ)^t := by unfold hash_probe_tail_prob rw [hash_probe_tail_two_eq_adjacent_mean_tail_count_eq n hn r hr0 t] push_cast have hn_ne : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ] rw [hpow] rw [div_mul_eq_div_div, mul_div_cancel₀ _ hn_ne]