TCSLib

230 Boolean Analysis — Halfspace

230.1 Overview

Unit linear projections preserve standard Gaussian laws. Conditioning scalar rotation crossings gives an infinitesimal crossing formula and hence the normalized rotation-sensitivity limit for halfspaces.

230.2 Declarations

Lemma 230.1 Unit Gaussian projection law
✓

For every \(a\in \mathbb R^n\) with \(\sum _i a_i^2=1\), the map \(z\mapsto \sum _i a_i z_i\) pushes standard Gaussian measure on \(\mathbb R^n\) to \(N(0,1)\).

Lemma 230.2 Derivative of the rotated threshold probability
✓

Let \(\Phi ,\varphi \) denote the standard Gaussian distribution function and density. For \(t,y\in \mathbb R\), define \(q_{t,y}(\theta )=\Phi ((t-\sin \theta \, y)/\cos \theta )-\Phi (t)\). For every \(t,y\), \(q_{t,y}'(0)=-\varphi (t)y\).

Lemma 230.3 Limit of the conditional crossing quotient
✓

Let \(\Phi ,\varphi \) denote the standard Gaussian distribution function and density. For \(t,y\in \mathbb R\), define \(q_{t,y}(\theta )=\Phi ((t-\sin \theta \, y)/\cos \theta )-\Phi (t)\). For every \(t,y\), \(|q_{t,y}(\theta )|/\theta \to \varphi (t)|y|\) as \(\theta \to 0^+\).

Lemma 230.4 Maximum Gaussian density
✓

The standard Gaussian density satisfies \(\varphi (x)\le \varphi (0)\) for every \(x\in \mathbb R\).

Lemma 230.5 Lipschitz Gaussian distribution function
✓

The standard Gaussian distribution function and density satisfy \(|\Phi (x)-\Phi (y)|\le \varphi (0)|x-y|\) for all \(x,y\in \mathbb R\).

Lemma 230.6 Dominating conditional crossing quotients
✓

Let \(\Phi ,\varphi \) denote the standard Gaussian distribution function and density. For \(t,y\in \mathbb R\), define \(q_{t,y}(\theta )=\Phi ((t-\sin \theta \, y)/\cos \theta )-\Phi (t)\). For all \(t,y\in \mathbb R\) and \(0\lt \theta \lt 1\), \(|q_{t,y}(\theta )|/\theta \le 2\varphi (0)(|t|+|y|)\).

Lemma 230.7 Integrated conditional crossing limit
✓

Let \(\Phi ,\varphi \) denote the standard Gaussian distribution function and density. For \(t,y\in \mathbb R\), define \(q_{t,y}(\theta )=\Phi ((t-\sin \theta \, y)/\cos \theta )-\Phi (t)\). For every real \(t\), if \(Y\sim N(0,1)\), then \(\mathbb E_Y(|q_{t,Y}(\theta )|/\theta )\to \varphi (t)\mathbb E|Y|\) as \(\theta \to 0^+\).

Lemma 230.8 Symmetric difference of Gaussian halflines
✓

Let \(\gamma \) be standard Gaussian measure on \(\mathbb R\) and \(\Phi \) its distribution function. For real \(a,b\), \(\gamma (({-\infty },a]\mathbin {\triangle }({-\infty },b])=|\Phi (b)-\Phi (a)|\).

Lemma 230.9 First absolute Gaussian moment
✓

For a random variable \(Y\sim N(0,1)\) and the standard Gaussian density \(\varphi \), \(\mathbb E|Y|=2\varphi (0)\).

Lemma 230.10 Measurability of scalar rotation disagreement
✓

For every real \(t,\theta \), the set \(\{ (x,y)\in \mathbb R^2:\neg (x\le t\ \Longleftrightarrow \ \cos \theta \, x+\sin \theta \, y\le t)\} \) is Borel measurable.

Lemma 230.11 Conditional formula for scalar disagreement
✓

Let \(\Phi ,\varphi \) denote the standard Gaussian distribution function and density. For \(t,y\in \mathbb R\), define \(q_{t,y}(\theta )=\Phi ((t-\sin \theta \, y)/\cos \theta )-\Phi (t)\). If \(\cos \theta \gt 0\) and \(X,Y\) are independent standard Gaussian variables, then \(\Pr (1_{(-\infty ,t]}(X)\ne 1_{(-\infty ,t]}(\cos \theta \, X+\sin \theta \, Y))=\mathbb E_Y|q_{t,Y}(\theta )|\).

Lemma 230.12 Normalization by the absolute Gaussian moment
✓

The standard Gaussian density satisfies \(\sqrt{\pi /2}\, 2\varphi (0)=1\).

Lemma 230.13 Normalized scalar crossing limit
✓

Let \(X,Y\) be independent standard Gaussian variables and \(\varphi \) their density. For every real \(t\), \(\sqrt{\pi /2}\, \Pr (1_{(-\infty ,t]}(X)\ne 1_{(-\infty ,t]}(\cos \theta \, X+\sin \theta \, Y))/\theta \to \varphi (t)\) as \(\theta \to 0^+\).

Lemma 230.14 Scalar reduction of halfspace sensitivity
✓

For a measurable \(A\subseteq \mathbb R^n\) and independent standard Gaussian vectors \(X,Y\), put \(R_A(\theta )=\Pr (1_A(X)\ne 1_A(\cos \theta \, X+\sin \theta \, Y))\). If \(a\in \mathbb R^n\) satisfies \(\sum _i a_i^2=1\) and \(H=\{ z:\sum _i a_i z_i\le t\} \), then \(R_H(\theta )=\Pr (1_{(-\infty ,t]}(U)\ne 1_{(-\infty ,t]}(\cos \theta \, U+\sin \theta \, V))\) for every real \(t,\theta \), where \(U,V\) are independent standard Gaussian scalars.

Lemma 230.15 Infinitesimal halfspace rotation sensitivity
✓

For a measurable \(A\subseteq \mathbb R^n\) and independent standard Gaussian vectors \(X,Y\), put \(R_A(\theta )=\Pr (1_A(X)\ne 1_A(\cos \theta \, X+\sin \theta \, Y))\). If \(a\in \mathbb R^n\) satisfies \(\sum _i a_i^2=1\) and \(H=\{ z:\sum _i a_i z_i\le t\} \) for \(t\in \mathbb R\), then \(\sqrt{\pi /2}\, R_H(\theta )/\theta \to \varphi (t)\) as \(\theta \to 0^+\), where \(\varphi \) is the standard Gaussian density.

Lemma 230.16 Absolute moment of a Gaussian linear form
✓

For every \(n\ge 0\) and \(a\in \mathbb R^n\), if \(Z\) is a standard Gaussian vector and \(\varphi \) is the one-dimensional standard Gaussian density, then \(\mathbb E|\sum _i a_i Z_i|=\sqrt{\sum _i a_i^2}\, 2\varphi (0)\).