CommunicationComplexity.Internal.cdf_succ
theoremverifiedimported Lean
CDF successor recurrence. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$, and let $n \in \mathrm{Fin}\,m$. Then the cumulative distribution function satisfies $\mathrm{cdf}(p, n+1) = \mathrm{cdf}(p, n) + p(n)$, where the sums are taken as extended non-negative reals in $\bbr_{\ge 0}^\infty$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ENNReal in lemma CommunicationComplexity.Internal.cdf_succ {m : ℕ} (p : PMF (Fin m)) (n : Fin m) : cdf p (n + 1) = cdf p n + p n
- Source
- TCSlib, `CommunicationComplexity.Internal.cdf_succ`
- 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.cdf_succ← CommunicationComplexity.Internal.cdf_succ (TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:77): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- 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/-- The cumulative distribution function increases by `p n` from `n` to `n + 1`. -/lemma CommunicationComplexity.Internal.cdf_succ {m : ℕ} (p : PMF (Fin m)) (n : Fin m) : cdf p (n + 1) = cdf p n + p n := by simp only [cdf] -- Split: ∑ (if j < n+1 ...) = ∑ (if j < n ...) + ∑ (if j = n ...) have key : ∀ j : Fin m, (if (j : ℕ) < (n : ℕ) + 1 then (p j : ℝ≥0∞) else 0) = (if (j : ℕ) < (n : ℕ) then p j else 0) + (if j = n then p n else 0) := by intro j split_ifs with h1 h2 <;> simp_all <;> omega simp_rw [key, Finset.sum_add_distrib, Finset.sum_ite_eq', Finset.mem_univ, if_true]