AFTD Auto-Formalizing Theoretical Domains

hash_probe_tail_prob

def

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

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