Documentation

Median.BinaryAux

The binary median dynamics: one round as a sum of independent coordinates #

With two values, the median rule keeps a node's value unless both sampled nodes hold the other one; a node holding true ends true unless both samples are false, and vice versa. The number of true nodes after one round is therefore a sum over the nodes of independent {0,1} coordinates, one per node, each depending only on that node's own pair of samples. This file develops the corresponding bookkeeping:

The median of three Bools #

theorem Median.med3_true (b c : Bool) :
med3 true b c = max b c

A true node takes the maximum of its two samples.

theorem Median.med3_false (b c : Bool) :
med3 false b c = min b c

A false node takes the minimum of its two samples.

Counts as real sums #

def Median.falsesR {n : ℕ} (x : Config n Bool) :

Number of false nodes, as a real.

Equations
Instances For
    def Median.gapR {n : ℕ} (x : Config n Bool) :

    The gap ones - falses, as a real.

    Equations
    Instances For
      theorem Median.ones_le {n : ℕ} (x : Config n Bool) :
      ones x ≤ n
      theorem Median.gapR_le {n : ℕ} (x : Config n Bool) :
      gapR x ≤ ↑n
      theorem Median.cast_nat_sub {n : ℕ} (x : Config n Bool) :
      ↑(n - ones x) = falsesR x

      The cast of the natural difference n - ones x.

      theorem Median.sum_ite_true_false {n : ℕ} (x : Config n Bool) :
      ((∑ v : Fin n, if x v = true then 1 else 0) + ∑ v : Fin n, if x v = false then 1 else 0) = ↑n
      theorem Median.ones_eq_sum {n : ℕ} (x : Config n Bool) :
      ↑(ones x) = ∑ v : Fin n, if x v = true then 1 else 0
      theorem Median.falsesR_eq_sum {n : ℕ} (x : Config n Bool) :
      falsesR x = ∑ v : Fin n, if x v = false then 1 else 0
      theorem Median.eq_true_iff_falsesR_zero {n : ℕ} {x : Config n Bool} :
      (x = fun (x : Fin n) => true) ↔ falsesR x = 0

      Only the all-true configuration has no false node.

      One round as a sum of independent coordinates #

      def Median.coord {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :

      The {0,1} coordinate of node v: whether v holds true after one round.

      Equations
      Instances For
        def Median.fcoord {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :

        The complementary coordinate: whether v holds false after one round.

        Equations
        Instances For
          theorem Median.coord_zero_one {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :
          coord x v p = 0 ∨ coord x v p = 1
          theorem Median.fcoord_zero_one {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :
          fcoord x v p = 0 ∨ fcoord x v p = 1
          theorem Median.coord_nonneg {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :
          0 ≤ coord x v p
          theorem Median.fcoord_nonneg {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :
          0 ≤ fcoord x v p
          theorem Median.fcoord_le_one {n : ℕ} (x : Config n Bool) (v : Fin n) (p : Fin n × Fin n) :
          fcoord x v p ≤ 1
          theorem Median.ones_step_sum {n : ℕ} (x : Config n Bool) (r : Round n) :
          ↑(ones (step x r)) = ∑ v : Fin n, coord x v (r v)

          The number of true nodes after a round is the sum of the coordinates.

          theorem Median.falses_step_sum {n : ℕ} (x : Config n Bool) (r : Round n) :
          falsesR (step x r) = ∑ v : Fin n, fcoord x v (r v)

          The number of false nodes after a round is the sum of the complementary coordinates.

          Per-node expectations #

          theorem Median.avg_false_ind {n : ℕ} (x : Config n Bool) :
          (Dynamics.avg fun (u : Fin n) => if x u = false then 1 else 0) = falsesR x / ↑n
          theorem Median.avg_true_ind {n : ℕ} (x : Config n Bool) :
          (Dynamics.avg fun (u : Fin n) => if x u = true then 1 else 0) = ↑(ones x) / ↑n
          theorem Median.avg_coord_of_true {n : ℕ} (x : Config n Bool) [NeZero n] {v : Fin n} (hv : x v = true) :
          Dynamics.avg (coord x v) = 1 - (falsesR x / ↑n) ^ 2

          A true node stays true unless both samples are false.

          theorem Median.avg_coord_of_false {n : ℕ} (x : Config n Bool) [NeZero n] {v : Fin n} (hv : x v = false) :
          Dynamics.avg (coord x v) = (↑(ones x) / ↑n) ^ 2

          A false node turns true only if both samples are true.

          theorem Median.sum_avg_coord {n : ℕ} (x : Config n Bool) [NeZero n] :
          ∑ v : Fin n, Dynamics.avg (coord x v) = ↑(ones x) + ↑(ones x) * falsesR x * gapR x / ↑n ^ 2

          The expected number of true nodes after one round.

          theorem Median.sum_avg_fcoord {n : ℕ} (x : Config n Bool) [NeZero n] :
          ∑ v : Fin n, Dynamics.avg (fcoord x v) = falsesR x - ↑(ones x) * falsesR x * gapR x / ↑n ^ 2

          The expected number of false nodes after one round.

          Expectation bounds #

          theorem Median.falses_plus_ones {n : ℕ} (x : Config n Bool) :
          ↑(ones x) + falsesR x = ↑n
          theorem Median.gapR_eq {n : ℕ} (x : Config n Bool) :
          gapR x = ↑(ones x) - falsesR x
          theorem Median.le_of_mul_le_mul_right' {p q d : ℝ} (hd : 0 < d) (h : p * d ≤ q * d) :
          p ≤ q

          Multiplying both sides of a ≤ by a positive factor preserves it.

          theorem Median.ones_mul_falses {n : ℕ} (x : Config n Bool) [NeZero n] :
          ↑(ones x) * falsesR x = (↑n ^ 2 - gapR x ^ 2) / 4

          The product of the two counts is (n² - gap²)/4.

          theorem Median.expfalses_le {n : ℕ} (x : Config n Bool) [NeZero n] :
          ∑ v : Fin n, Dynamics.avg (fcoord x v) ≤ 3 * falsesR x ^ 2 / ↑n

          The expected number of false nodes after one round is at most 3m²/n.

          theorem Median.expfalses_le_three_fourth {n : ℕ} (x : Config n Bool) [NeZero n] (hm : falsesR x ≤ ↑n / 4) :
          ∑ v : Fin n, Dynamics.avg (fcoord x v) ≤ 3 / 4 * falsesR x

          Below n/4 false nodes, the expected number of false nodes drops by a factor 3/4: 𝔼[m'] ≤ (3/4) m.

          theorem Median.expfalses_le_five_eighth {n : ℕ} (x : Config n Bool) [NeZero n] (hm : falsesR x ≤ ↑n / 4) :
          ∑ v : Fin n, Dynamics.avg (fcoord x v) ≤ 5 / 8 * falsesR x

          Below n/4 false nodes, 𝔼[m'] ≤ (5/8) m.

          theorem Median.expones_ge {n : ℕ} (x : Config n Bool) [NeZero n] (hg0 : 0 ≤ gapR x) (hg : gapR x ≤ ↑n / 2) :
          ↑n / 2 + 11 / 16 * gapR x ≤ ∑ v : Fin n, Dynamics.avg (coord x v)

          While the gap is at most n/2, the expected number of true nodes after one round satisfies n/2 + (11/16) g ≤ 𝔼[ones'].

          Concentration for one round #

          theorem Median.ones_tail_lower {n : ℕ} (x : Config n Bool) [NeZero n] {lam : ℝ} (hlam : 0 ≤ lam) :
          (Dynamics.avg fun (r : Round n) => if ↑(ones (step x r)) + lam ≤ ∑ v : Fin n, Dynamics.avg (coord x v) then 1 else 0) ≤ Real.exp (-(2 * lam ^ 2 / ↑n))

          Probability that one round produces at most 𝔼 - lam true nodes.

          theorem Median.falses_tail_upper {n : ℕ} (x : Config n Bool) [NeZero n] {lam : ℝ} (hlam : 0 ≤ lam) :
          (Dynamics.avg fun (r : Round n) => if ∑ v : Fin n, Dynamics.avg (fcoord x v) + lam ≤ falsesR (step x r) then 1 else 0) ≤ Real.exp (-(2 * lam ^ 2 / ↑n))

          Probability that one round produces at least 𝔼 + lam false nodes.

          theorem Median.falses_tail_bernstein {n : ℕ} (x : Config n Bool) [NeZero n] {lam σ2 : ℝ} (hlam : 0 ≤ lam) (hσ0 : 0 < σ2) (hvar : ∑ v : Fin n, Dynamics.variance (fcoord x v) ≤ σ2) :
          (Dynamics.avg fun (r : Round n) => if ∑ v : Fin n, Dynamics.avg (fcoord x v) + lam ≤ falsesR (step x r) then 1 else 0) ≤ Real.exp (-(lam ^ 2 / (2 * σ2 * (1 + lam / (3 * σ2)))))

          Bernstein's bound for the number of false nodes after one round.

          theorem Median.falses_tail_markov {n : ℕ} (x : Config n Bool) [NeZero n] :
          (Dynamics.avg fun (r : Round n) => if 1 ≤ falsesR (step x r) then 1 else 0) ≤ ∑ v : Fin n, Dynamics.avg (fcoord x v)

          Markov's inequality: the probability of a false node after one round is at most the expected number of false nodes (Dynamics.avg_markov_one).