hash_probe_tail_prob
For 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 the real-valued probability (hash_probe_tail_count n r t k : ℝ) / ((n : ℝ) ^ (t + 1)), which is the probability that inserting an additional uniformly random key from ZMod n into an initially empty n-slot table after inserting t keys with independent uniform home slots in Fin t → ZMod n requires strictly more than k probes.
Statement
noncomputable def hash_probe_tail_prob (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t k : ℕ) : ℝ
- Defined in
- arXiv:2610.31363, Section 3
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 15
- hash_probe_tail_prob_zero_of_lt_strictFor 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.
- hash_probe_expected_costFor a table size n with [NeZero n], an offset sequence r : Fin n → ZMod n, and a number of inserted keys t : ℕ, hash_probe_expected_cost n…
- hash_probe_expected_cost_sub_constTranslating an offset sequence by subtracting a constant element c in ZMod n preserves the expected probe cost at any load t, by…
- prime_fixed_offset_linear_probe_tail_prob_interior_t_twoAt load t = 2 (where k = 2), the probe tail probability under any bijective offset r with r 0 = 0 is bounded by linear probing on any…
- 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…
- prime_fixed_offset_mean_le_of_tail_leFor any prime table size p, offset sequence r : Fin p → ZMod p, and load t, if every probe-cost tail probability under r is bounded by the…
- hash_probe_expected_cost_zeroFor any table size n with [NeZero n] and any offset sequence r : Fin n → ZMod n, the expected probe cost hash_probe_expected_cost n r 0…
- hash_probe_tail_prob_zeroFor 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…
- hash_probe_expected_cost_twoAfter two insertions the expected cost is 1+2/n+(3+[2r₁=0])/n².
- prime_fixed_offset_linear_probe_stochastic_maximum_threeFor a 3-slot hash table (p = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0, every load t < 3, and every integer k ≥…
- unit_first_fixed_offset_mean_probe_maximum_threeFor a 3-slot hash table (n = 3), every bijective probe sequence r : Fin 3 → ZMod 3 with r 0 = 0 and IsUnit (r 1), and every load t < 3,…
- not_hash_probe_tail_prob_zero_of_ltThe statement
hash_probe_tail_prob_zero_of_ltis false: Take n = 1, r = (fun _ => 0 : Fin 1 → ZMod 1), t = 1, k = 2. Hypotheses hold:… - hash_probe_tail_prob_oneFor 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_two_eq_adjacent_meanThe second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.
- prime_fixed_offset_linear_probe_tail_prob_interior_t_predAt load t = p - 1 (one empty slot), every bijective offset sequence has identical probe tail probabilities, matching linear probing.
Read back from the Lean
Given a positive natural number $n$, a probe offset function $r : \text{Fin } n \to \mathbb{Z}/n\mathbb{Z}$, and natural numbers $t$ and $k$, hash_probe_tail_prob n r t k is defined as the real number (hash_probe_tail_count n r t k : ℝ) / ((n : ℝ) ^ (t + 1)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Tail probability Pr[T_r > k] of insertion probe count under fixed offset sequence r. -/ noncomputable def hash_probe_tail_prob (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (t k : ℕ) : ℝ := (hash_probe_tail_count n r t k : ℝ) / ((n : ℝ) ^ (t + 1))