Sums of independent uniform signs #
Elementary facts about S = ∑ i, σ i for a uniform sign vector σ : I → ℤˣ: the law of S is
the binomial pushforward k ↦ m - 2 k (avg_fun_sum_signVec), every binomial weight is at most
1 / √(m + 1) (choose_div_le), hence anti-concentration bounds, the second moment of weighted
sums, and the symmetry S ↦ -S. The independence of disjoint blocks of signs is the core's
Dynamics.avg_pi_split.
Binomial bounds #
Central binomial bound, even case: centralBinom j ^ 2 * (2 j + 1) ≤ 16 ^ j.
The odd middle binomial coefficient is half of the next central one.
The law of the sum of the signs #
The indices carrying the sign -1.
Equations
- Averaging.Opportunistic.negSet τ = {i : I | τ i = -1}
Instances For
Sign vectors correspond to the sets of their -1 positions.
Equations
- Averaging.Opportunistic.signEquiv = { toFun := Averaging.Opportunistic.negSet, invFun := fun (s : Finset I) (i : I) => if i ∈ s then -1 else 1, left_inv := ⋯, right_inv := ⋯ }
Instances For
(T0) The law of a sum of m independent uniform signs: binomial pushforward.
The law of the sum against a nonnegative test function, with every binomial weight bounded
by 1 / √(m + 1).
(T2a) Point mass at zero.
The harmonic number H_m as ∑_{j ≤ m} j⁻¹ (the term 0⁻¹ = 0 is harmless).
(T2c) The inverse absolute value of the sum, on the event that it is nonzero.
Second moment, symmetry, first moment #
Multiplying by Pi.mulSingle i (-1) flips the sign at i only.
(T4) Second moment of a weighted sum of independent signs.
(T5) Symmetry: flipping all signs.
Jensen for the square: (E f)² ≤ E f².
(T6) First absolute moment.
(T7) The sum is positive with probability (1 - P(sum = 0)) / 2.