hash_probe_tail_prob_one
For any table size n ≥ 2 with [NeZero n], any bijective offset sequence r with r 0 = 0, and any load t ≤ n, the 1st tail probability hash_probe_tail_prob n r t 1 is identically equal to (t : ℝ) / (n : ℝ).
Statement
theorem hash_probe_tail_prob_one (n : ℕ) [NeZero n] (hn : 2 ≤ n)
(r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0)
(t : ℕ) (ht : t ≤ n) :
hash_probe_tail_prob n r t 1 = (t : ℝ) / (n : ℝ)- Source
- step towards unit_first_fixed_offset_mean_probe_maximum
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_occupied_slots_cardFor any table size n with [NeZero n], any bijective offset sequence r : Fin n → ZMod n, and any list of keys A with length at most n, the…
- 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…
- 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…
- Used by 1
- 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…
The proof, explained
The probability that an item requires at least 1 probe is the fraction of pairs (A, b)—an insertion sequence A of length t and an initial probe slot b—where the first probed slot b + r(0) is occupied. Because r(0) = 0, this occurs precisely when the initial slot b is already one of the occupied slots. Since the probe sequence r is bijective and t ≤ n, exactly t distinct slots are occupied for each of the n^t possible insertion sequences, giving a total of n^t * t favorable pairs. Dividing by the total sample space size n^(t+1) and cancelling n^t yields t / n.
For any sequence of inserted keys, the set of initial probe locations that require at least 1 probe is identically the set of already occupied slots.
For probe depth k = 1, the condition that probe step j hits an occupied slot for all j < 1 restricts entirely to j = 0, since 0 is the only index in Fin n with numerical value strictly less than 1. Because the offset sequence satisfies r 0 = 0, the first probe location b + r 0 simplifies to b + 0 = b. Thus, a starting slot b requires at least 1 probe if and only if b itself is already occupied.
uses
Finset.mem_filter,Finset.mem_univ,true_and,add_zero,Fin.val_zerohave h_filter_eq : ∀ (A : Fin t → ZMod n), (Finset.filter (fun b : ZMod n => ∀ (j : Fin n), (j : ℕ) < 1 → b + r j ∈ hash_occupied_slots n r (List.ofFn A)) Finset.univ) = hash_occupied_slots n r (List.ofFn A) := by intro A ext b simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h have h0 : ((0 : Fin n) : ℕ) < 1 := by simp have := h 0 h0 rwa [hr0, add_zero] at this · intro h j hj have hj0 : j = 0 := by ext simp only [Fin.val_zero] omega subst hj0 rwa [hr0, add_zero]
The total count of pairs (A, b) of insertion sequences and probe locations requiring at least 1 probe is n^t * t.
Unfolding hash_probe_tail_count, the count is the size of the set of pairs (A, b) ∈ (Fin t → ZMod n) × ZMod n meeting the probe condition. Converting this cardinality into an iterated sum over sequences A and slots b, the inner sum for a fixed A counts the slots requiring at least 1 probe. By the previous step, these are exactly the occupied slots of A. Since r is bijective and t ≤ n, inserting t elements fills exactly t distinct slots by hash_occupied_slots_card. Summing this constant value t over all |(Fin t → ZMod n)| = n^t possible insertion sequences yields n^t * t.
uses
Finset.card_filter,Fintype.sum_prod_type,List.length_ofFn,hash_occupied_slots_card,Finset.sum_const,Finset.card_univ,smul_eq_mul,Fintype.card_fun,ZMod.card,Fintype.card_finhave h_count : hash_probe_tail_count n r t 1 = n ^ t * t := by unfold hash_probe_tail_count rw [Finset.card_filter] rw [Fintype.sum_prod_type] have h_inner : ∀ A : Fin t → ZMod n, (∑ y : ZMod n, if (∀ (j : Fin n), (j : ℕ) < 1 → y + r j ∈ hash_occupied_slots n r (List.ofFn A)) then 1 else 0) = t := by intro A rw [← Finset.card_filter] rw [h_filter_eq A] have hlen : (List.ofFn A).length ≤ n := by simp only [List.length_ofFn] exact ht rw [hash_occupied_slots_card n r hr (List.ofFn A) hlen, List.length_ofFn] simp_rw [h_inner] rw [Finset.sum_const, Finset.card_univ, smul_eq_mul] rw [Fintype.card_fun, ZMod.card, Fintype.card_fin]
The probability of requiring at least 1 probe equals t / n.
By definition, hash_probe_tail_prob is the favorable count divided by n^(t+1). Substituting the count n^t * t and factoring the denominator as n^t * n, we cancel the factor n^t from both numerator and denominator. This cancellation is valid because n ≥ 2 > 0 ensures n ≠ 0 and therefore n^t ≠ 0, leaving t / n.
uses
ne_of_gt,lt_of_lt_of_le,pow_succ,pow_ne_zero,mul_div_mul_leftunfold hash_probe_tail_prob rw [h_count] have hn0 : (n : ℝ) ≠ 0 := by exact_mod_cast ne_of_gt (lt_of_lt_of_le (by decide : 0 < 2) hn) have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ] push_cast rw [hpow] have hnt : (n : ℝ) ^ t ≠ 0 := pow_ne_zero t hn0 rw [mul_div_mul_left _ _ hnt]
add_zero- Adding zero to any element leaves it unchanged (a + 0 = a).
Fin.val_zero- The canonical numerical value of 0 in Fin n is 0.
Finset.card_filter- The size of a filtered subset {i ∈ s | p i} equals the sum of the indicator values (1 if p i, else 0) over s.
Finset.card_univ- The cardinality of Finset.univ for a finite type α is the cardinality of α.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.sum_const- Summing a constant value b over a finite set s yields |s| • b.
Fintype.card_fin- The number of elements in Fin n is n.
Fintype.card_fun- The number of functions from a finite type α to a finite type β is |β|^|α|.
Fintype.sum_prod_type- A sum of a function over a Cartesian product α₁ × α₂ equals the iterated double sum over α₁ and α₂.
hash_occupied_slots_card- For a bijective probe sequence r and an insertion list A of length at most n, the number of occupied slots in the hash table equals the length of A.
List.length_ofFn- The length of a list generated from a function on Fin n via List.ofFn is n.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
mul_div_mul_left- In a group with zero, (c * a) / (c * b) = a / b provided c ≠ 0.
ne_of_gt- If b < a, then a ≠ b.
pow_ne_zero- In a monoid with zero without zero divisors, if a ≠ 0 then a ^ n ≠ 0.
pow_succ- In any monoid, a ^ (n + 1) = a ^ n * a.
smul_eq_mul- Scalar multiplication by a natural number coincides with multiplication.
true_and- The logical conjunction True ∧ p simplifies to p.
ZMod.card- The cardinality of the ring ℤ/nℤ is n.
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 bijective offset sequence with r 0 = 0 and load t ≤ n, the k=1 probe tail probability is t / n. -/theorem hash_probe_tail_prob_one (n : ℕ) [NeZero n] (hn : 2 ≤ n) (r : Fin n → ZMod n) (hr : Function.Bijective r) (hr0 : r 0 = 0) (t : ℕ) (ht : t ≤ n) : hash_probe_tail_prob n r t 1 = (t : ℝ) / (n : ℝ) := by have h_filter_eq : ∀ (A : Fin t → ZMod n), (Finset.filter (fun b : ZMod n => ∀ (j : Fin n), (j : ℕ) < 1 → b + r j ∈ hash_occupied_slots n r (List.ofFn A)) Finset.univ) = hash_occupied_slots n r (List.ofFn A) := by intro A ext b simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h have h0 : ((0 : Fin n) : ℕ) < 1 := by simp have := h 0 h0 rwa [hr0, add_zero] at this · intro h j hj have hj0 : j = 0 := by ext simp only [Fin.val_zero] omega subst hj0 rwa [hr0, add_zero] have h_count : hash_probe_tail_count n r t 1 = n ^ t * t := by unfold hash_probe_tail_count rw [Finset.card_filter] rw [Fintype.sum_prod_type] have h_inner : ∀ A : Fin t → ZMod n, (∑ y : ZMod n, if (∀ (j : Fin n), (j : ℕ) < 1 → y + r j ∈ hash_occupied_slots n r (List.ofFn A)) then 1 else 0) = t := by intro A rw [← Finset.card_filter] rw [h_filter_eq A] have hlen : (List.ofFn A).length ≤ n := by simp only [List.length_ofFn] exact ht rw [hash_occupied_slots_card n r hr (List.ofFn A) hlen, List.length_ofFn] simp_rw [h_inner] rw [Finset.sum_const, Finset.card_univ, smul_eq_mul] rw [Fintype.card_fun, ZMod.card, Fintype.card_fin] unfold hash_probe_tail_prob rw [h_count] have hn0 : (n : ℝ) ≠ 0 := by exact_mod_cast ne_of_gt (lt_of_lt_of_le (by decide : 0 < 2) hn) have hpow : (n : ℝ) ^ (t + 1) = (n : ℝ) ^ t * (n : ℝ) := by rw [pow_succ] push_cast rw [hpow] have hnt : (n : ℝ) ^ t ≠ 0 := pow_ne_zero t hn0 rw [mul_div_mul_left _ _ hnt]