AFTD Auto-Formalizing Theoretical Domains

hash_probe_expected_cost_zero

theoremverified

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

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.

  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`.

    lines 3–8

    uses Finset.filter_true_of_mem, Nat.not_lt_zero

      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 _)
  2. 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`.

    lines 9–10

    uses Finset.card_univ, Fintype.card_prod, Fintype.card_fun, Fintype.card_fin, ZMod.card

      rw [hh, Finset.card_univ, Fintype.card_prod, Fintype.card_fun, Fintype.card_fin]
      simp [ZMod.card]
  3. 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$.

    lines 14–19

    uses Finset.card_eq_zero, Finset.filter_eq_empty_iff, List.ofFn_zero, hash_occupied_slots_nil

      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 h0
  4. 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.

    lines 23–25

    uses hash_probe_expected_cost_zero_tail_count_zero

      unfold hash_probe_tail_prob
      rw [hash_probe_expected_cost_zero_tail_count_zero]
      norm_num
  5. 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.

    lines 29–31

    uses hash_probe_expected_cost_zero_tail_count_succ

      unfold hash_probe_tail_prob
      rw [hash_probe_expected_cost_zero_tail_count_succ]
      simp
  6. 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`).

    lines 36–44

    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_pos

      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
  7. 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`.

    line 45

    uses hash_probe_expected_cost_zero_tail_prob_zero

      rw [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$.

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

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