AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_prob_zero_of_lt_strict

theoremverified

For any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail probability is 0 whenever k > t.

Statement

theorem hash_probe_tail_prob_zero_of_lt_strict
    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r)
    (t k : ℕ) (ht : t < n) (hkt : t < k) :
    hash_probe_tail_prob n r t k = 0
Source
step towards prime_fixed_offset_linear_probe_stochastic_maximum
Verified
02 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_count_zero_of_lt_strictFor any table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail count is 0 whenever k > t.
  • 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 probe tail probability is defined as the count of configurations requiring at least k probes divided by n^(t + 1). Because the table has load t < k, an insertion cannot take more than t probes before finding an empty slot, so the number of such configurations is zero by `hash_probe_tail_count_zero_of_lt_strict`. The overall probability is therefore 0 / n^(t + 1) = 0.

  1. The probe tail probability expression reduces to 0 / n^(t + 1).

    By definition, the probe tail probability `hash_probe_tail_prob` is the ratio of `hash_probe_tail_count n r t k` to n^(t + 1). Rewriting with `hash_probe_tail_count_zero_of_lt_strict` substitutes 0 for this count, since an insertion into a table containing t elements cannot require k > t probes.

    lines 6–7

    uses hash_probe_tail_count_zero_of_lt_strict

      dsimp [hash_probe_tail_prob]
      rw [hash_probe_tail_count_zero_of_lt_strict n r hr t k ht hkt]
  2. The probe tail probability is 0.

    Simplification of the fraction 0 / n^(t + 1) in ℝ yields 0, closing the goal.

    line 8

      simp
hash_probe_tail_count_zero_of_lt_strict
For a hash table of size n with bijective offset sequence r and load t < n, the number of insertion configurations requiring at least k probes is 0 whenever k > t.

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 table size n with [NeZero n], any bijective offset sequence r, and load t < n, the probe tail probability is 0 whenever k exceeds t. -/theorem hash_probe_tail_prob_zero_of_lt_strict    (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (hr : Function.Bijective r)    (t k : ℕ) (ht : t < n) (hkt : t < k) :    hash_probe_tail_prob n r t k = 0 := by  dsimp [hash_probe_tail_prob]  rw [hash_probe_tail_count_zero_of_lt_strict n r hr t k ht hkt]  simp
See it in the graphDiscuss this resultChallenge it