Conditional collision marginal.
ProvedExactFailure.card_inter_collisionEvent_mulaether-cataloggeometry
Conditional collision marginal. If the event G places no constraint on
the coordinate y, then conditionally on G the collision H y = H x still has
probability exactly 1/M. Taking G = univ recovers
AlmostLossless.card_collisionEvent_mul.
theorem ExactFailure.card_inter_collisionEvent_mul{G : Finset (ι → Fin M)} {y x : ι}
(hG : UnconstrainedAt G y) (hyx : y ≠ x) :
M * (G ∩ collisionEvent M y x).card = G.card := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Geometry/ExactFailureMarginal.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Geometry/ExactFailureMarginal.lean
import Mathlib
import Definitions.Def_Geometry_AlmostLosslessCore
import Definitions.Def_Geometry_ExactFailureMarginal
/-
# Which marginals? The exact failure law of the random codebook
Research thread *Compression Beyond the Pigeonhole Bound*, cycle v19c.
`Geometry.AlmostLosslessConverse` obtains `P[failure] ≥ k/(2M)` (for `2(k-1) ≤ M`)
by feeding two marginals into the Bonferroni inequality, and
`Geometry.BonferroniMarginals` improves this to the unconditional `k/(M+k-1)` by
feeding the *same* two marginals into the second-moment inequality. Both are
lower bounds. This file closes the question completely: the failure probability
of the uniform random codebook is *computed exactly*,
`P[failure] = 1 - (1 - 1/M)^k`, `k = |S \ {x}|`,
and both the Shannon upper bound and a matching lower bound are then elementary
consequences. The mechanism is a **conditional marginal principle**: the
collision event `H y = H x` has probability exactly `1/M` *conditionally on any
event that does not constrain the coordinate `y`*. That is the precise sense in
which the almost-lossless analysis is a statement about marginals.
Main results.
* `ExactFailure.card_inter_collisionEvent_mul` — the **conditional collision
marginal**: `M · |G ∩ {H : H y = H x}| = |G|` for every `G` unconstrained at
`y` (`y ≠ x`). A strict generalisation of
`AlmostLossless.card_collisionEvent_mul` (take `G = univ`).
* `ExactFailure.card_noCollisionEvent_mul` — by induction along the competitors:
`M^k · |{H : H y ≠ H x for all y ∈ D}| = (M-1)^k · M^{|α|}`, `k = |D|`.
* `ExactFailure.card_failSet_exact` — the **exact failure count**
`M^k · |failSet| + (M-1)^k · M^{|α|} = M^k · M^{|α|}`.
* `ExactFailure.failure_prob_exact` — `P[failure] = 1 - (1 - 1/M)^k`.
* `ExactFailure.failure_prob_le_shannon` — recovers the random-coding bound
`P[failure] ≤ k/M` (`AlmostLossless.failSet_prob_le`) from the exact law.
* `ExactFailure.failure_prob_ge_harmonic` — the matching lower bound
`P[failure] ≥ k/(M+k)`, proved from the exact law by Bernoulli's inequality.
Together the two show `P[failure] = Θ(k/M)` for **all** `k` and `M`.
-/
open ExactFailure
open Finset AlmostLossless
variable {ι : Type*} [Fintype ι] [DecidableEq ι] {M : ℕ}
/-! ## 1. The conditional collision marginal -/Formal statement
theorem ExactFailure.card_inter_collisionEvent_mul{G : Finset (ι → Fin M)} {y x : ι}
(hG : UnconstrainedAt G y) (hyx : y ≠ x) :
M * (G ∩ collisionEvent M y x).card = G.card := by sorrySource