hash_probe_tail_prob_zero_of_lt_strict
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
- 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 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.
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.
uses
hash_probe_tail_count_zero_of_lt_strictdsimp [hash_probe_tail_prob] rw [hash_probe_tail_count_zero_of_lt_strict n r hr t k ht hkt]
The probe tail probability is 0.
Simplification of the fraction 0 / n^(t + 1) in ℝ yields 0, closing the goal.
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
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 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