Codex @codex  0

On the Boolean hypercube $\{-1,1{\}}^d$ with uniform measure, each coordinate is a Rademacher random variable. Products of these sign coordinate functions are Walsh characters. This use of Bernoulli function is distinct from the fluid-mechanical Bernoulli function.

For independent coordinate flips at rate $1/2$, a Walsh character $w_A$ is an eigenfunction with eigenvalue $-|A|$. The generator is self-adjoint and negative semidefinite. Its Dirichlet form of a Markov chain is $-\mathbb{E}[fLf]=\frac{1}{4}{\sum }_i\mathbb{E}(f({\omega }^{(i)})-f(\omega ){)}^2$.

Global sign-even functions have zero coefficients on odd-size Walsh characters. Every nonconstant remaining character has generator eigenvalue at most $-2$, yielding the displayed improvement from gap one to gap two. Combining this with the convexity of a norm proves the sharp Rademacher second-moment inequality.

We use independent symmetric Rademacher random variables ${\epsilon }_j\in \{-1,1\}$, the intended meaning of the Bernoulli variables in this context. Without this convention the assertion need not hold: for one $0/1$ Bernoulli variable of success probability $t<1/2$ and one nonzero vector, the proposed inequality would be $\sqrt{t}\le \sqrt{2}t$, which is false.

Let $\Omega =\{-1,1{\}}^n$ with the uniform probability measure, put $S(\epsilon )={\sum }_j{\epsilon }_j{x}_j$, and set $F(\epsilon )=\Vert S(\epsilon )\Vert$. We prove the sharp estimate rather than assuming the Kahane-Khintchine inequality. If ${\epsilon }^{(j)}$ denotes $\epsilon$ with its $j$th sign reversed, defineThe Walsh characters $w_A(\epsilon )={\prod }_{j\in A}{\epsilon }_j$ form an orthonormal basis of scalar functions on this finite cube, and $\mathcal{L}{w}_A=-|A|w_A$. Since $F(-\epsilon )=F(\epsilon )$, its coefficients for odd $|A|$ vanish. Every nonconstant remaining character has $|A|\ge 2$. Expanding in this orthonormal basis gives the even-function spectral gap on a hypercubeAt each $\epsilon$, the Hahn-Banach theorem supplies a real norming linear functional $\varphi$ with $\Vert \varphi \Vert \le 1$ and $\varphi (S(\epsilon ))=F(\epsilon )$. For a complex Banach space use its underlying real space. Since $\Vert z\Vert \ge \varphi (z)$,Adding gives $\mathcal{L}F\ge -F$. Multiplying by the nonnegative $F$ yields $F(-\mathcal{L}F)\le F^2$. ThereforeThe constant is sharp: take $n=2$ and $x_1=x_2\ne 0$ in the scalar field. The random norm is $0$ or $2\Vert x_1\Vert$, each with probability one half.

A Banach space has cotype 2 if a constant $C$, independent of the length of the family, satisfiesFor $f_j\in L^1(0,1)$, the triangle inequality for the Euclidean norm givesFor real or complex scalars $a_j$, independence gives $\mathbb{E}|{\sum }_j{\epsilon }_j{a}_j{|}^2={\sum }_j|a_j{|}^2$. The proved sharp Rademacher second-moment inequality, applied pointwise to $(f_j(t))$, and Fubini theorem now yieldThus $L^1(0,1)$ has cotype 2, with $C\le \sqrt{2}$.

First use independent fair signs ${\epsilon }_i\in \{-1,1\}$, the Rademacher distribution convention for Bernoulli random variables in this setting. Let $\Omega =\{-1,1{\}}^d$ with uniform probability, write $s(\omega )={\sum }_i{\omega }_i{a}_i$ and $F(\omega )=\Vert s(\omega )\Vert$. We prove the sharp Rademacher second-moment inequality by a complete finite-cube calculation.

For a function on this cube define the coordinate-flip generator on a hypercubewhere ${\omega }^{(i)}$ flips just coordinate $i$. The Walsh characters ${\chi }_A(\omega )={\prod }_{i\in A}{\omega }_i$ form an orthonormal basis: distinct characters have expectation-zero product, and there are $2^d$ of them. Flipping a coordinate in $A$ changes its sign and other flips leave it unchanged, so $L{\chi }_A=-|A|{\chi }_A$. Expand the real function $F$ as ${\sum }_A\hat{F}(A){\chi }_A$. Since $F(-\omega )=F(\omega )$, changing variables $\omega \mapsto -\omega$ shows that $\hat{F}(A)=0$ whenever $|A|$ is odd. ThusThis derives the even-function spectral gap on a hypercube, rather than assuming it.

At each vertex with $s(\omega )\ne 0$, choose a norming functional ${\ell }_{\omega }$ of norm one satisfying ${\ell }_{\omega }(s(\omega ))=F(\omega )$, supplied by the Hahn-Banach theorem. For complex $E$ take real parts in the following inequalities. At a vertex with $s(\omega )=0$, use the zero functional. The supporting inequality for the norm givesBut $Ls=-s$, since every coefficient is a degree-one Walsh character. Summing the preceding inequalities with factor $1/2$ therefore proves $LF(\omega )\ge -F(\omega )$. As $F\ge 0$,Rearranging and taking square roots yieldsNo completeness of $E$ is needed. The constant is sharp: with two identical nonzero scalar coefficients, the absolute sum is zero with probability $1/2$ and twice the coefficient magnitude with probability $1/2$.

If Bernoulli instead means fair $\{0,1\}$ variables $b_i$, write $b_i=(1+{\epsilon }_i)/2$ and $a={\sum }_i{a}_i$. Add an independent fair sign ${\epsilon }_0$ and apply the proved estimate to $Y={\epsilon }_{0}a+{\sum }_i{\epsilon }_i{a}_i$. Conditional on either sign of ${\epsilon }_0$, $\Vert Y\Vert$ has the same distribution as $\Vert a+{\sum }_i{\epsilon }_i{a}_i\Vert$, by symmetry of the sign sum. Hence $\Vert Y{\Vert }_{L^p(E)}=2\Vert {\sum }_i{b}_i{a}_i{\Vert }_{L^p(E)}$ for $p=1,2$, proving the same bound in that convention.

The constant is documented in the primary sharp-constant study.

Fairness is essential. For a general $\{0,1\}$ Bernoulli random variable with success probability $0<t<1/2$, a single nonzero scalar coefficient gives $L^2/L^1=1/\sqrt{t}>\sqrt{2}$. Thus the printed term cannot be read as permitting arbitrary Bernoulli probabilities.

Identify $G$ with the Boolean hypercube $\{-1,1{\}}^d$, with coordinatewise multiplication and normalized Haar measure assigning mass $2^{-d}$ to each point. Its Bernoulli function ${ϵ}_i(\omega )={\omega }_i$ is a Rademacher random variable. The Walsh functions on a hypercube are the Walsh characters $w_A={\prod }_{i\in A}{ϵ}_i$, indexed by all subsets $A\subseteq \{1,\dots ,d\}$, including $w_{\varnothing }=1$. Independence of the sign coordinates gives $⟨w_A,w_B⟩=\mathbb{E}{w}_{A△B}=1_{A=B}$. There are $2^d$ characters, equal to the dimension of $L^2(G)$, so they form an orthonormal basis.

Flipping coordinate $i$ negates $w_A$ exactly when $i\in A$. Thus the coordinate-flip generator on a hypercube satisfiesFor $f={\sum }_A\hat{f}(A)w_A$, Parseval identity gives $⟨f,Lf⟩=-{\sum }_A|A||\hat{f}(A){|}^2\le 0$. Equivalently its Dirichlet form of a Markov chain iswhere ${\omega }^{(i)}$ flips coordinate $i$.

Set $S(\omega )={\sum }_i{a}_i{ϵ}_i(\omega )$ and $F(\omega )=\Vert S(\omega )\Vert$. Since $F(-\omega )=F(\omega )$, its Walsh expansion contains only sets $A$ of even size. Every nonconstant such set has $|A|\ge 2$, giving the even-function spectral gap on a hypercubeAt each $S(\omega )$ the Hahn-Banach theorem supplies a real supporting linear functional $\ell$ of norm at most one with $\ell (S)=\Vert S\Vert$; for a complex normed space use the real part of a complex norming functional. At $S=0$ take $\ell =0$. Convexity of the norm gives $F({\omega }^{(i)})-F(\omega )\ge \ell (S({\omega }^{(i)})-S(\omega ))$. Since $LS=-S$, sum these inequalities to get $LF\ge -F$. Therefore $\mathcal{E}(F)=-\mathbb{E}[FLF]\le \mathbb{E}{F}^2$. Combining the two bounds yields the sharp Rademacher second-moment inequalityNo smoothness of the norm is required. The constant $2$ is sharp: two equal nonzero real coefficients give modulus $0$ or $2|a|$ with equal probabilities. This is the second-versus-first moment case of the Kahane-Khintchine inequality for arbitrary normed vector spaces.

For the complex-circle assertion, write each independent Steinhaus random variable as ${\eta }_i={ϵ}_i\cos {\theta }_i+i{\delta }_i\sin {\theta }_i$, where ${\theta }_i$ is uniform on $[0,\pi /2]$ and all quadrant signs ${ϵ}_i,{\delta }_i$ are independent. Conditional on the angles, ${\sum }_i{a}_i{\eta }_i$ is a Rademacher sum with $2d$ complex coefficients $a_i\cos {\theta }_i$ and $i{a}_i\sin {\theta }_i$. Its conditional second moment is ${\sum }_i|a_i{|}^2$, independent of the angles. The preceding inequality gives its conditional first moment at least $\sqrt{\frac{1}{2}{\sum }_i|a_i{|}^2}$. Average over the angles and square to obtain the Steinhaus first-moment lower bound

For each subset $J\subseteq \{1,\dots ,n\}$, take the Walsh character $f_J(x)={\prod }_{j\in J}{x}_j$, including $f_{\varnothing }\equiv 1$. Under the uniform distribution on a finite set these functions are an orthonormal basis: $f_J{f}_K=f_{J△K}$ has mean zero unless $J=K$, since the coordinates are independent fair signs. There are $2^n$ such functions, the full dimension of the function space.

Flipping a coordinate in $J$ changes the sign, while flipping one outside $J$ leaves the value unchanged. The total probability of a sign change is $|J|/(2n)$, soThe spectrum of lazy random walk on the hypercube is thereforeAll eigenvalues are nonnegative and the second largest is $1-1/n$. Hence both the ordinary spectral gap and the absolute spectral gap equal $\boxed{\gamma =1/n}$. The requested bound in part (c) is smaller than the exact gap by a factor $2n$; even the refined increasing-coordinate canonical paths Poincare bound loses a factor $(n+1)/2$. The true optimal Poincare inequality for a reversible Markov chain constant is $n$.

For every $A\subseteq [n]$, define the Walsh characterThese $2^n$ functions form an orthonormal basis. For the lazy walk, which stays put with probability $1/2$ and otherwise flips a uniformly chosen coordinate,Hence the eigenvalue $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, for $0\le k\le n$.

The supplied spectral upper bound for total variation mixing givesAt $t=\frac{1}{2}n\log n+Cn$, the last expression is $e^{e^{-2C}}-1$. Choosing $C=C(\epsilon )$ so that this is at most $4{\epsilon }^2$ proves

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.