The law of a sum of independent integer random variables
DefinitionTwoFoldOPI_Supplement_sumLawcoding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
For distributions on , this is the distribution of for independent , i.e. the convolution (the point mass at when ).
It is the law of the sum in the local central limit theorem (Theorem 5.38).
Formalization Note Independence is built in: the law is the iterated convolution of probability mass functions.
Definition code
import Mathlib
namespace TwoFoldOPI
namespace Supplement
/-- **The law of a sum of independent integer random variables.**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.4, Theorem 5.38, p.34: "Let {Z_{r,i} : r ∈ [R], i ∈ [n_r]} be n independent random
variables with Z_{r,i} ∼ D_r for all i. Let Z = Σ_{r∈[R]} Σ_{i∈[n_r]} Z_{r,i}."
For a list `[D_1, …, D_N]` of distributions on `ℤ`, `sumLaw` is the distribution of
`Z_1 + ⋯ + Z_N` for independent `Z_j ∼ D_j` (the convolution `D_1 ∗ ⋯ ∗ D_N`); the empty list gives
the point mass at `0`.
**Formalization Note.** Independence is built in: the law is the iterated convolution, computed by
`PMF.bind`. -/
noncomputable def sumLaw : List (PMF ℤ) → PMF ℤ
| [] => PMF.pure 0
| D :: Ds => D.bind fun a => (sumLaw Ds).map fun b => a + b
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.4, Theorem 5.38, p. 34