TCSLib

239 Boolean Analysis — Invariance — Sequence

239.1 Overview

A sequence of hybrid input families gives the summed replacement bound. Equality of independent coordinate laws also determines the joint vector law.

239.2 Declarations

Definition 239.1 Selection from two coordinate copies
✓

For integers \(n,r\ge 0\) and an index \(i\in \{ 0,\ldots ,n-1\} \), the hybrid selection chooses the right copy of \(i\) if \(i\lt r\) and the left copy otherwise, as an element of two disjoint copies of the coordinate set.

Definition 239.2 Hybrid family after initial replacements
✓

Let \(Z_{L,i},Z_{R,i}\colon \Omega \to \mathbb R\) be two indexed families, \(0\le i\lt n\), and let \(r\ge 0\) be an integer. The hybrid family \(H^{(r)}\) has \(H^{(r)}_i=Z_{R,i}\) for \(i\lt r\) and \(H^{(r)}_i=Z_{L,i}\) for \(i\ge r\).

Lemma 239.3 Distinct coordinates remain distinct in hybrids
✓

For integers \(n,r\ge 0\), the map sending \(i\in \{ 0,\ldots ,n-1\} \) to its right copy when \(i\lt r\) and its left copy otherwise is injective.

Lemma 239.4 Initial hybrid equals the left family
✓

Let \(Z_{L,i},Z_{R,i}\colon \Omega \to \mathbb R\) be two families indexed by \(0\le i\lt n\), and define \(H^{(r)}_i=Z_{R,i}\) if \(i\lt r\) and \(Z_{L,i}\) otherwise. Then \(H^{(0)}_i=Z_{L,i}\) for every \(i\).

Lemma 239.5 Final hybrid equals the right family
✓

Let \(Z_{L,i},Z_{R,i}\colon \Omega \to \mathbb R\) be two families indexed by \(0\le i\lt n\), and define \(H^{(r)}_i=Z_{R,i}\) if \(i\lt r\) and \(Z_{L,i}\) otherwise. Then \(H^{(n)}_i=Z_{R,i}\) for every \(i\), including the empty family when \(n=0\).

Lemma 239.6 Consecutive hybrids agree away from the replaced input
✓

Let \(Z_{L,j},Z_{R,j}\colon \Omega \to \mathbb R\) be two families indexed by \(0\le j\lt n\), and put \(H^{(r)}_j=Z_{R,j}\) if \(j\lt r\) and \(Z_{L,j}\) otherwise. If \(i,j\in \{ 0,\ldots ,n-1\} \) and \(j\ne i\), then \(H^{(i)}_j=H^{(i+1)}_j\) as functions on \(\Omega \).

Theorem 239.7 Invariance for two mutually independent input copies
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{i\in S}x_i\) be a real multilinear polynomial of degree at most \(k\); let \(I_i(F)=\sum _{S\ni i}a_S^2\). Let \((Z_{L,i},Z_{R,i})_{i=1}^n\) be a mutually independent family of \(2n\) real inputs on a probability space, each measurable up to a null set with finite fourth absolute moment, first three moments \(0,1,0\), and fourth moment at most \(9\). If \(\psi \in C^4(\mathbb R)\) and \(C\ge 0\) bounds \(|\psi ^{(4)}|\) everywhere, then \(|\mathbb E\psi (F(Z_L))-\mathbb E\psi (F(Z_R))|\le (C/12)9^k\sum _i I_i(F)^2\).

Theorem 239.8 Joint laws from independent coordinate laws
✓

Let \(I\) be a finite index set and let \((X_i)_{i\in I}\) and \((Y_i)_{i\in I}\) be real input families on probability spaces \((\Omega ,\mu )\) and \((\Xi ,\nu )\), respectively. If each family is independent and \(X_i\) and \(Y_i\) are measurable up to null sets with the same distribution for every \(i\), then the random vectors \((X_i)_{i\in I}\) and \((Y_i)_{i\in I}\) have the same distribution.