CommunicationComplexity.Internal.invCdf_eq_iff
theoremverifiedimported Lean
Characterization of the inverse CDF. Let $p$ be a probability mass function on $\mathrm{Fin}\,m = \{0, 1, \dots, m-1\}$ with $m \ge 1$, and write $F(n) = \sum_{j < n} p(j) \in \bbr_{\ge 0}^{\infty}$ for its cumulative distribution function. Let $x \in \bbr_{\ge 0}^{\infty}$ satisfy $x < 1$, and let $i \in \mathrm{Fin}\,m$. Then the largest index whose cumulative probability does not exceed $x$ equals $i$ if and only if \[ F(i) \le x < F(i+1). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ENNReal in theorem CommunicationComplexity.Internal.invCdf_eq_iff {m : ℕ} [NeZero m] (p : PMF (Fin m)) (x : ℝ≥0∞) (hx : x < 1) (i : Fin m) : invCdf p x = i ↔ cdf p i ≤ x ∧ x < cdf p (i + 1)
- Source
- TCSlib, `CommunicationComplexity.Internal.invCdf_eq_iff`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Internal.invCdf_eq_iff← CommunicationComplexity.Internal.invCdf_eq_iff (TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:130): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- CommunicationComplexity.Internal.cdfGiven a probability mass function $p$ on $\mathrm{Fin}\,m$ and a natural number $n$, $\mathrm{cdf}(p, n)$ is the cumulative probability…
- CommunicationComplexity.Internal.cdf_zeroCumulative distribution function vanishes at zero. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$. Then the cumulative…
- CommunicationComplexity.Internal.cdf_oneTotal cumulative probability equals one. Let $p$ be a probability mass function on the finite set…
- CommunicationComplexity.Internal.invCdfGiven a PMF $p$ on $\mathrm{Fin}\,m$ (with $m \ge 1$) and a value $x \in \mathbb{R}_{\ge 0}^\infty$, $\mathrm{invCdf}(p, x)$ is the…
- CommunicationComplexity.Internal.cdf_monoMonotonicity of the cumulative distribution function. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$, and for each natural…
- Used by 1
- CommunicationComplexity.Internal.uniformApprox_approxUniform approximation error bound. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$ with $m \ge 1$, and let $n \ge 1$ be an…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen scoped ENNReal in/-- For `x < 1`, `invCdf p x = i` if and only if `x` lies in the half-open interval `[cdf p i, cdf p (i + 1))`. **Proof sketch.** `invCdf p x` is the maximum of the set of indices `j` with `cdf p j ≤ x`. If `i` is that maximum then `cdf p i ≤ x` by membership; and either `i + 1 < m`, in which case `i + 1` is not in the set (it would exceed the maximum), so `x < cdf p (i + 1)`, or `i + 1 = m`, in which case `cdf p (i + 1) = 1 > x`. Conversely, if `cdf p i ≤ x < cdf p (i + 1)` then `i` is in the set, and every `b` in the set has `cdf p b ≤ x < cdf p (i + 1)`, hence `b < i + 1` by monotonicity of `cdf`; so `i` is the maximum. -/theorem CommunicationComplexity.Internal.invCdf_eq_iff {m : ℕ} [NeZero m] (p : PMF (Fin m)) (x : ℝ≥0∞) (hx : x < 1) (i : Fin m) : invCdf p x = i ↔ cdf p i ≤ x ∧ x < cdf p (i + 1) := by constructor · intro h unfold invCdf at h rw [Finset.max'_eq_iff] at h constructor · have h := h.1 simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h exact h · have h := h.2 by_cases hi : i + 1 < m · specialize h ⟨i + 1, hi⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h by_contra hcontra rw [not_lt] at hcontra specialize h hcontra rw [← Fin.val_fin_le] at h simp at h · have hi : i + 1 = m := by omega rw [hi, cdf_one] trivial · rintro ⟨hlo, hhi⟩ unfold invCdf rw [Finset.max'_eq_iff] constructor · simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hlo · intro b hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb have hlt := lt_of_le_of_lt hb hhi have hmono := Monotone.reflect_lt (cdf_mono p) hlt omega