Analysis of Boolean Functions in Lean

8.4. Biased analysis🔗

Definition8.4.1
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 2
Reverse dependency previews
Preview
Definition 8.4.2
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 8.39. In p-biased analysis put q=1-p, \qquad \mu=q-p=1-2p, \qquad \sigma=\sqrt{4pq}=2\sqrt{p(1-p)}. For one biased sign define \phi(x)=\frac{x-\mu}{\sigma}. Then \sigma^2=1-\mu^2, \qquad \phi(1)=\sqrt{p/q}, \qquad \phi(-1)=-\sqrt{q/p}.

Lean code for Definition8.4.112 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasComplement (p : ) : 
    def FABL.biasComplement (p : ) : 
    O'Donnell, Definition 8.39: `q = 1 - p`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasMean (p : ) : 
    def FABL.biasMean (p : ) : 
    O'Donnell, Definition 8.39: the mean `μ = q - p = 1 - 2p`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasVarianceScale (p : ) : 
    def FABL.biasVarianceScale (p : ) : 
    O'Donnell, Definition 8.39: the variance scale `σ² = 4p(1-p)`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasSigma (p : ) : 
    def FABL.biasSigma (p : ) : 
    O'Donnell, Definition 8.39: `σ = √(4p(1-p))`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasMean_mem_Icc (p : ) (hp : p  Set.Icc 0 1) :
      FABL.biasMean p  Set.Icc (-1) 1
    theorem FABL.biasMean_mem_Icc (p : )
      (hp : p  Set.Icc 0 1) :
      FABL.biasMean p  Set.Icc (-1) 1
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasSigma_sq (p : ) (hp : p  Set.Icc 0 1) :
      FABL.biasSigma p ^ 2 = FABL.biasVarianceScale p
    theorem FABL.biasSigma_sq (p : )
      (hp : p  Set.Icc 0 1) :
      FABL.biasSigma p ^ 2 =
        FABL.biasVarianceScale p
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasSigma_pos (p : ) (hp : p  Set.Ioo 0 1) : 0 < FABL.biasSigma p
    theorem FABL.biasSigma_pos (p : )
      (hp : p  Set.Ioo 0 1) :
      0 < FABL.biasSigma p
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedStandardizedSign (p : ) (x : FABL.Sign) : 
    def FABL.biasedStandardizedSign (p : )
      (x : FABL.Sign) : 
    Definition 8.39's normalized centered one-bit function. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedStandardizedSign_one_eq_sqrt (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.biasedStandardizedSign p 1 = (p / (1 - p))
    theorem FABL.biasedStandardizedSign_one_eq_sqrt
      (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.biasedStandardizedSign p 1 =
        (p / (1 - p))
    Definition 8.39's displayed value `φ(1) = √(p/q)`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedStandardizedSign_neg_one_eq_neg_sqrt (p : )
      (hp : p  Set.Ioo 0 1) :
      FABL.biasedStandardizedSign p (-1) = -((1 - p) / p)
    theorem FABL.biasedStandardizedSign_neg_one_eq_neg_sqrt
      (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.biasedStandardizedSign p (-1) =
        -((1 - p) / p)
    Definition 8.39's displayed value `φ(-1) = -√(q/p)`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.pmfExpectation_biasedStandardizedSign (p : )
      (hp : p  Set.Ioo 0 1) :
      FABL.pmfExpectation (FABL.biasedSignPMF p )
          (FABL.biasedStandardizedSign p) =
        0
    theorem FABL.pmfExpectation_biasedStandardizedSign
      (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.pmfExpectation
          (FABL.biasedSignPMF p )
          (FABL.biasedStandardizedSign p) =
        0
    The standardized sign has mean zero. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.pmfExpectation_biasedStandardizedSign_sq (p : )
      (hp : p  Set.Ioo 0 1) :
      (FABL.pmfExpectation (FABL.biasedSignPMF p ) fun x =>
          FABL.biasedStandardizedSign p x ^ 2) =
        1
    theorem FABL.pmfExpectation_biasedStandardizedSign_sq
      (p : ) (hp : p  Set.Ioo 0 1) :
      (FABL.pmfExpectation
          (FABL.biasedSignPMF p ) fun x =>
          FABL.biasedStandardizedSign p x ^
            2) =
        1
    The standardized sign has second moment one. 
Definition8.4.2
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 3
Statement dependency previews
Preview
Theorem 8.1.13
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 8
Reverse dependency previews
Preview
Lemma 8.4.3
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 8.40. The p-biased product Fourier basis is \phi_S(x)=\prod_{i\in S}\phi(x_i). For f:\{-1,1\}^n\to\mathbb R, \widehat f(S) =\mathbb E_{x\sim\pi_p^{\otimes n}}[f(x)\phi_S(x)], \qquad f(x)=\sum_{S\subseteq[n]}\widehat f(S)\phi_S(x). In general \phi_S\phi_T\ne\phi_{S\mathbin\triangle T}.

Lean code for Definition8.4.215 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedSignPMF (p : ) (hp : p  Set.Icc 0 1) : PMF FABL.Sign
    def FABL.biasedSignPMF (p : )
      (hp : p  Set.Icc 0 1) : PMF FABL.Sign
    The book's `πₚ`: a sign is `-1` with probability `p` and `+1` with probability `1-p`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedSignPMF_apply_toReal (p : ) (hp : p  Set.Icc 0 1)
      (x : FABL.Sign) :
      ((FABL.biasedSignPMF p hp) x).toReal = if x = 1 then 1 - p else p
    theorem FABL.biasedSignPMF_apply_toReal (p : )
      (hp : p  Set.Icc 0 1) (x : FABL.Sign) :
      ((FABL.biasedSignPMF p hp) x).toReal =
        if x = 1 then 1 - p else p
    Point masses of the biased sign law, expressed as real probabilities. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedSignPMF_hasFullSupport (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.PMFHasFullSupport (FABL.biasedSignPMF p )
    theorem FABL.biasedSignPMF_hasFullSupport (p : )
      (hp : p  Set.Ioo 0 1) :
      FABL.PMFHasFullSupport
        (FABL.biasedSignPMF p )
    The biased sign law has full support for `0 < p < 1`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.pmfExpectation_biasedSignPMF_signValue (p : )
      (hp : p  Set.Icc 0 1) :
      FABL.pmfExpectation (FABL.biasedSignPMF p hp) FABL.signValue =
        FABL.biasMean p
    theorem FABL.pmfExpectation_biasedSignPMF_signValue
      (p : ) (hp : p  Set.Icc 0 1) :
      FABL.pmfExpectation
          (FABL.biasedSignPMF p hp)
          FABL.signValue =
        FABL.biasMean p
    The biased sign has mean `μ = 1 - 2p`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedSiteFourierFunction (p : ) (j : Fin 2) (x : FABL.Sign) : 
    def FABL.biasedSiteFourierFunction (p : )
      (j : Fin 2) (x : FABL.Sign) : 
    The two one-site functions `1, φ` from Definition 8.39. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedSiteFourierFunction_orthonormal (p : )
      (hp : p  Set.Ioo 0 1) (a b : Fin 2) :
      (FABL.pmfExpectation (FABL.biasedSignPMF p ) fun x =>
          FABL.biasedSiteFourierFunction p a x *
            FABL.biasedSiteFourierFunction p b x) =
        if a = b then 1 else 0
    theorem FABL.biasedSiteFourierFunction_orthonormal
      (p : ) (hp : p  Set.Ioo 0 1)
      (a b : Fin 2) :
      (FABL.pmfExpectation
          (FABL.biasedSignPMF p ) fun x =>
          FABL.biasedSiteFourierFunction p a
              x *
            FABL.biasedSiteFourierFunction p b
              x) =
        if a = b then 1 else 0
    The biased one-site family is orthonormal. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedSiteBasis (p : ) (hp : p  Set.Ioo 0 1) :
      Module.Basis (Fin 2)  (FABL.Sign  )
    def FABL.biasedSiteBasis (p : )
      (hp : p  Set.Ioo 0 1) :
      Module.Basis (Fin 2)  (FABL.Sign  )
    The algebraic basis underlying the biased one-site Fourier basis. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedSiteFourierBasis (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.FiniteFourierBasis FABL.Sign (FABL.biasedSignPMF p ) (Fin 2)
    def FABL.biasedSiteFourierBasis (p : )
      (hp : p  Set.Ioo 0 1) :
      FABL.FiniteFourierBasis FABL.Sign
        (FABL.biasedSignPMF p ) (Fin 2)
    O'Donnell, Definitions 8.39--8.40: the biased single-site Fourier basis. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.subsetMultiIndex {n : } (S : Finset (Fin n)) :
      FABL.MultiIndex n (Fin 2)
    def FABL.subsetMultiIndex {n : }
      (S : Finset (Fin n)) :
      FABL.MultiIndex n (Fin 2)
    The binary multi-index associated with a subset. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.finsetEquivBinaryMultiIndex (n : ) :
      Finset (Fin n)  FABL.MultiIndex n (Fin 2)
    def FABL.finsetEquivBinaryMultiIndex (n : ) :
      Finset (Fin n) 
        FABL.MultiIndex n (Fin 2)
    Subsets and binary multi-indices are equivalent. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedMonomial {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (S : Finset (Fin n)) (x : FABL.SignCube n) : 
    def FABL.biasedMonomial {n : } (p : )
      (hp : p  Set.Ioo 0 1)
      (S : Finset (Fin n))
      (x : FABL.SignCube n) : 
    O'Donnell, Definition 8.40: the biased monomial `φ_S`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedMonomial_apply {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (S : Finset (Fin n)) (x : FABL.SignCube n) :
      FABL.biasedMonomial p hp S x =
         i  S, FABL.biasedStandardizedSign p (x i)
    theorem FABL.biasedMonomial_apply {n : } (p : )
      (hp : p  Set.Ioo 0 1)
      (S : Finset (Fin n))
      (x : FABL.SignCube n) :
      FABL.biasedMonomial p hp S x =
         i  S,
          FABL.biasedStandardizedSign p (x i)
    The biased monomial is the product of standardized signs on `S`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedFourierCoeff {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) (S : Finset (Fin n)) : 
    def FABL.biasedFourierCoeff {n : } (p : )
      (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  )
      (S : Finset (Fin n)) : 
    O'Donnell, Definition 8.40: the `p`-biased Fourier coefficient. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_eq_expect {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp f S =
        FABL.pmfExpectation
          (FABL.productProbabilityPMF (FABL.biasedSignPMF p ) n) fun x =>
          f x * FABL.biasedMonomial p hp S x
    theorem FABL.biasedFourierCoeff_eq_expect {n : }
      (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  )
      (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp f S =
        FABL.pmfExpectation
          (FABL.productProbabilityPMF
            (FABL.biasedSignPMF p ) n)
          fun x =>
          f x * FABL.biasedMonomial p hp S x
    Biased Fourier coefficients are weighted correlations with `φ_S`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biased_fourier_expansion {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) (x : FABL.SignCube n) :
      f x =
         S, FABL.biasedFourierCoeff p hp f S * FABL.biasedMonomial p hp S x
    theorem FABL.biased_fourier_expansion {n : }
      (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  )
      (x : FABL.SignCube n) :
      f x =
         S,
          FABL.biasedFourierCoeff p hp f S *
            FABL.biasedMonomial p hp S x
    O'Donnell, Definition 8.40: the biased Fourier expansion. 
Lemma8.4.3
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Example 8.41. The dictator satisfies x_i=\mu+\sigma\phi(x_i). Thus its only nonzero biased Fourier coefficients are \widehat{\chi_i}(\varnothing)=\mu and \widehat{\chi_i}(\{i\})=\sigma.

Lean code for Lemma8.4.35 theorems
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.signValue_eq_biasMean_add_sigma_mul_biasedMonomial_singleton
      {n : } (p : ) (hp : p  Set.Ioo 0 1) (i : Fin n)
      (x : FABL.SignCube n) :
      FABL.signValue (x i) =
        FABL.biasMean p + FABL.biasSigma p * FABL.biasedMonomial p hp {i} x
    theorem FABL.signValue_eq_biasMean_add_sigma_mul_biasedMonomial_singleton
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) (x : FABL.SignCube n) :
      FABL.signValue (x i) =
        FABL.biasMean p +
          FABL.biasSigma p *
            FABL.biasedMonomial p hp {i} x
    Example 8.41: a dictator has constant and singleton biased-Fourier parts. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_dictator {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp (fun x => FABL.signValue (x i)) S =
        if S =  then FABL.biasMean p
        else if S = {i} then FABL.biasSigma p else 0
    theorem FABL.biasedFourierCoeff_dictator {n : }
      (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp
          (fun x => FABL.signValue (x i)) S =
        if S =  then FABL.biasMean p
        else
          if S = {i} then FABL.biasSigma p
          else 0
    Example 8.41: the exact biased Fourier coefficient table of a dictator. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_dictator_empty {n : } (p : )
      (hp : p  Set.Ioo 0 1) (i : Fin n) :
      FABL.biasedFourierCoeff p hp (fun x => FABL.signValue (x i))  =
        FABL.biasMean p
    theorem FABL.biasedFourierCoeff_dictator_empty
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) :
      FABL.biasedFourierCoeff p hp
          (fun x => FABL.signValue (x i))  =
        FABL.biasMean p
    Example 8.41's three coefficient clauses as separate reusable statements. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_dictator_singleton {n : } (p : )
      (hp : p  Set.Ioo 0 1) (i : Fin n) :
      FABL.biasedFourierCoeff p hp (fun x => FABL.signValue (x i)) {i} =
        FABL.biasSigma p
    theorem FABL.biasedFourierCoeff_dictator_singleton
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) :
      FABL.biasedFourierCoeff p hp
          (fun x => FABL.signValue (x i))
          {i} =
        FABL.biasSigma p
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_dictator_other {n : } (p : )
      (hp : p  Set.Ioo 0 1) (i : Fin n) (S : Finset (Fin n)) (hS0 : S  )
      (hSi : S  {i}) :
      FABL.biasedFourierCoeff p hp (fun x => FABL.signValue (x i)) S = 0
    theorem FABL.biasedFourierCoeff_dictator_other
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) (S : Finset (Fin n))
      (hS0 : S  ) (hSi : S  {i}) :
      FABL.biasedFourierCoeff p hp
          (fun x => FABL.signValue (x i)) S =
        0
Lemma8.4.4
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Example 8.42. Let \operatorname{Sel}(x_1,x_2,x_3) equal x_2 when x_1=-1 and x_3 when x_1=1. Its biased expansion is \begin{aligned} \operatorname{Sel}={}&\mu +(\tfrac12-\tfrac12\mu)\sigma\phi_2 +(\tfrac12+\tfrac12\mu)\sigma\phi_3\\ &-\tfrac12\sigma^2\phi_1\phi_2 +\tfrac12\sigma^2\phi_1\phi_3. \end{aligned}

Lean code for Lemma8.4.42 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.selectionFunction (x : FABL.SignCube 3) : FABL.Sign
    def FABL.selectionFunction
      (x : FABL.SignCube 3) : FABL.Sign
    O'Donnell, Example 8.42: the first bit selects the second or third bit. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.selectionFunction_biased_expansion (p : ) (hp : p  Set.Ioo 0 1)
      (x : FABL.SignCube 3) :
      FABL.signValue (FABL.selectionFunction x) =
        FABL.biasMean p +
                (1 / 2 - FABL.biasMean p / 2) * FABL.biasSigma p *
                  FABL.biasedMonomial p hp {1} x +
              (1 / 2 + FABL.biasMean p / 2) * FABL.biasSigma p *
                FABL.biasedMonomial p hp {2} x -
            1 / 2 * FABL.biasSigma p ^ 2 *
              FABL.biasedMonomial p hp {0, 1} x +
          1 / 2 * FABL.biasSigma p ^ 2 * FABL.biasedMonomial p hp {0, 2} x
    theorem FABL.selectionFunction_biased_expansion
      (p : ) (hp : p  Set.Ioo 0 1)
      (x : FABL.SignCube 3) :
      FABL.signValue
          (FABL.selectionFunction x) =
        FABL.biasMean p +
                (1 / 2 -
                      FABL.biasMean p / 2) *
                    FABL.biasSigma p *
                  FABL.biasedMonomial p hp {1}
                    x +
              (1 / 2 + FABL.biasMean p / 2) *
                  FABL.biasSigma p *
                FABL.biasedMonomial p hp {2}
                  x -
            1 / 2 * FABL.biasSigma p ^ 2 *
              FABL.biasedMonomial p hp {0, 1}
                x +
          1 / 2 * FABL.biasSigma p ^ 2 *
            FABL.biasedMonomial p hp {0, 2} x
    Example 8.42's exact biased Fourier expansion, stated pointwise. 
Definition8.4.5
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Notation 8.43. The notation f^{(p)} means that a fixed combinatorial function f:\{-1,1\}^n\to\mathbb R is regarded as an element of L^2(\{-1,1\}^n,\pi_p^{\otimes n}).

Lean code for Definition8.4.52 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedView {n : } (p : ) (_hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) : FABL.ProductL2 FABL.Sign n
    def FABL.biasedView {n : } (p : )
      (_hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) :
      FABL.ProductL2 FABL.Sign n
    O'Donnell, Notation 8.43: view a fixed cube function under the `p`-biased product law.
    The underlying function is unchanged; the explicit `p` and proof arguments prevent the law from
    being hidden at API boundaries. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_biasedView {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.SignCube n  )
      (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp (FABL.biasedView p hp f) S =
        FABL.biasedFourierCoeff p hp f S
    theorem FABL.biasedFourierCoeff_biasedView {n : }
      (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  )
      (S : Finset (Fin n)) :
      FABL.biasedFourierCoeff p hp
          (FABL.biasedView p hp f) S =
        FABL.biasedFourierCoeff p hp f S
    The public Notation 8.43 bridge preserves the expected biased coefficient API. 
Definition8.4.6
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.4.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 3
Reverse dependency previews
Preview
Theorem 8.4.7
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 8.44. The p-biased discrete derivative is D_i f(x) =\sigma\frac{f(x^{i\mapsto1})-f(x^{i\mapsto-1})}{2}. It acts on the biased expansion by D_i f =\sum_{S\ni i}\widehat f(S)\phi_{S\setminus\{i\}}.

Lean code for Definition8.4.65 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedDiscreteDerivative {n : } (p : ) (i : Fin n)
      (f : FABL.SignCube n  ) : FABL.SignCube n  
    def FABL.biasedDiscreteDerivative {n : }
      (p : ) (i : Fin n)
      (f : FABL.SignCube n  ) :
      FABL.SignCube n  
    O'Donnell, Definition 8.44: the biased discrete derivative. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedDiscreteDerivative_eq_sigma_mul {n : } (p : ) (i : Fin n)
      (f : FABL.SignCube n  ) :
      FABL.biasedDiscreteDerivative p i f = fun x =>
        FABL.biasSigma p * (FABL.discreteDerivative i) f x
    theorem FABL.biasedDiscreteDerivative_eq_sigma_mul
      {n : } (p : ) (i : Fin n)
      (f : FABL.SignCube n  ) :
      FABL.biasedDiscreteDerivative p i f =
        fun x =>
        FABL.biasSigma p *
          (FABL.discreteDerivative i) f x
    The biased derivative is `σ` times the canonical discrete derivative. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasSigma_mul_standardizedSign_difference_div_two (p : )
      (hp : p  Set.Ioo 0 1) :
      FABL.biasSigma p *
            (FABL.biasedStandardizedSign p 1 -
              FABL.biasedStandardizedSign p (-1)) /
          2 =
        1
    theorem FABL.biasSigma_mul_standardizedSign_difference_div_two
      (p : ) (hp : p  Set.Ioo 0 1) :
      FABL.biasSigma p *
            (FABL.biasedStandardizedSign p 1 -
              FABL.biasedStandardizedSign p
                (-1)) /
          2 =
        1
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedDiscreteDerivative_biasedMonomial {n : } (p : )
      (hp : p  Set.Ioo 0 1) (i : Fin n) (S : Finset (Fin n))
      (x : FABL.SignCube n) :
      FABL.biasedDiscreteDerivative p i (FABL.biasedMonomial p hp S) x =
        if i  S then FABL.biasedMonomial p hp (S.erase i) x else 0
    theorem FABL.biasedDiscreteDerivative_biasedMonomial
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (i : Fin n) (S : Finset (Fin n))
      (x : FABL.SignCube n) :
      FABL.biasedDiscreteDerivative p i
          (FABL.biasedMonomial p hp S) x =
        if i  S then
          FABL.biasedMonomial p hp (S.erase i)
            x
        else 0
    Definition 8.44: the biased derivative deletes a present basis coordinate and kills an
    absent one. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedDiscreteDerivative_eq_fourier_sum {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.SignCube n  ) (i : Fin n)
      (x : FABL.SignCube n) :
      FABL.biasedDiscreteDerivative p i f x =
         S with i  S,
          FABL.biasedFourierCoeff p hp f S *
            FABL.biasedMonomial p hp (S.erase i) x
    theorem FABL.biasedDiscreteDerivative_eq_fourier_sum
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) (i : Fin n)
      (x : FABL.SignCube n) :
      FABL.biasedDiscreteDerivative p i f x =
         S with i  S,
          FABL.biasedFourierCoeff p hp f S *
            FABL.biasedMonomial p hp
              (S.erase i) x
    Definition 8.44: the Fourier expansion of the biased derivative. 
Theorem8.4.7
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.2.7
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 3
Reverse dependency previews
Preview
Theorem 8.4.10
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Proposition 8.45. If f is \{-1,1\}-valued, then \operatorname{Inf}_i[f] =\sigma^2\Pr_{x\sim\pi_p^{\otimes n}} [f(x)\ne f(x^{\oplus i})], \mathbf I[f]=\sigma^2\mathbb E[\operatorname{sens}_f(x)]. If f is also monotone, then \operatorname{Inf}_i[f]=\sigma\widehat f(\{i\}).

Lean code for Theorem8.4.77 declarations
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.coordinateConditionalVariance_biasedSignPMF_toReal {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n) (i : Fin n)
      (x : FABL.SignCube n) :
      FABL.coordinateConditionalVariance (FABL.biasedSignPMF p ) f.toReal i
          x =
        FABL.biasSigma p ^ 2 *
          if f x  f (FABL.flipCoordinate x i) then 1 else 0
    theorem FABL.coordinateConditionalVariance_biasedSignPMF_toReal
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n) (i : Fin n)
      (x : FABL.SignCube n) :
      FABL.coordinateConditionalVariance
          (FABL.biasedSignPMF p ) f.toReal i
          x =
        FABL.biasSigma p ^ 2 *
          if
              f x 
                f
                  (FABL.flipCoordinate x
                    i) then
            1
          else 0
    Pointwise form of Proposition 8.45: the conditional coordinate variance of a Boolean
    function is `σ²` exactly when the coordinate is pivotal. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedFlipProbability {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n) (i : Fin n) : 
    def FABL.biasedFlipProbability {n : } (p : )
      (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (i : Fin n) : 
    Probability that flipping coordinate `i` changes a Boolean function under the biased product
    law. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.productInfluence_biased_eq_sigma_sq_mul_flipProbability {n : }
      (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n)
      (i : Fin n) :
      FABL.productInfluence (FABL.biasedSignPMF p ) f.toReal i =
        FABL.biasSigma p ^ 2 * FABL.biasedFlipProbability p hp f i
    theorem FABL.productInfluence_biased_eq_sigma_sq_mul_flipProbability
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (i : Fin n) :
      FABL.productInfluence
          (FABL.biasedSignPMF p ) f.toReal
          i =
        FABL.biasSigma p ^ 2 *
          FABL.biasedFlipProbability p hp f i
    Proposition 8.45: generalized influence equals `σ²` times deterministic-flip
    probability. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedSensitivity {n : } (f : FABL.BooleanFunction n)
      (x : FABL.SignCube n) : 
    def FABL.biasedSensitivity {n : }
      (f : FABL.BooleanFunction n)
      (x : FABL.SignCube n) : 
    Biased sensitivity is the number of pivotal coordinates at an input. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.productTotalInfluence_biased_eq_sigma_sq_mul_expect_sensitivity
      {n : } (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n) :
      FABL.productTotalInfluence (FABL.biasedSignPMF p ) f.toReal =
        FABL.biasSigma p ^ 2 *
          FABL.productMean (FABL.biasedSignPMF p ) fun x =>
            (FABL.biasedSensitivity f x)
    theorem FABL.productTotalInfluence_biased_eq_sigma_sq_mul_expect_sensitivity
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n) :
      FABL.productTotalInfluence
          (FABL.biasedSignPMF p ) f.toReal =
        FABL.biasSigma p ^ 2 *
          FABL.productMean
            (FABL.biasedSignPMF p ) fun x =>
            (FABL.biasedSensitivity f x)
    Proposition 8.45: total influence is `σ²` times expected sensitivity. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedFourierCoeff_singleton_eq_sigma_mul_expect_discreteDerivative
      {n : } (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.SignCube n  )
      (i : Fin n) :
      FABL.biasedFourierCoeff p hp f {i} =
        FABL.biasSigma p *
          FABL.productMean (FABL.biasedSignPMF p )
            ((FABL.discreteDerivative i) f)
    theorem FABL.biasedFourierCoeff_singleton_eq_sigma_mul_expect_discreteDerivative
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) (i : Fin n) :
      FABL.biasedFourierCoeff p hp f {i} =
        FABL.biasSigma p *
          FABL.productMean
            (FABL.biasedSignPMF p )
            ((FABL.discreteDerivative i) f)
    The singleton biased Fourier coefficient is `σ` times the biased mean of the canonical
    discrete derivative. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.productInfluence_biased_eq_sigma_mul_singletonCoeff_of_monotone
      {n : } (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n)
      (hf : Monotone f) (i : Fin n) :
      FABL.productInfluence (FABL.biasedSignPMF p ) f.toReal i =
        FABL.biasSigma p * FABL.biasedFourierCoeff p hp f.toReal {i}
    theorem FABL.productInfluence_biased_eq_sigma_mul_singletonCoeff_of_monotone
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (hf : Monotone f) (i : Fin n) :
      FABL.productInfluence
          (FABL.biasedSignPMF p ) f.toReal
          i =
        FABL.biasSigma p *
          FABL.biasedFourierCoeff p hp
            f.toReal {i}
    Proposition 8.45, monotone case: influence is `σ` times the singleton coefficient. 
Definition8.4.8
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 3
Reverse dependency previews
Preview
Lemma 8.4.9
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 8.46. A graph on v labeled vertices is identified with a point of \{\mathrm{True},\mathrm{False}\}^{\binom v2}. The law G(v,p) is the corresponding biased product law. A graph property is a Boolean function invariant under all vertex permutations; in particular it is transitive-symmetric in the edge coordinates.

Lean code for Definition8.4.810 declarations
  • abbrevdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    abbrev FABL.GraphEdge (v : ) : Type
    abbrev FABL.GraphEdge (v : ) : Type
    Definition 8.46: an undirected loopless edge is a two-element set of vertices. 
  • abbrevdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    abbrev FABL.EncodedGraph (v : ) : Type
    abbrev FABL.EncodedGraph (v : ) : Type
    Definition 8.46: an encoded graph records whether each possible edge is present. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.graphEdgePermEquiv {v : } (σ : Equiv.Perm (Fin v)) :
      FABL.GraphEdge v  FABL.GraphEdge v
    def FABL.graphEdgePermEquiv {v : }
      (σ : Equiv.Perm (Fin v)) :
      FABL.GraphEdge v  FABL.GraphEdge v
    Relabeling vertices induces an equivalence of the possible edges. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.permuteEncodedGraph {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) : FABL.EncodedGraph v
    def FABL.permuteEncodedGraph {v : }
      (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.EncodedGraph v
    Relabel an encoded graph by a vertex permutation. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.IsGraphProperty {v : } (P : FABL.EncodedGraph v  Bool) : Prop
    def FABL.IsGraphProperty {v : }
      (P : FABL.EncodedGraph v  Bool) : Prop
    Definition 8.46: a graph property is invariant under all vertex relabelings. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.EncodedGraphLE {v : } (G H : FABL.EncodedGraph v) : Prop
    def FABL.EncodedGraphLE {v : }
      (G H : FABL.EncodedGraph v) : Prop
    Coordinatewise inclusion of edge sets. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.IsMonotoneGraphProperty {v : } (P : FABL.EncodedGraph v  Bool) :
      Prop
    def FABL.IsMonotoneGraphProperty {v : }
      (P : FABL.EncodedGraph v  Bool) : Prop
    A graph predicate is monotone when adding edges cannot change true to false. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedBoolPMF (p : ) (hp : p  Set.Icc 0 1) : PMF Bool
    def FABL.biasedBoolPMF (p : )
      (hp : p  Set.Icc 0 1) : PMF Bool
    Boolean edge-presence law: `true` has probability `p`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.erdosRenyiPMF (v : ) (p : ) (hp : p  Set.Icc 0 1) :
      PMF (FABL.EncodedGraph v)
    def FABL.erdosRenyiPMF (v : ) (p : )
      (hp : p  Set.Icc 0 1) :
      PMF (FABL.EncodedGraph v)
    Definition 8.46: the finite Erdős--Rényi product law `G(v,p)`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.graphProperty_invariant {v : } {P : FABL.EncodedGraph v  Bool}
      (hP : FABL.IsGraphProperty P) (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) : P (FABL.permuteEncodedGraph σ G) = P G
    theorem FABL.graphProperty_invariant {v : }
      {P : FABL.EncodedGraph v  Bool}
      (hP : FABL.IsGraphProperty P)
      (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      P (FABL.permuteEncodedGraph σ G) = P G
    Definition 8.46's structural statement: graph properties are transitive-symmetric under the
    vertex-permutation action on edge coordinates. 
Lemma8.4.9
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Example 8.47. Connectivity, 3-colorability, containing a k-clique, edge-majority, and edge-parity are graph properties. Connectivity, clique containment, edge-majority, and the negation of 3-colorability are monotone.

Lean code for Lemma8.4.926 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.encodedGraphEdgeCount {v : } (G : FABL.EncodedGraph v) : 
    def FABL.encodedGraphEdgeCount {v : }
      (G : FABL.EncodedGraph v) : 
    Number of present edges. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.encodedGraphEdgeCount_permute {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.encodedGraphEdgeCount (FABL.permuteEncodedGraph σ G) =
        FABL.encodedGraphEdgeCount G
    theorem FABL.encodedGraphEdgeCount_permute {v : }
      (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.encodedGraphEdgeCount
          (FABL.permuteEncodedGraph σ G) =
        FABL.encodedGraphEdgeCount G
    Relabeling preserves the number of edges. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.edgeMajorityGraphProperty {v : } (G : FABL.EncodedGraph v) : Bool
    def FABL.edgeMajorityGraphProperty {v : }
      (G : FABL.EncodedGraph v) : Bool
    Example 8.47: the edge-majority predicate. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.edgeMajority_isGraphProperty (v : ) :
      FABL.IsGraphProperty FABL.edgeMajorityGraphProperty
    theorem FABL.edgeMajority_isGraphProperty
      (v : ) :
      FABL.IsGraphProperty
        FABL.edgeMajorityGraphProperty
    Example 8.47: edge majority is a graph property. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.edgeParityGraphProperty {v : } (G : FABL.EncodedGraph v) : Bool
    def FABL.edgeParityGraphProperty {v : }
      (G : FABL.EncodedGraph v) : Bool
    Example 8.47: parity of the number of graph edges. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.edgeParity_isGraphProperty (v : ) :
      FABL.IsGraphProperty FABL.edgeParityGraphProperty
    theorem FABL.edgeParity_isGraphProperty (v : ) :
      FABL.IsGraphProperty
        FABL.edgeParityGraphProperty
    Example 8.47: edge parity is a graph property. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.edgeMajority_isMonotoneGraphProperty (v : ) :
      FABL.IsMonotoneGraphProperty FABL.edgeMajorityGraphProperty
    theorem FABL.edgeMajority_isMonotoneGraphProperty
      (v : ) :
      FABL.IsMonotoneGraphProperty
        FABL.edgeMajorityGraphProperty
    Edge majority is monotone under addition of edges. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.EncodedGraphAdjacent {v : } (G : FABL.EncodedGraph v)
      (u w : Fin v) : Prop
    def FABL.EncodedGraphAdjacent {v : }
      (G : FABL.EncodedGraph v)
      (u w : Fin v) : Prop
    Adjacency in an encoded graph, expressed through the unique two-vertex edge containing a
    distinct pair. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.encodedGraphAdjacent_permute_iff {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) (u w : Fin v) :
      FABL.EncodedGraphAdjacent (FABL.permuteEncodedGraph σ G) (σ u) (σ w) 
        FABL.EncodedGraphAdjacent G u w
    theorem FABL.encodedGraphAdjacent_permute_iff
      {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v)
      (u w : Fin v) :
      FABL.EncodedGraphAdjacent
          (FABL.permuteEncodedGraph σ G) (σ u)
          (σ w) 
        FABL.EncodedGraphAdjacent G u w
    Vertex relabeling preserves encoded adjacency. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.EncodedGraphConnected {v : } (G : FABL.EncodedGraph v) : Prop
    def FABL.EncodedGraphConnected {v : }
      (G : FABL.EncodedGraph v) : Prop
    Connectivity is reachability in the reflexive-transitive closure of encoded adjacency. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.encodedGraphConnected_permute_iff {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphConnected (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphConnected G
    theorem FABL.encodedGraphConnected_permute_iff
      {v : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphConnected
          (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphConnected G
    Connectivity is invariant under vertex relabeling. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.EncodedGraphColorable {v q : } (G : FABL.EncodedGraph v) : Prop
    def FABL.EncodedGraphColorable {v q : }
      (G : FABL.EncodedGraph v) : Prop
    An encoded graph is `q`-colorable when adjacent vertices receive distinct colors in `Fin q`. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.encodedGraphColorable_permute_iff {v q : }
      (σ : Equiv.Perm (Fin v)) (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphColorable (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphColorable G
    theorem FABL.encodedGraphColorable_permute_iff
      {v q : } (σ : Equiv.Perm (Fin v))
      (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphColorable
          (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphColorable G
    Colorability is invariant under vertex relabeling. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.EncodedGraphContainsClique {v : } (k : )
      (G : FABL.EncodedGraph v) : Prop
    def FABL.EncodedGraphContainsClique {v : }
      (k : ) (G : FABL.EncodedGraph v) : Prop
    An encoded graph contains a `k`-clique when some `k` vertices are pairwise adjacent. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.encodedGraphContainsClique_permute_iff {v : }
      (σ : Equiv.Perm (Fin v)) (k : ) (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphContainsClique k (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphContainsClique k G
    theorem FABL.encodedGraphContainsClique_permute_iff
      {v : } (σ : Equiv.Perm (Fin v)) (k : )
      (G : FABL.EncodedGraph v) :
      FABL.EncodedGraphContainsClique k
          (FABL.permuteEncodedGraph σ G) 
        FABL.EncodedGraphContainsClique k G
    Fixed-size clique containment is invariant under vertex relabeling. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.connectivityGraphProperty {v : } (G : FABL.EncodedGraph v) : Bool
    def FABL.connectivityGraphProperty {v : }
      (G : FABL.EncodedGraph v) : Bool
    Example 8.47's connectivity predicate as a Boolean graph property. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.connectivity_isGraphProperty (v : ) :
      FABL.IsGraphProperty FABL.connectivityGraphProperty
    theorem FABL.connectivity_isGraphProperty
      (v : ) :
      FABL.IsGraphProperty
        FABL.connectivityGraphProperty
    Connectivity is a graph property. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.connectivity_isMonotoneGraphProperty (v : ) :
      FABL.IsMonotoneGraphProperty FABL.connectivityGraphProperty
    theorem FABL.connectivity_isMonotoneGraphProperty
      (v : ) :
      FABL.IsMonotoneGraphProperty
        FABL.connectivityGraphProperty
    Connectivity is monotone under edge addition. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.threeColorableGraphProperty {v : } (G : FABL.EncodedGraph v) :
      Bool
    def FABL.threeColorableGraphProperty {v : }
      (G : FABL.EncodedGraph v) : Bool
    Example 8.47's three-colorability predicate. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.threeColorable_isGraphProperty (v : ) :
      FABL.IsGraphProperty FABL.threeColorableGraphProperty
    theorem FABL.threeColorable_isGraphProperty
      (v : ) :
      FABL.IsGraphProperty
        FABL.threeColorableGraphProperty
    Three-colorability is a graph property. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.notThreeColorableGraphProperty {v : } (G : FABL.EncodedGraph v) :
      Bool
    def FABL.notThreeColorableGraphProperty
      {v : } (G : FABL.EncodedGraph v) : Bool
    The negation of three-colorability as a Boolean graph predicate. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.notThreeColorable_isGraphProperty (v : ) :
      FABL.IsGraphProperty FABL.notThreeColorableGraphProperty
    theorem FABL.notThreeColorable_isGraphProperty
      (v : ) :
      FABL.IsGraphProperty
        FABL.notThreeColorableGraphProperty
    Non-three-colorability is a graph property. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.notThreeColorable_isMonotoneGraphProperty (v : ) :
      FABL.IsMonotoneGraphProperty FABL.notThreeColorableGraphProperty
    theorem FABL.notThreeColorable_isMonotoneGraphProperty
      (v : ) :
      FABL.IsMonotoneGraphProperty
        FABL.notThreeColorableGraphProperty
    Non-three-colorability is monotone under edge addition. 
  • defdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    def FABL.containsCliqueGraphProperty {v : } (k : )
      (G : FABL.EncodedGraph v) : Bool
    def FABL.containsCliqueGraphProperty {v : }
      (k : ) (G : FABL.EncodedGraph v) : Bool
    Example 8.47's fixed-size clique-containment predicate. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.containsClique_isGraphProperty (v k : ) :
      FABL.IsGraphProperty (FABL.containsCliqueGraphProperty k)
    theorem FABL.containsClique_isGraphProperty
      (v k : ) :
      FABL.IsGraphProperty
        (FABL.containsCliqueGraphProperty k)
    Fixed-size clique containment is a graph property. 
  • theoremdefined in FABL/Chapter08/GraphPropertyExamples.lean
    complete
    theorem FABL.containsClique_isMonotoneGraphProperty (v k : ) :
      FABL.IsMonotoneGraphProperty (FABL.containsCliqueGraphProperty k)
    theorem FABL.containsClique_isMonotoneGraphProperty
      (v k : ) :
      FABL.IsMonotoneGraphProperty
        (FABL.containsCliqueGraphProperty k)
    Fixed-size clique containment is monotone under edge addition. 
Theorem8.4.10
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 3
Statement dependency previews
Preview
Definition 8.4.2
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 4
Reverse dependency previews
Preview
Lemma 8.4.11
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Margulis--Russo Formula. For f:\{-1,1\}^n\to\mathbb R, \frac{d}{d\mu}\mathbb E[f^{(p)}] =\frac1\sigma\sum_{i=1}^n\widehat{f^{(p)}}(\{i\}). If f is monotone and Boolean-valued, then \frac{d}{dp}\Pr_{\pi_p^{\otimes n}}[f=-1] =\frac{d}{d\mu}\mathbb E[f^{(p)}] =\frac1{\sigma^2}\mathbf I[f^{(p)}].

Lean code for Theorem8.4.109 declarations
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedExpectationPolynomial {n : } (f : FABL.SignCube n  )
      (μ : ) : 
    def FABL.biasedExpectationPolynomial {n : }
      (f : FABL.SignCube n  ) (μ : ) : 
    The finite polynomial giving `𝔼[f]` as a function of the common coordinate mean `μ`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedExpectationPolynomial_biasMean {n : } (p : )
      (hp : p  Set.Icc 0 1) (f : FABL.SignCube n  ) :
      FABL.biasedExpectationPolynomial f (FABL.biasMean p) =
        FABL.productMean (FABL.biasedSignPMF p hp) f
    theorem FABL.biasedExpectationPolynomial_biasMean
      {n : } (p : ) (hp : p  Set.Icc 0 1)
      (f : FABL.SignCube n  ) :
      FABL.biasedExpectationPolynomial f
          (FABL.biasMean p) =
        FABL.productMean
          (FABL.biasedSignPMF p hp) f
    Evaluation of the expectation polynomial at `μ = 1-2p` is the actual biased
    expectation. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.hasDerivAt_biasedExpectationPolynomial {n : }
      (f : FABL.SignCube n  ) (μ : ) :
      HasDerivAt (FABL.biasedExpectationPolynomial f)
        (∑ S, S.card * μ ^ (S.card - 1) * FABL.fourierCoeff f S) μ
    theorem FABL.hasDerivAt_biasedExpectationPolynomial
      {n : } (f : FABL.SignCube n  )
      (μ : ) :
      HasDerivAt
        (FABL.biasedExpectationPolynomial f)
        (∑ S,
          S.card * μ ^ (S.card - 1) *
            FABL.fourierCoeff f S)
        μ
    The derivative of the finite expectation polynomial. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.sum_productMean_biasedSignPMF_discreteDerivative {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.SignCube n  ) :
       i,
          FABL.productMean (FABL.biasedSignPMF p )
            ((FABL.discreteDerivative i) f) =
         S,
          S.card * FABL.biasMean p ^ (S.card - 1) * FABL.fourierCoeff f S
    theorem FABL.sum_productMean_biasedSignPMF_discreteDerivative
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) :
       i,
          FABL.productMean
            (FABL.biasedSignPMF p )
            ((FABL.discreteDerivative i) f) =
         S,
          S.card *
              FABL.biasMean p ^ (S.card - 1) *
            FABL.fourierCoeff f S
    Summing biased derivative means gives the formal derivative of the expectation
    polynomial. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.hasDerivAt_biasedExpectationPolynomial_eq_singletons {n : }
      (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.SignCube n  ) :
      HasDerivAt (FABL.biasedExpectationPolynomial f)
        ((FABL.biasSigma p)⁻¹ *  i, FABL.biasedFourierCoeff p hp f {i})
        (FABL.biasMean p)
    theorem FABL.hasDerivAt_biasedExpectationPolynomial_eq_singletons
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.SignCube n  ) :
      HasDerivAt
        (FABL.biasedExpectationPolynomial f)
        ((FABL.biasSigma p)⁻¹ *
           i,
            FABL.biasedFourierCoeff p hp f
              {i})
        (FABL.biasMean p)
    Margulis--Russo Formula (8.8): exact derivative with respect to `μ`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedMinusProbability {n : } (p : ) (hp : p  Set.Icc 0 1)
      (f : FABL.BooleanFunction n) : 
    def FABL.biasedMinusProbability {n : }
      (p : ) (hp : p  Set.Icc 0 1)
      (f : FABL.BooleanFunction n) : 
    The probability that a Boolean function has sign `-1`, under the actual biased law. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.biasedMinusProbabilityPolynomial {n : }
      (f : FABL.BooleanFunction n) (p : ) : 
    def FABL.biasedMinusProbabilityPolynomial
      {n : } (f : FABL.BooleanFunction n)
      (p : ) : 
    A globally defined finite polynomial for the biased `-1` probability. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.hasDerivAt_biasedMinusProbabilityPolynomial {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n) :
      HasDerivAt (FABL.biasedMinusProbabilityPolynomial f)
        ((FABL.biasSigma p)⁻¹ *
           i, FABL.biasedFourierCoeff p hp f.toReal {i})
        p
    theorem FABL.hasDerivAt_biasedMinusProbabilityPolynomial
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n) :
      HasDerivAt
        (FABL.biasedMinusProbabilityPolynomial
          f)
        ((FABL.biasSigma p)⁻¹ *
           i,
            FABL.biasedFourierCoeff p hp
              f.toReal {i})
        p
    The `p`-derivative of the `-1` probability polynomial is the Margulis--Russo singleton
    sum. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.hasDerivAt_biasedMinusProbabilityPolynomial_eq_totalInfluence
      {n : } (p : ) (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n)
      (hf : Monotone f) :
      HasDerivAt (FABL.biasedMinusProbabilityPolynomial f)
        (FABL.productTotalInfluence (FABL.biasedSignPMF p ) f.toReal /
          FABL.biasSigma p ^ 2)
        p
    theorem FABL.hasDerivAt_biasedMinusProbabilityPolynomial_eq_totalInfluence
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (hf : Monotone f) :
      HasDerivAt
        (FABL.biasedMinusProbabilityPolynomial
          f)
        (FABL.productTotalInfluence
            (FABL.biasedSignPMF p )
            f.toReal /
          FABL.biasSigma p ^ 2)
        p
    Margulis--Russo Formula (8.9): for monotone Boolean functions the `p`-derivative is
    `I[f]/σ²`. 
Lemma8.4.11
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 3
Reverse dependency previews
Preview
Lemma 8.4.12
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Remark 8.48. If f is a nonconstant monotone Boolean function, then p\mapsto\Pr_{\pi_p^{\otimes n}}[f=\mathrm{True}] is strictly increasing on (0,1).

Lean code for Lemma8.4.114 theorems
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.productVariance_biased_pos_of_nonconstant {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n)
      (hf : FABL.IsNonconstantCubeFunction f) :
      0 < FABL.productVariance (FABL.biasedSignPMF p ) f.toReal
    theorem FABL.productVariance_biased_pos_of_nonconstant
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (hf :
        FABL.IsNonconstantCubeFunction f) :
      0 <
        FABL.productVariance
          (FABL.biasedSignPMF p ) f.toReal
    A nonconstant Boolean function has positive variance under every full-support biased law. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.productTotalInfluence_biased_pos_of_nonconstant {n : } (p : )
      (hp : p  Set.Ioo 0 1) (f : FABL.BooleanFunction n)
      (hf : FABL.IsNonconstantCubeFunction f) :
      0 < FABL.productTotalInfluence (FABL.biasedSignPMF p ) f.toReal
    theorem FABL.productTotalInfluence_biased_pos_of_nonconstant
      {n : } (p : ) (hp : p  Set.Ioo 0 1)
      (f : FABL.BooleanFunction n)
      (hf :
        FABL.IsNonconstantCubeFunction f) :
      0 <
        FABL.productTotalInfluence
          (FABL.biasedSignPMF p ) f.toReal
    A nonconstant Boolean function has strictly positive total influence under the biased law. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.strictMonoOn_biasedMinusProbabilityPolynomial {n : }
      (f : FABL.BooleanFunction n) (hmono : Monotone f)
      (hnonconst : FABL.IsNonconstantCubeFunction f) :
      StrictMonoOn (FABL.biasedMinusProbabilityPolynomial f) (Set.Icc 0 1)
    theorem FABL.strictMonoOn_biasedMinusProbabilityPolynomial
      {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      StrictMonoOn
        (FABL.biasedMinusProbabilityPolynomial
          f)
        (Set.Icc 0 1)
    Remark 8.48: the probability polynomial of a nonconstant monotone Boolean function is
    strictly increasing on `[0,1]`. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedMinusProbability_strictMono {n : }
      (f : FABL.BooleanFunction n) (hmono : Monotone f)
      (hnonconst : FABL.IsNonconstantCubeFunction f) {p q : }
      (hp : p  Set.Icc 0 1) (hq : q  Set.Icc 0 1) (hpq : p < q) :
      FABL.biasedMinusProbability p hp f <
        FABL.biasedMinusProbability q hq f
    theorem FABL.biasedMinusProbability_strictMono
      {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f)
      {p q : } (hp : p  Set.Icc 0 1)
      (hq : q  Set.Icc 0 1) (hpq : p < q) :
      FABL.biasedMinusProbability p hp f <
        FABL.biasedMinusProbability q hq f
    Remark 8.48 stated for the actual biased probabilities at two parameters. 
Lemma8.4.12
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 2.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 2
Reverse dependency previews
Preview
Lemma 8.7.23
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Example 8.49, majority. For every \epsilon>0 there is C such that \Pr_{\pi_{1/2-C/\sqrt n}}[\operatorname{Maj}_n=\mathrm{True}] \le\epsilon, \qquad \Pr_{\pi_{1/2+C/\sqrt n}}[\operatorname{Maj}_n=\mathrm{True}] \ge1-\epsilon.

Lean code for Lemma8.4.122 declarations
  • defdefined in FABL/Chapter08/BiasedThresholdPhenomena.lean
    complete
    def FABL.condorcetConstant (epsilon : ) : 
    def FABL.condorcetConstant (epsilon : ) : 
    An explicit Condorcet constant whose two-sided Hoeffding error is at most `epsilon`. 
  • theoremdefined in FABL/Chapter08/BiasedThresholdPhenomena.lean
    complete
    theorem FABL.exists_condorcetMajorityThresholdBounds (epsilon : )
      (hepsilon : 0 < epsilon) :
       C  0,
        2 * Real.exp (-(2 * C ^ 2))  epsilon 
           (m : ),
            C / (2 * m + 1)  1 / 2 
              FABL.biasedMinusProbabilityPolynomial
                    (FABL.majority (2 * m + 1))
                    (1 / 2 - C / (2 * m + 1)) 
                  epsilon 
                1 - epsilon 
                  FABL.biasedMinusProbabilityPolynomial
                    (FABL.majority (2 * m + 1)) (1 / 2 + C / (2 * m + 1))
    theorem FABL.exists_condorcetMajorityThresholdBounds
      (epsilon : ) (hepsilon : 0 < epsilon) :
       C  0,
        2 * Real.exp (-(2 * C ^ 2)) 
            epsilon 
           (m : ),
            C / (2 * m + 1)  1 / 2 
              FABL.biasedMinusProbabilityPolynomial
                    (FABL.majority
                      (2 * m + 1))
                    (1 / 2 -
                      C / (2 * m + 1)) 
                  epsilon 
                1 - epsilon 
                  FABL.biasedMinusProbabilityPolynomial
                    (FABL.majority
                      (2 * m + 1))
                    (1 / 2 +
                      C / (2 * m + 1))
    Exercise 8.23, both majority threshold bounds with one explicit constant. 
Theorem8.4.13
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0XL∃∀N

Example 8.49, random graphs. As v\to\infty, a clique of size \log v in G(v,p) has probability tending to 0 for p<1/4 and to 1 for p>1/4. Connectivity has its threshold around p=\frac{\ln v}{v} \left(1\mathbin\pm\frac{\log\log v}{\log v}\right), with probability tending respectively to 0 and 1 on the two sides.

Definition8.4.14
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 6
Reverse dependency previews
Preview
Lemma 8.4.15
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Definition 8.50. For a nonconstant monotone Boolean function, the critical probability p_c\in(0,1) is the unique value such that \Pr_{\pi_{p_c}^{\otimes n}}[f=\mathrm{True}]=\frac12. Write q_c=1-p_c, \qquad \mu_c=1-2p_c, \qquad \sigma_c=\sqrt{4p_cq_c}.

Lean code for Definition8.4.148 declarations
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.existsUnique_criticalProbability {n : }
      (f : FABL.BooleanFunction n) (hmono : Monotone f)
      (hnonconst : FABL.IsNonconstantCubeFunction f) :
      ∃! p,
        p  Set.Ioo 0 1  FABL.biasedMinusProbabilityPolynomial f p = 1 / 2
    theorem FABL.existsUnique_criticalProbability
      {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      ∃! p,
        p  Set.Ioo 0 1 
          FABL.biasedMinusProbabilityPolynomial
              f p =
            1 / 2
    Existence and uniqueness of the critical probability from Definition 8.50. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.criticalProbability {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f) (hnonconst : FABL.IsNonconstantCubeFunction f) :
      
    def FABL.criticalProbability {n : }
      (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      
    Definition 8.50: the unique critical probability. 
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.criticalProbability_mem_Ioo {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f) (hnonconst : FABL.IsNonconstantCubeFunction f) :
      FABL.criticalProbability f hmono hnonconst  Set.Ioo 0 1
    theorem FABL.criticalProbability_mem_Ioo {n : }
      (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      FABL.criticalProbability f hmono
          hnonconst 
        Set.Ioo 0 1
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.biasedMinusProbability_criticalProbability {n : }
      (f : FABL.BooleanFunction n) (hmono : Monotone f)
      (hnonconst : FABL.IsNonconstantCubeFunction f) :
      FABL.biasedMinusProbability
          (FABL.criticalProbability f hmono hnonconst)  f =
        1 / 2
    theorem FABL.biasedMinusProbability_criticalProbability
      {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      FABL.biasedMinusProbability
          (FABL.criticalProbability f hmono
            hnonconst)
           f =
        1 / 2
    Definition 8.50 in terms of the actual biased probability. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.criticalComplement {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f) (hnonconst : FABL.IsNonconstantCubeFunction f) :
      
    def FABL.criticalComplement {n : }
      (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      
    Definition 8.50's associated `q_c`, `μ_c`, and `σ_c`. 
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.criticalMean {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f) (hnonconst : FABL.IsNonconstantCubeFunction f) :
      
    def FABL.criticalMean {n : }
      (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      
  • defdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    def FABL.criticalSigma {n : } (f : FABL.BooleanFunction n)
      (hmono : Monotone f) (hnonconst : FABL.IsNonconstantCubeFunction f) :
      
    def FABL.criticalSigma {n : }
      (f : FABL.BooleanFunction n)
      (hmono : Monotone f)
      (hnonconst :
        FABL.IsNonconstantCubeFunction f) :
      
  • theoremdefined in FABL/Chapter08/BiasedAnalysis.lean
    complete
    theorem FABL.criticalProbability_majority_odd (m : ) :
      FABL.criticalProbability (FABL.majority (2 * m + 1))   = 1 / 2
    theorem FABL.criticalProbability_majority_odd
      (m : ) :
      FABL.criticalProbability
          (FABL.majority (2 * m + 1))   =
        1 / 2
    The critical probability of odd majority is `1/2`. 
Lemma8.4.15
Group: Chapter 8: Generalized domains (128)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Theorem 8.4.10
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0XL∃∀N

Sharp-threshold principle. Roughly speaking, a monotone function has a sharp threshold near p_c exactly when its total influence at p_c is superconstant. Exercise 8.28 gives the precise sequential definition and the proved coarse-threshold consequence.