8.4. Biased analysis
-
FABL.biasComplement[complete] -
FABL.biasMean[complete] -
FABL.biasVarianceScale[complete] -
FABL.biasSigma[complete] -
FABL.biasMean_mem_Icc[complete] -
FABL.biasSigma_sq[complete] -
FABL.biasSigma_pos[complete] -
FABL.biasedStandardizedSign[complete] -
FABL.biasedStandardizedSign_one_eq_sqrt[complete] -
FABL.biasedStandardizedSign_neg_one_eq_neg_sqrt[complete] -
FABL.pmfExpectation_biasedStandardizedSign[complete] -
FABL.pmfExpectation_biasedStandardizedSign_sq[complete]
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.1●12 declarations
Associated Lean declarations
-
FABL.biasComplement[complete]
-
FABL.biasMean[complete]
-
FABL.biasVarianceScale[complete]
-
FABL.biasSigma[complete]
-
FABL.biasMean_mem_Icc[complete]
-
FABL.biasSigma_sq[complete]
-
FABL.biasSigma_pos[complete]
-
FABL.biasedStandardizedSign[complete]
-
FABL.biasedStandardizedSign_one_eq_sqrt[complete]
-
FABL.biasedStandardizedSign_neg_one_eq_neg_sqrt[complete]
-
FABL.pmfExpectation_biasedStandardizedSign[complete]
-
FABL.pmfExpectation_biasedStandardizedSign_sq[complete]
-
FABL.biasComplement[complete] -
FABL.biasMean[complete] -
FABL.biasVarianceScale[complete] -
FABL.biasSigma[complete] -
FABL.biasMean_mem_Icc[complete] -
FABL.biasSigma_sq[complete] -
FABL.biasSigma_pos[complete] -
FABL.biasedStandardizedSign[complete] -
FABL.biasedStandardizedSign_one_eq_sqrt[complete] -
FABL.biasedStandardizedSign_neg_one_eq_neg_sqrt[complete] -
FABL.pmfExpectation_biasedStandardizedSign[complete] -
FABL.pmfExpectation_biasedStandardizedSign_sq[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
def FABL.biasComplement (p : ℝ) : ℝ
def FABL.biasComplement (p : ℝ) : ℝ
O'Donnell, Definition 8.39: `q = 1 - p`.
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
def FABL.biasMean (p : ℝ) : ℝ
def FABL.biasMean (p : ℝ) : ℝ
O'Donnell, Definition 8.39: the mean `μ = q - p = 1 - 2p`.
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
def FABL.biasVarianceScale (p : ℝ) : ℝ
def FABL.biasVarianceScale (p : ℝ) : ℝ
O'Donnell, Definition 8.39: the variance scale `σ² = 4p(1-p)`.
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
def FABL.biasSigma (p : ℝ) : ℝ
def FABL.biasSigma (p : ℝ) : ℝ
O'Donnell, Definition 8.39: `σ = √(4p(1-p))`.
-
theoremdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.biasedSignPMF[complete] -
FABL.biasedSignPMF_apply_toReal[complete] -
FABL.biasedSignPMF_hasFullSupport[complete] -
FABL.pmfExpectation_biasedSignPMF_signValue[complete] -
FABL.biasedSiteFourierFunction[complete] -
FABL.biasedSiteFourierFunction_orthonormal[complete] -
FABL.biasedSiteBasis[complete] -
FABL.biasedSiteFourierBasis[complete] -
FABL.subsetMultiIndex[complete] -
FABL.finsetEquivBinaryMultiIndex[complete] -
FABL.biasedMonomial[complete] -
FABL.biasedMonomial_apply[complete] -
FABL.biasedFourierCoeff[complete] -
FABL.biasedFourierCoeff_eq_expect[complete] -
FABL.biased_fourier_expansion[complete]
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.2●15 declarations
Associated Lean declarations
-
FABL.biasedSignPMF[complete]
-
FABL.biasedSignPMF_apply_toReal[complete]
-
FABL.biasedSignPMF_hasFullSupport[complete]
-
FABL.pmfExpectation_biasedSignPMF_signValue[complete]
-
FABL.biasedSiteFourierFunction[complete]
-
FABL.biasedSiteFourierFunction_orthonormal[complete]
-
FABL.biasedSiteBasis[complete]
-
FABL.biasedSiteFourierBasis[complete]
-
FABL.subsetMultiIndex[complete]
-
FABL.finsetEquivBinaryMultiIndex[complete]
-
FABL.biasedMonomial[complete]
-
FABL.biasedMonomial_apply[complete]
-
FABL.biasedFourierCoeff[complete]
-
FABL.biasedFourierCoeff_eq_expect[complete]
-
FABL.biased_fourier_expansion[complete]
-
FABL.biasedSignPMF[complete] -
FABL.biasedSignPMF_apply_toReal[complete] -
FABL.biasedSignPMF_hasFullSupport[complete] -
FABL.pmfExpectation_biasedSignPMF_signValue[complete] -
FABL.biasedSiteFourierFunction[complete] -
FABL.biasedSiteFourierFunction_orthonormal[complete] -
FABL.biasedSiteBasis[complete] -
FABL.biasedSiteFourierBasis[complete] -
FABL.subsetMultiIndex[complete] -
FABL.finsetEquivBinaryMultiIndex[complete] -
FABL.biasedMonomial[complete] -
FABL.biasedMonomial_apply[complete] -
FABL.biasedFourierCoeff[complete] -
FABL.biasedFourierCoeff_eq_expect[complete] -
FABL.biased_fourier_expansion[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.signValue_eq_biasMean_add_sigma_mul_biasedMonomial_singleton[complete] -
FABL.biasedFourierCoeff_dictator[complete] -
FABL.biasedFourierCoeff_dictator_empty[complete] -
FABL.biasedFourierCoeff_dictator_singleton[complete] -
FABL.biasedFourierCoeff_dictator_other[complete]
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.3●5 theorems
Associated Lean declarations
-
FABL.signValue_eq_biasMean_add_sigma_mul_biasedMonomial_singleton[complete]
-
FABL.biasedFourierCoeff_dictator[complete]
-
FABL.biasedFourierCoeff_dictator_empty[complete]
-
FABL.biasedFourierCoeff_dictator_singleton[complete]
-
FABL.biasedFourierCoeff_dictator_other[complete]
-
FABL.signValue_eq_biasMean_add_sigma_mul_biasedMonomial_singleton[complete] -
FABL.biasedFourierCoeff_dictator[complete] -
FABL.biasedFourierCoeff_dictator_empty[complete] -
FABL.biasedFourierCoeff_dictator_singleton[complete] -
FABL.biasedFourierCoeff_dictator_other[complete]
-
theoremdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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
-
FABL.selectionFunction[complete] -
FABL.selectionFunction_biased_expansion[complete]
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.4●2 declarations
Associated Lean declarations
-
FABL.selectionFunction[complete]
-
FABL.selectionFunction_biased_expansion[complete]
-
FABL.selectionFunction[complete] -
FABL.selectionFunction_biased_expansion[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.
-
FABL.biasedView[complete] -
FABL.biasedFourierCoeff_biasedView[complete]
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.5●2 declarations
Associated Lean declarations
-
FABL.biasedView[complete]
-
FABL.biasedFourierCoeff_biasedView[complete]
-
FABL.biasedView[complete] -
FABL.biasedFourierCoeff_biasedView[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.
-
FABL.biasedDiscreteDerivative[complete] -
FABL.biasedDiscreteDerivative_eq_sigma_mul[complete] -
FABL.biasSigma_mul_standardizedSign_difference_div_two[complete] -
FABL.biasedDiscreteDerivative_biasedMonomial[complete] -
FABL.biasedDiscreteDerivative_eq_fourier_sum[complete]
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.6●5 declarations
Associated Lean declarations
-
FABL.biasedDiscreteDerivative[complete]
-
FABL.biasedDiscreteDerivative_eq_sigma_mul[complete]
-
FABL.biasSigma_mul_standardizedSign_difference_div_two[complete]
-
FABL.biasedDiscreteDerivative_biasedMonomial[complete]
-
FABL.biasedDiscreteDerivative_eq_fourier_sum[complete]
-
FABL.biasedDiscreteDerivative[complete] -
FABL.biasedDiscreteDerivative_eq_sigma_mul[complete] -
FABL.biasSigma_mul_standardizedSign_difference_div_two[complete] -
FABL.biasedDiscreteDerivative_biasedMonomial[complete] -
FABL.biasedDiscreteDerivative_eq_fourier_sum[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.coordinateConditionalVariance_biasedSignPMF_toReal[complete] -
FABL.biasedFlipProbability[complete] -
FABL.productInfluence_biased_eq_sigma_sq_mul_flipProbability[complete] -
FABL.biasedSensitivity[complete] -
FABL.productTotalInfluence_biased_eq_sigma_sq_mul_expect_sensitivity[complete] -
FABL.biasedFourierCoeff_singleton_eq_sigma_mul_expect_discreteDerivative[complete] -
FABL.productInfluence_biased_eq_sigma_mul_singletonCoeff_of_monotone[complete]
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.7●7 declarations
Associated Lean declarations
-
FABL.coordinateConditionalVariance_biasedSignPMF_toReal[complete]
-
FABL.biasedFlipProbability[complete]
-
FABL.productInfluence_biased_eq_sigma_sq_mul_flipProbability[complete]
-
FABL.biasedSensitivity[complete]
-
FABL.productTotalInfluence_biased_eq_sigma_sq_mul_expect_sensitivity[complete]
-
FABL.biasedFourierCoeff_singleton_eq_sigma_mul_expect_discreteDerivative[complete]
-
FABL.productInfluence_biased_eq_sigma_mul_singletonCoeff_of_monotone[complete]
-
FABL.coordinateConditionalVariance_biasedSignPMF_toReal[complete] -
FABL.biasedFlipProbability[complete] -
FABL.productInfluence_biased_eq_sigma_sq_mul_flipProbability[complete] -
FABL.biasedSensitivity[complete] -
FABL.productTotalInfluence_biased_eq_sigma_sq_mul_expect_sensitivity[complete] -
FABL.biasedFourierCoeff_singleton_eq_sigma_mul_expect_discreteDerivative[complete] -
FABL.productInfluence_biased_eq_sigma_mul_singletonCoeff_of_monotone[complete]
-
theoremdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.GraphEdge[complete] -
FABL.EncodedGraph[complete] -
FABL.graphEdgePermEquiv[complete] -
FABL.permuteEncodedGraph[complete] -
FABL.IsGraphProperty[complete] -
FABL.EncodedGraphLE[complete] -
FABL.IsMonotoneGraphProperty[complete] -
FABL.biasedBoolPMF[complete] -
FABL.erdosRenyiPMF[complete] -
FABL.graphProperty_invariant[complete]
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.8●10 declarations
Associated Lean declarations
-
FABL.GraphEdge[complete]
-
FABL.EncodedGraph[complete]
-
FABL.graphEdgePermEquiv[complete]
-
FABL.permuteEncodedGraph[complete]
-
FABL.IsGraphProperty[complete]
-
FABL.EncodedGraphLE[complete]
-
FABL.IsMonotoneGraphProperty[complete]
-
FABL.biasedBoolPMF[complete]
-
FABL.erdosRenyiPMF[complete]
-
FABL.graphProperty_invariant[complete]
-
FABL.GraphEdge[complete] -
FABL.EncodedGraph[complete] -
FABL.graphEdgePermEquiv[complete] -
FABL.permuteEncodedGraph[complete] -
FABL.IsGraphProperty[complete] -
FABL.EncodedGraphLE[complete] -
FABL.IsMonotoneGraphProperty[complete] -
FABL.biasedBoolPMF[complete] -
FABL.erdosRenyiPMF[complete] -
FABL.graphProperty_invariant[complete]
-
abbrevdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.encodedGraphEdgeCount[complete] -
FABL.encodedGraphEdgeCount_permute[complete] -
FABL.edgeMajorityGraphProperty[complete] -
FABL.edgeMajority_isGraphProperty[complete] -
FABL.edgeParityGraphProperty[complete] -
FABL.edgeParity_isGraphProperty[complete] -
FABL.edgeMajority_isMonotoneGraphProperty[complete] -
FABL.EncodedGraphAdjacent[complete] -
FABL.encodedGraphAdjacent_permute_iff[complete] -
FABL.EncodedGraphConnected[complete] -
FABL.encodedGraphConnected_permute_iff[complete] -
FABL.EncodedGraphColorable[complete] -
FABL.encodedGraphColorable_permute_iff[complete] -
FABL.EncodedGraphContainsClique[complete] -
FABL.encodedGraphContainsClique_permute_iff[complete] -
FABL.connectivityGraphProperty[complete] -
FABL.connectivity_isGraphProperty[complete] -
FABL.connectivity_isMonotoneGraphProperty[complete] -
FABL.threeColorableGraphProperty[complete] -
FABL.threeColorable_isGraphProperty[complete] -
FABL.notThreeColorableGraphProperty[complete] -
FABL.notThreeColorable_isGraphProperty[complete] -
FABL.notThreeColorable_isMonotoneGraphProperty[complete] -
FABL.containsCliqueGraphProperty[complete] -
FABL.containsClique_isGraphProperty[complete] -
FABL.containsClique_isMonotoneGraphProperty[complete]
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.9●26 declarations
Associated Lean declarations
-
FABL.encodedGraphEdgeCount[complete]
-
FABL.encodedGraphEdgeCount_permute[complete]
-
FABL.edgeMajorityGraphProperty[complete]
-
FABL.edgeMajority_isGraphProperty[complete]
-
FABL.edgeParityGraphProperty[complete]
-
FABL.edgeParity_isGraphProperty[complete]
-
FABL.edgeMajority_isMonotoneGraphProperty[complete]
-
FABL.EncodedGraphAdjacent[complete]
-
FABL.encodedGraphAdjacent_permute_iff[complete]
-
FABL.EncodedGraphConnected[complete]
-
FABL.encodedGraphConnected_permute_iff[complete]
-
FABL.EncodedGraphColorable[complete]
-
FABL.encodedGraphColorable_permute_iff[complete]
-
FABL.EncodedGraphContainsClique[complete]
-
FABL.encodedGraphContainsClique_permute_iff[complete]
-
FABL.connectivityGraphProperty[complete]
-
FABL.connectivity_isGraphProperty[complete]
-
FABL.connectivity_isMonotoneGraphProperty[complete]
-
FABL.threeColorableGraphProperty[complete]
-
FABL.threeColorable_isGraphProperty[complete]
-
FABL.notThreeColorableGraphProperty[complete]
-
FABL.notThreeColorable_isGraphProperty[complete]
-
FABL.notThreeColorable_isMonotoneGraphProperty[complete]
-
FABL.containsCliqueGraphProperty[complete]
-
FABL.containsClique_isGraphProperty[complete]
-
FABL.containsClique_isMonotoneGraphProperty[complete]
-
FABL.encodedGraphEdgeCount[complete] -
FABL.encodedGraphEdgeCount_permute[complete] -
FABL.edgeMajorityGraphProperty[complete] -
FABL.edgeMajority_isGraphProperty[complete] -
FABL.edgeParityGraphProperty[complete] -
FABL.edgeParity_isGraphProperty[complete] -
FABL.edgeMajority_isMonotoneGraphProperty[complete] -
FABL.EncodedGraphAdjacent[complete] -
FABL.encodedGraphAdjacent_permute_iff[complete] -
FABL.EncodedGraphConnected[complete] -
FABL.encodedGraphConnected_permute_iff[complete] -
FABL.EncodedGraphColorable[complete] -
FABL.encodedGraphColorable_permute_iff[complete] -
FABL.EncodedGraphContainsClique[complete] -
FABL.encodedGraphContainsClique_permute_iff[complete] -
FABL.connectivityGraphProperty[complete] -
FABL.connectivity_isGraphProperty[complete] -
FABL.connectivity_isMonotoneGraphProperty[complete] -
FABL.threeColorableGraphProperty[complete] -
FABL.threeColorable_isGraphProperty[complete] -
FABL.notThreeColorableGraphProperty[complete] -
FABL.notThreeColorable_isGraphProperty[complete] -
FABL.notThreeColorable_isMonotoneGraphProperty[complete] -
FABL.containsCliqueGraphProperty[complete] -
FABL.containsClique_isGraphProperty[complete] -
FABL.containsClique_isMonotoneGraphProperty[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.biasedExpectationPolynomial[complete] -
FABL.biasedExpectationPolynomial_biasMean[complete] -
FABL.hasDerivAt_biasedExpectationPolynomial[complete] -
FABL.sum_productMean_biasedSignPMF_discreteDerivative[complete] -
FABL.hasDerivAt_biasedExpectationPolynomial_eq_singletons[complete] -
FABL.biasedMinusProbability[complete] -
FABL.biasedMinusProbabilityPolynomial[complete] -
FABL.hasDerivAt_biasedMinusProbabilityPolynomial[complete] -
FABL.hasDerivAt_biasedMinusProbabilityPolynomial_eq_totalInfluence[complete]
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.10●9 declarations
Associated Lean declarations
-
FABL.biasedExpectationPolynomial[complete]
-
FABL.biasedExpectationPolynomial_biasMean[complete]
-
FABL.hasDerivAt_biasedExpectationPolynomial[complete]
-
FABL.sum_productMean_biasedSignPMF_discreteDerivative[complete]
-
FABL.hasDerivAt_biasedExpectationPolynomial_eq_singletons[complete]
-
FABL.biasedMinusProbability[complete]
-
FABL.biasedMinusProbabilityPolynomial[complete]
-
FABL.hasDerivAt_biasedMinusProbabilityPolynomial[complete]
-
FABL.hasDerivAt_biasedMinusProbabilityPolynomial_eq_totalInfluence[complete]
-
FABL.biasedExpectationPolynomial[complete] -
FABL.biasedExpectationPolynomial_biasMean[complete] -
FABL.hasDerivAt_biasedExpectationPolynomial[complete] -
FABL.sum_productMean_biasedSignPMF_discreteDerivative[complete] -
FABL.hasDerivAt_biasedExpectationPolynomial_eq_singletons[complete] -
FABL.biasedMinusProbability[complete] -
FABL.biasedMinusProbabilityPolynomial[complete] -
FABL.hasDerivAt_biasedMinusProbabilityPolynomial[complete] -
FABL.hasDerivAt_biasedMinusProbabilityPolynomial_eq_totalInfluence[complete]
-
defdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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]/σ²`.
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.11●4 theorems
Associated Lean declarations
-
theoremdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.
-
FABL.condorcetConstant[complete] -
FABL.exists_condorcetMajorityThresholdBounds[complete]
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.12●2 declarations
Associated Lean declarations
-
FABL.condorcetConstant[complete]
-
FABL.exists_condorcetMajorityThresholdBounds[complete]
-
FABL.condorcetConstant[complete] -
FABL.exists_condorcetMajorityThresholdBounds[complete]
-
defdefined in FABL/Chapter08/BiasedThresholdPhenomena.leancomplete
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.leancomplete
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.
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.
-
FABL.existsUnique_criticalProbability[complete] -
FABL.criticalProbability[complete] -
FABL.criticalProbability_mem_Ioo[complete] -
FABL.biasedMinusProbability_criticalProbability[complete] -
FABL.criticalComplement[complete] -
FABL.criticalMean[complete] -
FABL.criticalSigma[complete] -
FABL.criticalProbability_majority_odd[complete]
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.14●8 declarations
Associated Lean declarations
-
FABL.existsUnique_criticalProbability[complete]
-
FABL.criticalProbability[complete]
-
FABL.criticalProbability_mem_Ioo[complete]
-
FABL.biasedMinusProbability_criticalProbability[complete]
-
FABL.criticalComplement[complete]
-
FABL.criticalMean[complete]
-
FABL.criticalSigma[complete]
-
FABL.criticalProbability_majority_odd[complete]
-
FABL.existsUnique_criticalProbability[complete] -
FABL.criticalProbability[complete] -
FABL.criticalProbability_mem_Ioo[complete] -
FABL.biasedMinusProbability_criticalProbability[complete] -
FABL.criticalComplement[complete] -
FABL.criticalMean[complete] -
FABL.criticalSigma[complete] -
FABL.criticalProbability_majority_odd[complete]
-
theoremdefined in FABL/Chapter08/BiasedAnalysis.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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.leancomplete
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`.
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.