CommunicationComplexity.Internal.uniformApprox_approx
Uniform 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 integer. For each $j \in \mathrm{Fin}\,n$, let $\varphi(j) \in \mathrm{Fin}\,m$ be the largest index $k$ whose cumulative probability $\sum_{\ell < k} p(\ell)$ does not exceed $j/n$; equivalently, $\varphi$ evaluates the generalized inverse (quantile function) of the cumulative distribution function of $p$ at the $n$ equally spaced points $0, 1/n, \dots, (n-1)/n$. Then for every index $i \in \mathrm{Fin}\,m$, the fraction of these $n$ points that $\varphi$ sends to $i$ exceeds the true probability $p(i)$ by at most $1/n$: \[ \frac{\abs{\{\, j \in \mathrm{Fin}\,n : \varphi(j) = i \,\}}}{n} \;\le\; p(i) + \frac{1}{n}, \] where $p(i)$ is read as a real number.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ENNReal in theorem CommunicationComplexity.Internal.uniformApprox_approx {m : ℕ} [NeZero m] (p : PMF (Fin m)) (n : ℕ) [NeZero n] (i : Fin m) : ((Finset.univ.filter (fun j : Fin n => uniformApprox p n j = i)).card : ℝ) / n ≤ (p i).toReal + 1 / n
- Source
- TCSlib, `CommunicationComplexity.Internal.uniformApprox_approx`
- 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.uniformApprox_approx← CommunicationComplexity.Internal.uniformApprox_approx (TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:219): adapted
What was changed in
CommunicationComplexity.Internal.uniformApprox_approx--- TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:219 (CommunicationComplexity.Internal.uniformApprox_approx) +++ as compiled here @@ -1,13 +1,6 @@ -/-- The pushforward of the uniform distribution on `Fin n` along `uniformApprox p n` -overshoots `p` by at most `1/n` at every point: the fraction of grid points `j` with -`uniformApprox p n j = i` is at most `p i + 1/n`. - -**Proof sketch.** Step 1: `cdf p i ≤ cdf p (i + 1) ≤ 1`, so both values are finite. -Step 2: by `invCdf_eq_iff`, a grid point `j` is mapped to `i` exactly when -`cdf p i ≤ j/n < cdf p (i + 1)`; converting from `ℝ≥0∞` to real numbers, the preimage -of `i` is contained in the set of `j` with `cdf p i · n ≤ j < cdf p (i + 1) · n`. -Step 3: by `card_nat_in_Ico` that set has at most `cdf p (i + 1) · n − cdf p i · n + 1` -elements. Step 4: since `cdf p (i + 1) − cdf p i = p i`, dividing by `n` gives the -bound `p i + 1/n`. -/ -theorem uniformApprox_approx {m : ℕ} [NeZero m] (p : PMF (Fin m)) (n : ℕ) [NeZero n] (i : Fin m) : +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +open MeasureTheory in +open scoped ENNReal in +theorem CommunicationComplexity.Internal.uniformApprox_approx {m : ℕ} [NeZero m] (p : PMF (Fin m)) (n : ℕ) [NeZero n] (i : Fin m) : ((Finset.univ.filter (fun j : Fin n => uniformApprox p n j = i)).card : ℝ) / n @@ -33,3 +26,3 @@ simp [show (j : ℕ) < n from j.isLt] - obtain ⟨hlo, hhi⟩ := (invCdf_eq_iff p _ hlt i).mp hj + obtain ⟨hlo, hhi⟩ := (invCdf_eq_iff p _ hlt i).mp (Finset.mem_filter.mp hj).2 have hjn_toReal : ((j : ℝ≥0∞) / n).toReal = (j : ℝ) / n := by - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- 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_monoMonotonicity of the cumulative distribution function. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$, and for each natural…
- CommunicationComplexity.Internal.cdf_oneTotal cumulative probability equals one. Let $p$ be a probability mass function on the finite set…
- CommunicationComplexity.Internal.cdf_succCDF successor recurrence. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$, and let $n \in \mathrm{Fin}\,m$. Then the…
- CommunicationComplexity.Internal.invCdf_eq_iffCharacterization of the inverse CDF. Let $p$ be a probability mass function on $\mathrm{Fin}\,m = \{0, 1, \dots, m-1\}$ with $m \ge 1$,…
- CommunicationComplexity.Internal.uniformApproxGiven a PMF $p$ on $\mathrm{Fin}\,m$ and a positive integer $n$, the map…
- CommunicationComplexity.Internal.card_nat_in_IcoCounting bound in a real interval. Fix $n \in \bbn$ and real numbers $a \le b$. Among the integers $j \in \{0, 1, \dots, n-1\}$, the…
- 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.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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- CommunicationComplexity.Internal.single_coin_approxApproximating a finite probability space by fair coin flips. Let $\Omega$ be a finite probability space, and let $\delta > 0$. Then there…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ENNReal in /-- The pushforward of the uniform distribution on `Fin n` along `uniformApprox p n` overshoots `p` by at most `1/n` at every point: the fraction of grid points `j` with `uniformApprox p n j = i` is at most `p i + 1/n`. **Proof sketch.** Step 1: `cdf p i ≤ cdf p (i + 1) ≤ 1`, so both values are finite. Step 2: by `invCdf_eq_iff`, a grid point `j` is mapped to `i` exactly when `cdf p i ≤ j/n < cdf p (i + 1)`; converting from `ℝ≥0∞` to real numbers, the preimage of `i` is contained in the set of `j` with `cdf p i · n ≤ j < cdf p (i + 1) · n`. Step 3: by `card_nat_in_Ico` that set has at most `cdf p (i + 1) · n − cdf p i · n + 1` elements. Step 4: since `cdf p (i + 1) − cdf p i = p i`, dividing by `n` gives the bound `p i + 1/n`. -/ theorem CommunicationComplexity.Internal.uniformApprox_approx {m : ℕ} [NeZero m] (p : PMF (Fin m)) (n : ℕ) [NeZero n] (i : Fin m) : ((Finset.univ.filter (fun j : Fin n => uniformApprox p n j = i)).card : ℝ) / n ≤ (p i).toReal + 1 / n := by -- Characterize the preimage: invCdf p (j/n) = i iff cdf p i ≤ j/n < cdf p (i+1) -- Convert ENNReal div conditions to ℝ mul conditions: cdf.toReal*n ≤ j < cdf(i+1).toReal*n -- Step 1: the two cdf values are ordered, at most 1, and finite have hn_pos : (0 : ℝ) < n := Nat.cast_pos.mpr (NeZero.pos n) have hcdf_le : cdf p i ≤ cdf p (i + 1) := cdf_mono p (Nat.le_succ _) have hcdf_le1 : cdf p (i + 1) ≤ 1 := by calc cdf p (i + 1) ≤ cdf p m := cdf_mono p (by omega) _ = 1 := cdf_one p have hcdf_fin : cdf p i ≠ ⊤ := ne_top_of_le_ne_top ENNReal.one_ne_top (hcdf_le.trans hcdf_le1) have hcdf1_fin : cdf p (i + 1) ≠ ⊤ := ne_top_of_le_ne_top ENNReal.one_ne_top hcdf_le1 -- Step 2: the preimage of i is contained in a half-open interval of grid points have hset : Finset.univ.filter (fun j : Fin n => uniformApprox p n j = i) ⊆ Finset.univ.filter (fun j : Fin n => (cdf p i).toReal * n ≤ (j : ℝ) ∧ (j : ℝ) < (cdf p (i + 1)).toReal * n) := by intro j hj simp only [Finset.mem_filter, Finset.mem_univ, true_and, uniformApprox] at hj ⊢ have hlt : (j : ℝ≥0∞) / n < 1 := by rw [ENNReal.div_lt_iff (by simp [NeZero.ne n]) (by simp)] simp [show (j : ℕ) < n from j.isLt] obtain ⟨hlo, hhi⟩ := (invCdf_eq_iff p _ hlt i).mp (Finset.mem_filter.mp hj).2 have hjn_toReal : ((j : ℝ≥0∞) / n).toReal = (j : ℝ) / n := by rw [ENNReal.toReal_div, ENNReal.toReal_natCast, ENNReal.toReal_natCast] constructor · -- cdf p i ≤ j/n (ENNReal) → cdf.toReal * n ≤ j (ℝ) rw [← le_div_iff₀ hn_pos] rw [← hjn_toReal] exact ENNReal.toReal_mono (ne_top_of_lt hlt) hlo · -- j/n < cdf p (i+1) (ENNReal) → j < cdf(i+1).toReal * n (ℝ) rw [← div_lt_iff₀ hn_pos, ← hjn_toReal] exact (ENNReal.toReal_lt_toReal (ne_top_of_lt hlt) hcdf1_fin).mpr hhi have hcard := Finset.card_le_card hset -- Step 3: apply the ℝ counting lemma have hab_real : (cdf p i).toReal ≤ (cdf p (i + 1)).toReal := (ENNReal.toReal_le_toReal hcdf_fin hcdf1_fin).mpr hcdf_le have hint := card_nat_in_Ico n ((cdf p i).toReal * n) ((cdf p (i + 1)).toReal * n) (mul_le_mul_of_nonneg_right hab_real (Nat.cast_nonneg _)) -- Step 4: cdf p (i+1).toReal - cdf p i.toReal = (p i).toReal, then divide by n have hdiff : (cdf p (↑i + 1)).toReal - (cdf p i).toReal = (p i).toReal := by rw [cdf_succ, ENNReal.toReal_add hcdf_fin (PMF.apply_lt_top p _).ne, add_sub_cancel_left] calc ((Finset.univ.filter _).card : ℝ) / n ≤ ((Finset.univ.filter _).card : ℝ) / n := div_le_div_of_nonneg_right (by exact_mod_cast hcard) hn_pos.le _ ≤ ((cdf p (i + 1)).toReal * n - (cdf p i).toReal * n + 1) / n := div_le_div_of_nonneg_right hint hn_pos.le _ = (p i).toReal + 1 / n := by rw [← hdiff]; field_simp