hash_probe_tail_prob_zero
For any table size n with [NeZero n], offset sequence r : Fin n → ZMod n, and number of inserted keys t, the 0-th tail probability of probe cost hash_probe_tail_prob n r t 0 is 1.
Statement
theorem hash_probe_tail_prob_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) :
hash_probe_tail_prob n r t 0 = 1- Source
- step towards unit_first_fixed_offset_mean_probe_maximum
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- Used by 3
- cyclic_latin_rank_matching_rank_sumFor the rotation matching μ_r(i) = a r - i, the aggregate proposer rank is constant equal to r, hence its total is n * r.
- prime_fixed_offset_tail_prob_two_twoFor any odd prime p and any bijective offset sequence r : Fin p → ZMod p with r 0 = 0, the second tail probability at load t = 2 is…
- hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
The proof, explained
The 0-th tail probability of probe cost is defined as the fraction of configuration pairs in `(Fin t → ZMod n) × ZMod n` whose first 0 probe slots are occupied. Because the index condition `j < 0` is vacuously false for all natural numbers, every configuration pair satisfies this requirement, making the event set the entire universe of configurations. Counting the product space yields `n^t * n = n^(t+1)` outcomes, which matches the denominator and evaluates to 1.
The set of configuration pairs satisfying the 0-th probe condition is the entire universe `Finset.univ`.
Unfolding `hash_probe_tail_prob` and `hash_probe_tail_count`, the condition for probe cost being at least 0 requires that all probe indices `j` satisfying `(j : ℕ) < 0` correspond to occupied slots. Since no natural number is less than zero (`Nat.not_lt_zero`), this implication is vacuously true for every configuration. Therefore, filtering `Finset.univ` by this condition keeps every element (`Finset.filter_true_of_mem`).
uses
Finset.filter_true_of_mem,Nat.not_lt_zerounfold hash_probe_tail_prob hash_probe_tail_count have h : (Finset.univ.filter (fun p : (Fin t → ZMod n) × ZMod n => ∀ j : Fin n, (j : ℕ) < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1))) = Finset.univ := by rw [Finset.filter_true_of_mem] intro p _ j hj exact absurd hj (Nat.not_lt_zero _)
The cardinality of the event set is `n ^ t * n`.
Replacing the filtered set with `Finset.univ`, its cardinality is given by `Fintype.card ((Fin t → ZMod n) × ZMod n)` (`Finset.card_univ`). Applying the cardinality formulas for product types (`Fintype.card_prod`) and function spaces (`Fintype.card_fun`), together with the cardinalities `|ZMod n| = n` (`ZMod.card`) and `|Fin t| = t` (`Fintype.card_fin`), the total number of configurations is `n ^ t * n`.
uses
Finset.card_univ,Fintype.card_prod,Fintype.card_fun,ZMod.card,Fintype.card_finrw [h, Finset.card_univ] have hcard : Fintype.card ((Fin t → ZMod n) × ZMod n) = n ^ t * n := by rw [Fintype.card_prod, Fintype.card_fun, ZMod.card, Fintype.card_fin] rw [hcard]
The quotient simplifies to 1.
Since `n ≠ 0` (`NeZero.ne`), the real number `n` is nonzero, implying `(n : ℝ) ^ t * n ≠ 0` by `pow_ne_zero` and `mul_ne_zero`. Rewriting the denominator `n ^ (t + 1)` as `n ^ t * n` using `pow_succ`, the numerator and denominator are identical and nonzero, so their division evaluates to 1 (`div_self`).
uses
NeZero.ne,pow_succ,div_self,mul_ne_zero,pow_ne_zerohave hn : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * n := by rw [pow_succ] push_cast rw [hpow, div_self (mul_ne_zero (pow_ne_zero _ hn) hn)]
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all of its elements yields the original finite set.
Nat.not_lt_zero- No natural number is strictly less than zero.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` on a finite type is the cardinality of the type itself.
Fintype.card_prod- The cardinality of a Cartesian product of two finite types is the product of their cardinalities.
Fintype.card_fun- The cardinality of the function type `α → β` between finite types is the cardinality of `β` raised to the power of the cardinality of `α`.
ZMod.card- The cardinality of `ZMod n` is `n`.
Fintype.card_fin- The cardinality of `Fin n` is `n`.
NeZero.ne- An element with an instance of `NeZero` is nonzero.
pow_succ- In any monoid, a power satisfies `a ^ (n + 1) = a ^ n * a`.
div_self- Any nonzero element divided by itself equals 1.
mul_ne_zero- The product of two nonzero elements in a structure with no zero divisors is nonzero.
pow_ne_zero- Any natural power of a nonzero element in a structure without zero divisors is nonzero.
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.
/-- For any table size n, offset sequence r, and load t, the 0-th tail probability of probe cost is 1. -/theorem hash_probe_tail_prob_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t : ℕ) : hash_probe_tail_prob n r t 0 = 1 := by unfold hash_probe_tail_prob hash_probe_tail_count have h : (Finset.univ.filter (fun p : (Fin t → ZMod n) × ZMod n => ∀ j : Fin n, (j : ℕ) < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1))) = Finset.univ := by rw [Finset.filter_true_of_mem] intro p _ j hj exact absurd hj (Nat.not_lt_zero _) rw [h, Finset.card_univ] have hcard : Fintype.card ((Fin t → ZMod n) × ZMod n) = n ^ t * n := by rw [Fintype.card_prod, Fintype.card_fun, ZMod.card, Fintype.card_fin] rw [hcard] have hn : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * n := by rw [pow_succ] push_cast rw [hpow, div_self (mul_ne_zero (pow_ne_zero _ hn) hn)]