Documentation

Averaging.OpportunisticSigns

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.

theorem Averaging.Opportunistic.choose_sq_mul_le_nat (m k : ℕ) :
m.choose k ^ 2 * (m + 1) ≤ 4 ^ m

Central binomial bound in ℕ: choose m k ^ 2 * (m + 1) ≤ 4 ^ m.

theorem Averaging.Opportunistic.choose_sq_mul_le (m k : ℕ) :
↑(m.choose k) ^ 2 * (↑m + 1) ≤ 4 ^ m

(T1) Central binomial bound.

theorem Averaging.Opportunistic.choose_div_le (m k : ℕ) :
↑(m.choose k) / 2 ^ m ≤ 1 / √(↑m + 1)

(T1') Each binomial weight is at most 1/√(m+1).

The law of the sum of the signs #

def Averaging.Opportunistic.negSet {I : Type u_1} [Fintype I] (τ : I → ℤˣ) :

The indices carrying the sign -1.

Equations
Instances For

    Sign vectors correspond to the sets of their -1 positions.

    Equations
    Instances For
      theorem Averaging.Opportunistic.signVec_eq_one_sub {I : Type u_1} (τ : I → ℤˣ) (i : I) :
      signVec τ i = 1 - 2 * if τ i = -1 then 1 else 0

      Each sign is 1 - 2 [τ i = -1].

      theorem Averaging.Opportunistic.sum_signVec_eq {I : Type u_1} [Fintype I] (τ : I → ℤˣ) :
      ∑ i : I, signVec τ i = ↑(Fintype.card I) - 2 * ↑(negSet τ).card

      The sum of the signs is m - 2 #{i | τ i = -1}.

      theorem Averaging.Opportunistic.avg_fun_sum_signVec {I : Type u_1} [Fintype I] [DecidableEq I] (F : ℝ → ℝ) :
      (Dynamics.avg fun (τ : I → ℤˣ) => F (∑ i : I, signVec τ i)) = ∑ k ∈ Finset.range (Fintype.card I + 1), ↑((Fintype.card I).choose k) / 2 ^ Fintype.card I * F (↑(Fintype.card I) - 2 * ↑k)

      (T0) The law of a sum of m independent uniform signs: binomial pushforward.

      theorem Averaging.Opportunistic.avg_fun_sum_signVec_le {I : Type u_1} [Fintype I] [DecidableEq I] (F : ℝ → ℝ) (hF : ∀ (x : ℝ), 0 ≤ F x) :
      (Dynamics.avg fun (τ : I → ℤˣ) => F (∑ i : I, signVec τ i)) ≤ (∑ k ∈ Finset.range (Fintype.card I + 1), F (↑(Fintype.card I) - 2 * ↑k)) / √(↑(Fintype.card I) + 1)

      The law of the sum against a nonnegative test function, with every binomial weight bounded by 1 / √(m + 1).

      theorem Averaging.Opportunistic.sum_range_ite_eq_zero_le (m : ℕ) :
      (∑ k ∈ Finset.range (m + 1), if ↑m - 2 * ↑k = 0 then 1 else 0) ≤ 1

      At most one k satisfies m - 2 k = 0.

      theorem Averaging.Opportunistic.avg_sum_signVec_eq_zero {I : Type u_1} [Fintype I] [DecidableEq I] :
      (Dynamics.avg fun (τ : I → ℤˣ) => if ∑ i : I, signVec τ i = 0 then 1 else 0) ≤ 1 / √(↑(Fintype.card I) + 1)

      (T2a) Point mass at zero.

      theorem Averaging.Opportunistic.card_filter_abs_le (m : ℕ) (r : ℝ) (hr : 0 ≤ r) :
      ↑{k ∈ Finset.range (m + 1) | |↑m - 2 * ↑k| ≤ r}.card ≤ r + 1

      At most r + 1 indices k ≤ m satisfy |m - 2 k| ≤ r.

      theorem Averaging.Opportunistic.avg_abs_sum_signVec_le {I : Type u_1} [Fintype I] [DecidableEq I] (r : ℝ) (hr : 0 ≤ r) :
      (Dynamics.avg fun (τ : I → ℤˣ) => if |∑ i : I, signVec τ i| ≤ r then 1 else 0) ≤ (r + 1) / √(↑(Fintype.card I) + 1)

      (T2b) Anti-concentration in an interval around zero.

      theorem Averaging.Opportunistic.abs_sub_two_mul_eq (m k : ℕ) :
      |↑m - 2 * ↑k| = ↑(↑m - 2 * ↑k).natAbs

      |m - 2 k| is the cast of the natural number Int.natAbs (m - 2 k).

      theorem Averaging.Opportunistic.card_fiber_le_two (m j : ℕ) :
      {k ∈ Finset.range (m + 1) | (↑m - 2 * ↑k).natAbs = j}.card ≤ 2

      Each value of |m - 2 k| is taken by at most two indices k.

      The harmonic number H_m as ∑_{j ≤ m} j⁻¹ (the term 0⁻¹ = 0 is harmless).

      theorem Averaging.Opportunistic.sum_inv_abs_le (m : ℕ) :
      ∑ k ∈ Finset.range (m + 1), |↑m - 2 * ↑k|⁻¹ ≤ 2 * ↑(harmonic m)

      ∑_{k ≤ m} |m - 2 k|⁻¹ ≤ 2 H_m.

      theorem Averaging.Opportunistic.avg_inv_abs_sum_signVec {I : Type u_1} [Fintype I] [DecidableEq I] :
      (Dynamics.avg fun (τ : I → ℤˣ) => if ∑ i : I, signVec τ i = 0 then 0 else 1 / |∑ i : I, signVec τ i|) ≤ 2 * (1 + Real.log ↑(Fintype.card I)) / √(↑(Fintype.card I) + 1)

      (T2c) The inverse absolute value of the sum, on the event that it is nonzero.

      Second moment, symmetry, first moment #

      theorem Averaging.Opportunistic.signVec_mul_self {I : Type u_1} (τ : I → ℤˣ) (i : I) :
      signVec τ i * signVec τ i = 1

      The square of a sign is 1.

      theorem Averaging.Opportunistic.signVec_mulSingle_mul {I : Type u_1} [DecidableEq I] (τ : I → ℤˣ) (i j : I) :
      signVec (Pi.mulSingle i (-1) * τ) j = if j = i then -signVec τ j else signVec τ j

      Multiplying by Pi.mulSingle i (-1) flips the sign at i only.

      theorem Averaging.Opportunistic.avg_eq_zero_of_equiv_neg {α : Type u_2} [Fintype α] (e : α ≃ α) (f : α → ℝ) (h : ∀ (a : α), f (e a) = -f a) :

      An average that changes sign under a bijection of the sample space vanishes.

      theorem Averaging.Opportunistic.avg_signVec_mul_signVec {I : Type u_1} [Fintype I] [DecidableEq I] (i j : I) :
      (Dynamics.avg fun (τ : I → ℤˣ) => signVec τ i * signVec τ j) = if i = j then 1 else 0

      Distinct signs are uncorrelated: E[σ i σ j] = [i = j].

      theorem Averaging.Opportunistic.avg_sum_mul_signVec_sq {I : Type u_1} [Fintype I] [DecidableEq I] (w : I → ℝ) :
      (Dynamics.avg fun (τ : I → ℤˣ) => (∑ i : I, w i * signVec τ i) ^ 2) = ∑ i : I, w i ^ 2

      (T4) Second moment of a weighted sum of independent signs.

      theorem Averaging.Opportunistic.sum_signVec_neg {I : Type u_1} [Fintype I] (τ : I → ℤˣ) :
      ∑ i : I, signVec (-τ) i = -∑ i : I, signVec τ i

      Flipping all signs negates the sum.

      theorem Averaging.Opportunistic.avg_fun_neg_sum_signVec {I : Type u_1} [Fintype I] [DecidableEq I] (F : ℝ → ℝ) :
      (Dynamics.avg fun (τ : I → ℤˣ) => F (-∑ i : I, signVec τ i)) = Dynamics.avg fun (τ : I → ℤˣ) => F (∑ i : I, signVec τ i)

      (T5) Symmetry: flipping all signs.

      theorem Averaging.Opportunistic.sq_avg_le_avg_sq {α : Type u_2} [Fintype α] [Nonempty α] (f : α → ℝ) :
      Dynamics.avg f ^ 2 ≤ Dynamics.avg fun (a : α) => f a ^ 2

      Jensen for the square: (E f)² ≤ E f².

      theorem Averaging.Opportunistic.avg_abs_sum_signVec_le_sqrt {I : Type u_1} [Fintype I] [DecidableEq I] :
      (Dynamics.avg fun (τ : I → ℤˣ) => |∑ i : I, signVec τ i|) ≤ √↑(Fintype.card I)

      (T6) First absolute moment.

      theorem Averaging.Opportunistic.avg_sum_signVec_pos {I : Type u_1} [Fintype I] [DecidableEq I] :
      (Dynamics.avg fun (τ : I → ℤˣ) => if 0 < ∑ i : I, signVec τ i then 1 else 0) = (1 - Dynamics.avg fun (τ : I → ℤˣ) => if ∑ i : I, signVec τ i = 0 then 1 else 0) / 2

      (T7) The sum is positive with probability (1 - P(sum = 0)) / 2.