TCSLib

232 Boolean Analysis — Indicator Smoothing

232.1 Overview

Conditional Gaussian averaging of indicators preserves their means and approximates them in integral absolute difference. Coupling the averaging noises also shows that averaging contracts rotation variation.

232.2 Declarations

Definition 232.1 Gaussian conditional indicator average
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). The averaged indicator is the function \(u_\theta :\mathbb R^n\to \mathbb R\); for a nonintegrable integrand the integral is assigned zero.

Lemma 232.2 Averaged indicator as conditional probability
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). If \(A\) is measurable, then \(u_\theta (x)=\gamma _n\{ y:\cos \theta \, x+\sin \theta \, y\in A\} \) for every real \(\theta \) and every \(x\).

Lemma 232.3 Measurable membership disagreement
✓

Let \(\Omega ,\Xi \) be measurable spaces, \(A\subseteq \Xi \) a measurable set, and \(f,g:\Omega \to \Xi \) measurable maps. Then \(\{ z:\neg (f(z)\in A\ \Longleftrightarrow \ g(z)\in A)\} \) is measurable.

Lemma 232.4 Exact indicator approximation discrepancy
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). For independent \(X,Y\sim \gamma _n\), put \(R_A(\theta )=\Pr (1_A(X)\ne 1_A(\cos \theta \, X+\sin \theta \, Y))\). If \(A\) is measurable, then \(\int |u_\theta (x)-1_A(x)|\, d\gamma _n(x)=R_A(\theta )\) for every real \(\theta \).

Lemma 232.5 Range of averaged Gaussian indicators
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). If \(A\) is measurable, then \(0\le u_\theta (x)\le 1\) for every real \(\theta \) and every \(x\).

Lemma 232.6 Integral approximation of Gaussian indicators
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). If \(A\) is measurable, then \(\int |u_\theta -1_A|\, d\gamma _n\to 0\) as \(\theta \to 0\) through real values.

Lemma 232.7 Measurability of averaged indicators
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). For measurable \(A\) and every real \(\theta \), the function \(u_\theta \) is measurable.

Lemma 232.8 Integrability of averaged indicators
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). For measurable \(A\) and every real \(\theta \), the function \(u_\theta \) is \(\gamma _n\)-integrable.

Lemma 232.9 Gaussian mean preservation
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). For measurable \(A\) and every real \(\theta \), \(\int u_\theta \, d\gamma _n=\gamma _n(A)\).

Lemma 232.10 Exchange of middle product coordinates
✓

Let \(E\) be a measurable space and \(\mu \) an s-finite measure on \(E\). The map \(((a,b),(c,d))\mapsto ((a,c),(b,d))\) preserves the measure \((\mu \otimes \mu )\otimes (\mu \otimes \mu )\).

Lemma 232.11 Independent paired Gaussian mixtures
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For any real \(u\), if \(X_1,X_2,Y_1,Y_2\) are independent with law \(\gamma _n\), then \((\cos u\, X_1+\sin u\, Y_1,\cos u\, X_2+\sin u\, Y_2)\) has law \(\gamma _n\otimes \gamma _n\).

Lemma 232.12 Difference of finite set measures
✓

Let \(\mu \) be a finite measure on a measurable space \(E\), and let \(C,D\subseteq E\) be arbitrary sets. Then \(|\mu (C)-\mu (D)|\le \mu (C\mathbin {\triangle } D)\), where all values are viewed as finite real numbers.

Lemma 232.13 Coupled bound for two averaged values
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). Let \(A\) be measurable, \(u,v\in \mathbb R\), and \(x,x\prime \in \mathbb R^n\). For independent \(Y,Y\prime \sim \gamma _n\), \(|u_u(x)-u_u(\cos v\, x+\sin v\, x\prime )|\le \Pr (1_A(\cos u\, x+\sin u\, Y)\ne 1_A(\cos u(\cos v\, x+\sin v\, x\prime )+\sin u(\cos v\, Y+\sin v\, Y\prime )))\).

Lemma 232.14 Averaging contracts rotation variation
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). For \(A\subseteq \mathbb R^n\) and \(\theta \in \mathbb R\), put \(u_\theta (x)=\int 1_A(\cos \theta \, x+\sin \theta \, y)\, d\gamma _n(y)\). For independent \(X,Y\sim \gamma _n\), put \(R_A(\theta )=\Pr (1_A(X)\ne 1_A(\cos \theta \, X+\sin \theta \, Y))\). If \(A\) is measurable, then for every \(u,v\in \mathbb R\), \(\mathbb E_{X,Y}|u_u(X)-u_u(\cos v\, X+\sin v\, Y)|\le R_A(v)\).