hash_probe_expected_cost_zero
For 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 into an empty table (t = 0) is 1.
Statement
theorem hash_probe_expected_cost_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) :
hash_probe_expected_cost n r 0 = 1- Source
- scout/2610-31363-a-sharp-analysis-of-fixed-offset-hash-tables.md:333
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_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_nilFor any n and offset sequence r : Fin n → ZMod n, hash_occupied_slots n r [] = ∅.
- 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…
- 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…
- Used by 2
- mixed_radix_offset_mean_probe_zeroFor every table size n ≥ 2, every probe sequence r : Fin n → ZMod n, and every factor list P, the expected probe cost into an empty table…
- unit_first_fixed_offset_mean_probe_eq_zeroFor every table size n ≥ 2 with [NeZero n] and every bijective probe sequence r : Fin n → ZMod n with r 0 = 0 and IsUnit (r 1), the…
Read back from the Lean
For every natural number $n$ with $n \ne 0$ and every probe function $r : \mathrm{Fin}\ n \to \mathbb{Z}/n\mathbb{Z}$, the expected probe cost at step $0$, $\mathrm{hash\_probe\_expected\_cost}\ n\ r\ 0$, equals $1$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The expected probe cost into a hash table of size $n$ is defined by the tail probability formula $\sum_{k=0}^n \mathbb{P}(\text{probes} \ge k)$. When the table is empty ($t = 0$), no slots are occupied, so the very first probe ($j = 0$) finds an empty slot with certainty. Consequently, the probability of needing at least 0 probes is 1, while the probability of needing at least $k + 1$ probes is 0 for every $k \ge 0$. Summing these probabilities collapses to the single non-zero term at $k = 0$, giving an expected probe cost of exactly 1.
For an empty table ($t = 0$) and $k = 0$, the tail probe condition is vacuously satisfied, so the filtered set of pairs is the entire universe.
Unfolding `hash_probe_tail_count`, the count is the size of the set of pairs $(p_1, p_2) \in (\text{Fin } 0 \to \mathbb{Z}/n\mathbb{Z}) \times \mathbb{Z}/n\mathbb{Z}$ satisfying $p_2 + r(j) \in \text{hash\_occupied\_slots}$ for all probe indices $j < 0$. Since no natural number is strictly less than 0 (`Nat.not_lt_zero`), this hypothesis is vacuously true for every element, and `Finset.filter_true_of_mem` reduces the filtered set to `Finset.univ`.
uses
Finset.filter_true_of_mem,Nat.not_lt_zerounfold hash_probe_tail_count have hh : (Finset.univ.filter (fun (p : (Fin 0 → ZMod n) × ZMod n) => ∀ j : Fin n, j.val < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1))) = Finset.univ := by apply Finset.filter_true_of_mem intro x hx j hj exact absurd hj (Nat.not_lt_zero _)
The tail count `hash_probe_tail_count n r 0 0` equals $n$. automation
Having shown the set is `Finset.univ`, its cardinality is $|(\text{Fin } 0 \to \mathbb{Z}/n\mathbb{Z}) \times \mathbb{Z}/n\mathbb{Z}| = |\mathbb{Z}/n\mathbb{Z}|^0 \times |\mathbb{Z}/n\mathbb{Z}| = 1 \times n = n$, computed using `Finset.card_univ`, `Fintype.card_prod`, `Fintype.card_fun`, `Fintype.card_fin`, and `ZMod.card`.
uses
Finset.card_univ,Fintype.card_prod,Fintype.card_fun,Fintype.card_fin,ZMod.cardrw [hh, Finset.card_univ, Fintype.card_prod, Fintype.card_fun, Fintype.card_fin] simp [ZMod.card]
For any $k$, the tail count `hash_probe_tail_count n r 0 (k + 1)` equals 0. automation
By `Finset.card_eq_zero` and `Finset.filter_eq_empty_iff`, it suffices to show no pair $p$ satisfies the condition for all $j < k + 1$. In particular, taking $j = 0 < k + 1$ would require $p_2 + r(0)$ to be in the set of occupied slots. But since $t = 0$, the list of previously inserted keys is empty (`List.ofFn_zero`), so the set of occupied slots is empty (`hash_occupied_slots_nil`). This contradicts membership in $\emptyset$.
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iff,List.ofFn_zero,hash_occupied_slots_nilunfold hash_probe_tail_count rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro p _ hh have h0 := hh (0 : Fin n) (by simp) rw [List.ofFn_zero, hash_occupied_slots_nil] at h0 simpa using h0
The tail probability `hash_probe_tail_prob n r 0 0` equals 1. automation
Unfolding `hash_probe_tail_prob`, the probability is defined as the tail count divided by $n^{0 + 1} = n$. Rewriting with the tail count of $n$ from `hash_probe_expected_cost_zero_tail_count_zero`, the ratio $n / n$ evaluates to 1.
uses
hash_probe_expected_cost_zero_tail_count_zerounfold hash_probe_tail_prob rw [hash_probe_expected_cost_zero_tail_count_zero] norm_num
For any $k$, the tail probability `hash_probe_tail_prob n r 0 (k + 1)` equals 0. automation
Unfolding `hash_probe_tail_prob`, the probability is the tail count divided by $n^{0 + 1}$. Rewriting with the tail count of 0 from `hash_probe_expected_cost_zero_tail_count_succ`, the ratio $0 / n$ simplifies to 0.
uses
hash_probe_expected_cost_zero_tail_count_succunfold hash_probe_tail_prob rw [hash_probe_expected_cost_zero_tail_count_succ] simp
The sum defining expected probe cost reduces to the single term at $k = 0$.
Unfolding `hash_probe_expected_cost`, the expected cost is $\sum_{k=0}^n \text{hash\_probe\_tail\_prob } n\ r\ 0\ k$. By `Finset.sum_eq_single 0`, the sum collapses to its $k = 0$ term because every non-zero index $b \in \{0, \dots, n\}$ is a successor $k + 1$ (`Nat.exists_eq_succ_of_ne_zero`), where the tail probability vanishes by `hash_probe_expected_cost_zero_tail_prob_succ`, and $0$ belongs to the range $\{0, \dots, n\}$ since $0 < n + 1$ (`Finset.mem_range.mpr`, `Nat.succ_pos`).
uses
Finset.sum_eq_single,Nat.exists_eq_succ_of_ne_zero,hash_probe_expected_cost_zero_tail_prob_succ,Finset.mem_range.mpr,Nat.succ_posunfold hash_probe_expected_cost have hsum : ∑ k ∈ Finset.range (n + 1), hash_probe_tail_prob n r 0 k = hash_probe_tail_prob n r 0 0 := by apply Finset.sum_eq_single 0 · intro b _ hb0 obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hb0 exact hash_probe_expected_cost_zero_tail_prob_succ n r k · intro h0 exact absurd (Finset.mem_range.mpr (Nat.succ_pos n)) h0
The expected probe cost into an empty table is 1.
Rewriting the sum using `hsum` reduces the expression to `hash_probe_tail_prob n r 0 0`, which equals 1 by `hash_probe_expected_cost_zero_tail_prob_zero`.
uses
hash_probe_expected_cost_zero_tail_prob_zerorw [hsum, hash_probe_expected_cost_zero_tail_prob_zero]
Finset.filter_true_of_mem- If every element in a finset satisfies a predicate, filtering by that predicate returns the finset itself.
Nat.not_lt_zero- No natural number is strictly less than zero.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type is the cardinality of that type.
Fintype.card_prod- The cardinality of a product type is the product of the cardinalities of its factors.
Fintype.card_fun- The cardinality of the function type $\alpha \to \beta$ is $|\beta|^{|\alpha|}$.
Fintype.card_fin- The cardinality of `Fin n` is $n$.
ZMod.card- The cardinality of $\mathbb{Z}/n\mathbb{Z}$ is $n$.
Finset.card_eq_zero- A finset has cardinality 0 if and only if it is empty.
Finset.filter_eq_empty_iff- A filtered finset is empty if and only if no element in the finset satisfies the predicate.
List.ofFn_zero- Constructing a list from a function out of `Fin 0` yields the empty list.
hash_occupied_slots_nil- The set of occupied slots resulting from an empty sequence of insertions is the empty set.
hash_probe_expected_cost_zero_tail_count_zero- In an empty table ($t = 0$), the tail count at $k = 0$ is $n$.
hash_probe_expected_cost_zero_tail_count_succ- In an empty table ($t = 0$), the tail count at any successor index $k + 1$ is 0.
hash_probe_expected_cost_zero_tail_prob_zero- In an empty table ($t = 0$), the tail probability at $k = 0$ is 1.
hash_probe_expected_cost_zero_tail_prob_succ- In an empty table ($t = 0$), the tail probability at any successor index $k + 1$ is 0.
Finset.sum_eq_single- If all elements of a finset other than a designated element $a$ evaluate to 0, the sum over the finset equals the value at $a$ (or 0 if $a$ is not in the set).
Nat.exists_eq_succ_of_ne_zero- Any non-zero natural number is the successor of some natural number ($n = k + 1$).
Finset.mem_range.mpr- If $a < b$, then $a$ belongs to `Finset.range b`.
Nat.succ_pos- For any natural number $n$, $0 < n + 1$.
- The definition of expected probe cost uses tail probabilities: $\mathbb{E}[X] = \sum_{k=0}^n \mathbb{P}(X \ge k)$, where each tail probability is the count of qualifying sequences divided by $n^{t+1}$.
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.
private lemma hash_probe_expected_cost_zero_tail_count_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) : hash_probe_tail_count n r 0 0 = n := by unfold hash_probe_tail_count have hh : (Finset.univ.filter (fun (p : (Fin 0 → ZMod n) × ZMod n) => ∀ j : Fin n, j.val < 0 → p.2 + r j ∈ hash_occupied_slots n r (List.ofFn p.1))) = Finset.univ := by apply Finset.filter_true_of_mem intro x hx j hj exact absurd hj (Nat.not_lt_zero _) rw [hh, Finset.card_univ, Fintype.card_prod, Fintype.card_fun, Fintype.card_fin] simp [ZMod.card]private lemma hash_probe_expected_cost_zero_tail_count_succ (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k : ℕ) : hash_probe_tail_count n r 0 (k + 1) = 0 := by unfold hash_probe_tail_count rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro p _ hh have h0 := hh (0 : Fin n) (by simp) rw [List.ofFn_zero, hash_occupied_slots_nil] at h0 simpa using h0private lemma hash_probe_expected_cost_zero_tail_prob_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) : hash_probe_tail_prob n r 0 0 = 1 := by unfold hash_probe_tail_prob rw [hash_probe_expected_cost_zero_tail_count_zero] norm_numprivate lemma hash_probe_expected_cost_zero_tail_prob_succ (n : ℕ) [NeZero n] (r : Fin n → ZMod n) (k : ℕ) : hash_probe_tail_prob n r 0 (k + 1) = 0 := by unfold hash_probe_tail_prob rw [hash_probe_expected_cost_zero_tail_count_succ] simp/-- Inserting into an empty table always takes expected cost 1. -/theorem hash_probe_expected_cost_zero (n : ℕ) [NeZero n] (r : Fin n → ZMod n) : hash_probe_expected_cost n r 0 = 1 := by unfold hash_probe_expected_cost have hsum : ∑ k ∈ Finset.range (n + 1), hash_probe_tail_prob n r 0 k = hash_probe_tail_prob n r 0 0 := by apply Finset.sum_eq_single 0 · intro b _ hb0 obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hb0 exact hash_probe_expected_cost_zero_tail_prob_succ n r k · intro h0 exact absurd (Finset.mem_range.mpr (Nat.succ_pos n)) h0 rw [hsum, hash_probe_expected_cost_zero_tail_prob_zero]