AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_prob_one

theoremverified

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

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.

  1. 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.

    lines 6–23

    uses Finset.mem_filter, Finset.mem_univ, true_and, add_zero, Fin.val_zero

      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]
  2. 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.

    lines 24–39

    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_fin

      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]
  3. 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.

    lines 40–48

    uses ne_of_gt, lt_of_lt_of_le, pow_succ, pow_ne_zero, mul_div_mul_left

      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]
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

/-- 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]
See it in the graphDiscuss this resultChallenge it