The Efron-Stein inequality for identically distributed pairs

Jnaneshwar Baslingker, Bálint Virág · 2026

Read The Efron-Stein inequality for identically distributed pairs by Jnaneshwar Baslingker, Bálint Virág (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05388.txt.

Introduction

A short probability paper by Jnaneshwar Baslingker and Bálint Virág settles when the Efron-Stein inequality still holds. That inequality bounds how much a random quantity can vary, and it is a standard tool in probability theory. The question here concerns pairs of random variables drawn in two different ways.

The authors prove the inequality survives for independent exchangeable pairs. For independent pairs that are merely identically distributed, it fails, and a simple trigonometric example shows the weaker bound cannot be improved. When each variable takes only a few values, they still give a useful bound with an explicit constant.

Catalog record

CREATORJnaneshwar Baslingker, Bálint Virág
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.05388

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Efron-Stein inequality for identically distributed pairs Jnaneshwar Baslingker, Bálint Virág Abstract We prove that the classical Efron–Stein inequality holds for independent exchangeable pairs ( X i , Y i ) (X_{i},Y_{i}) . The same inequality fails for independent identically distributed pairs; a simple trigonometric counterexample shows that the trivial Cauchy–Schwarz bound of factor n n is sharp. When each random variable takes at most k i k_{i} values, a useful bound still holds with explicit constant ρ ⁡ ( k ) ≤ max i ⁡ k i / 2 \rho(k)\leq\max_{i}k_{i}/2 . 1 Introduction The classical Efron–Stein inequality Efron and Stein 1981 , Steele 1986 bounds the variance of a function of independent random variables by a sum of squared differences obtained by replacing one variable at a time with an independent copy. It has become a fundamental tool in concentration of measure, influence theory, and the analysis of algorithms. In this note we study a natural variant: instead of independent copies we are given, for each coordinate i , an exchangeable pair (X_{i},Y_{i}) (i.e., (X_{i},Y_{i})\stackrel{{\scriptstyle d}}{{=}}(Y_{i},X_{i}) ) and the pairs are independent across i . We show that the Efron–Stein inequality continues to hold in this setting (Theorem 2 ). The proof reduces the general exchangeable case to the classical Rademacher case by conditioning on the exchangeable \sigma -fields and a simple truncation argument. When the pairs are merely identically distributed (but not exchangeable), the inequality can fail dramatically. We give a sharp counterexample (Proposition 3 ) showing that the ratio of the two sides can be as large as the trivial Cauchy–Schwarz bound n . On the positive side, when each variable takes values in a finite set of size at most k_{i} , we obtain a useful bound whose constant \rho(k) depends only on the maximal cycle length appearing in the joint laws (Theorem 5 ). The proof combines Fourier analysis on cyclic groups with a Krein–Milman decomposition of circulations into cycle flows. As an illustration we recover a sign-flipping analogue of the Gaussian Poincaré inequality. We also show that, without the identical-distribution assumption, even three-point supports do not improve upon the factor- n bound. The exchangeable-pair technique and related concentration inequalities have been developed extensively by Chatterjee Chatterjee 2007 and are presented in detail in the monograph of Boucheron, Lugosi and Massart Boucheron et al. 2013 . The specific strengthening for exchangeable pairs and the finite-support analysis with cycle decomposition presented here appear to be new. A standard version of the Efron-Stein inequality can be stated as follows. Theorem 1 ( Efron and Stein 1981 , Steele 1986 ) . Let X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n} be 2n independent random variables with X_{i}\stackrel{{\scriptstyle d}}{{=}}Y_{i} for all i . Let f be a measurable function, and let Z_{i}=f(X_{1}\ldots X_{i},Y_{i+1},\ldots Y_{n}) for i=0,\dots,n . Then E(Z_{n}-Z_{0})^{2}\leq\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2}. Our goal is to prove the following strengthening: Theorem 2 . For each i , let (X_{i},Y_{i}) be an exchangeable pair, so that the pairs (X_{i},Y_{i}) are independent as i varies. Let f be a measurable function, and let Z_{i}=f(X_{1},\ldots X_{i},Y_{i+1},\ldots Y_{n}) . Then E(Z_{n}-Z_{0})^{2}\leq\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2}. The proof is based on Steele 1986 with some significant modifications. Proof. First we consider the special case when all X_{i} are uniform on \{-1,1\} and Y_{i}=-X_{i} . Since \{1,X_{i}\} is an orthonormal basis for the law of X_{i} , \{\chi_{s}=\prod_{i\in s}X_{i}\,:\,s\subset[n]\} forms an orthonormal basis for the joint law of the X_{i} . So we can write f(X_{1},\ldots,X_{n})=\sum_{s\subset[n]}c_{s}\chi_{s} for some coefficients c_{s} . We also have f(Y_{1},\ldots,Y_{n})=\sum_{s\subset[n]}(-1)^{|s|}c_{s}\chi_{s}, and the difference is given by Z_{n}-Z_{0}=2\sum_{s\subset[n],|s|\text{ odd}}c_{s}\chi_{s}. Similarly, we have Z_{i}-Z_{i-1}\stackrel{{\scriptstyle d}}{{=}}f(X_{1},\ldots,X_{n})-f(X_{1},\ldots,X_{i-1},Y_{i},X_{i+1},\ldots X_{n})=2\sum_{s\subset[n],i\in s}c_{s}\chi_{s}. Squaring, taking expectations and using orthonormality, the desired inequality reads 2\sum_{s\subset[n],|s|\text{ odd}}c_{s}^{2}\leq 2\sum_{s\subset[n]}c_{s}^{2}|s| which follows by summing 2c_{s}^{2} times the inequality \mathbf{1}_{|s|\text{ odd}}\leq|s| over s\subset[n] . For general exchangeable pairs (X_{i},Y_{i}) , and f bounded, given the exchangeable \sigma -field \mathcal{I}_{i} we know the set \{X_{i},Y_{i}\} but not the order. So we can represent the conditional law of (X_{i},Y_{i}) as X_{i}=A_{i}+B_{i}X_{i}^{\prime} , Y_{i}=A_{i}+B_{i}Y_{i}^{\prime} , where A_{i}=(X_{i}+Y_{i})/2 , B_{i}=|X_{i}-Y_{i}|/2 are \mathcal{I}_{i} -measurable, and X_{i}^{\prime}=-Y_{i}^{\prime} are uniform on \{-1,1\} independent of \mathcal{I}_{i} . Conditioning on the \sigma -field \mathcal{I} generated by all the \mathcal{I}_{i} , and setting f^{\prime}(x_{1},\ldots,x_{n})=f(A_{1}+B_{1}x_{1},\ldots,A_{n}+B_{n}x_{n}) , and applying the first part to the primed quantities, we get E[(Z_{n}-Z_{0})^{2}|\mathcal{I}]\leq\sum_{i=1}^{n}E[(Z_{i}-Z_{i-1})^{2}|\mathcal{I}]. Taking expectations completes the proof. To handle the unbounded case, note that it holds for f_{b}=(-b\vee f)\wedge b . Since x\mapsto(-b\vee x)\wedge b is a contraction with respect to Euclidean distance on \mathbb{R} , both sides of the inequality are monotone increasing in b . The monotone convergence theorem then implies the general case. ∎ Let (Z_{1},Z_{2},...,Z_{n}) be i.i.d N(0,1) random variables and (B_{1},B_{2},...,B_{n}) are i.i.d (independent of Z_{i} ) with \mathbb{P}(B_{1}=1)=p and \mathbb{P}(B_{1}=-1)=1-p . Taking Y_{i}=B_{i}Z_{i} and applying Theorem 2 gives, E[(Z_{n}-Z_{0})^{2}]\leq\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2} where \displaystyle E(Z_{n}-Z_{n-1})^{2} \displaystyle=(1-p)E[(f(Z_{1},Z_{2},...,Z_{n})-f(Z_{1},Z_{2},...,-Z_{n}))^{2}] \displaystyle\leq 4(1-p)E\left[\left(\frac{\partial f}{\partial z_{n}}\right)^{2}\right]. As a result we obtain E[(Z_{n}-Z_{0})^{2}]\leq 4(1-p)\sum_{i=1}^{n}E\left[\left(\frac{\partial f}{\partial z_{i}}\right)^{2}\right], which is the sign-flipping analogue of the classical Gaussian Poincaré inequality. Next, we show that the inequality fails for identically distributed pairs. Proposition 3 . Let \epsilon\in\mathbb{R} , let X_{i} be uniform on [0,2\pi] and let Y_{i} equal X_{i}+2\epsilon mod 2\pi . Then X_{i}\stackrel{{\scriptstyle d}}{{=}}Y_{i} . Assume that the pairs (X_{i},Y_{i}) are independent as i varies. Let f(x_{1},\ldots x_{n})=\sin(x_{1}+\ldots+x_{n}) , and let Z_{i}=f(X_{1},\ldots X_{i},Y_{i+1},\ldots Y_{n}) . Then the random variables Z_{i} (and hence the ratio on the left-hand side of ( 1 )) depend on \epsilon , and we have \lim_{\epsilon\to 0}\frac{E(Z_{n}-Z_{0})^{2}}{\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2}}=n. (1) This is as bad as possible, since for arbitrary random variables Z_{i} by Cauchy-Schwarz applied to the sequences Z_{i+1}-Z_{i} and 1 , E(Z_{n}-Z_{0})^{2}\leq n\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2}. (2) Proof. With S=X_{1}+\ldots+X_{n} we have Z_{0}-Z_{n}=\sin(S+2n\epsilon)-\sin(S)=2\cos(S+n\epsilon)\sin(n\epsilon), E(Z_{0}-Z_{n})^{2}=2\sin^{2}(n\epsilon). Similarly, E(Z_{i}-Z_{i-1})^{2}=2\sin^{2}(\epsilon). So ( 1 ) equals to \lim_{\epsilon\to 0}\frac{\sin^{2}(n\epsilon)}{n\sin^{2}(\epsilon)}=n.\qed Finite support case Inspired by the counterexample of Proposition 3 , we may ask if a useful bound still exists when X_{i} can take only k_{i} values. For k\in\mathbb{Z}^{n}, the constant factor we get is given by \rho(k)=\max_{u,m}\frac{\sin^{2}(\sum_{i}\pi u_{i}/m_{i})}{\sum_{i}\sin^{2}(\pi u_{i}/m_{i})}, where the maximum is over all m,u\in\mathbb{Z}^{n} , satisfying 1\leq m_{i}\leq k_{i} , and 0\leq u_{i}<m_{i} for all i . We can bound this quantity as follows. Lemma 4 . \rho(k)\leq\max_{i}k_{i}/{2} . Proof. Let \ell=|\{i:u_{i}\neq 0\}| and \kappa=\max\limits_{i}k_{i}. Using \left\lvert\sin\left(\sum\limits_{i=1}^{\ell}x_{i}\right)\right\rvert\leq\sum\limits_{i=1}^{\ell}\left\lvert\sin(x_{i})\right\rvert and Cauchy-Schwarz, we get \rho(k)\leq\ell . For u_{i}\neq 0 , \sin\left(\frac{\pi u_{i}}{m_{i}}\right)\geq\sin\left(\frac{\pi}{m_{i}}\right)\geq\sin\left(\frac{\pi}{\kappa}\right)\geq\frac{2}{\kappa}. This gives \rho(k)\leq\frac{\kappa^{2}}{4\ell} . Hence \rho(k)\leq\ell\wedge\left(\frac{\kappa^{2}}{4\ell}\right)\leq\frac{\kappa}{2}.\qed Theorem 5 . For each i let (X_{i},Y_{i}) be an identically distributed pair, so that the pairs (X_{i},Y_{i}) are independent as i varies, and X_{i} can take at most k_{i} values. Let f be a bounded measurable function, and let Z_{i}=f(X_{1},\ldots X_{i},Y_{i+1},\ldots Y_{n}) . Then E(Z_{n}-Z_{0})^{2}\leq\rho(k)\sum_{i=1}^{n}E(Z_{i}-Z_{i-1})^{2},\qquad\rho(k)\leq\max_{i}k_{i}/2. Proof. It helps to allow complex-valued f , in which case the result applies to the squared modulus: E|Z_{n}-Z_{0}|^{2}\leq\frac{\kappa}{2}\sum_{j=1}^{n}E|Z_{j}-Z_{j-1}|^{2} First we consider the special case when all X_{j} is uniform on \mathbb{Z}_{k_{j}}=\{0,\ldots,k_{j}-1\} , and Y_{j}=X_{j}+1 mod k_{j} . Then \{e^{2\pi ivX_{j}/k_{j}},v\in\mathbb{Z}_{k_{j}}\} is an orthonormal basis for the law of X_{j} , and so \{\chi_{u}=\prod_{j}e^{2\pi iu_{j}X_{j}/k_{j}}\ :\,u\in\prod_{j}\mathbb{Z}_{k_{j}}=\mathcal{U}\} forms an orthonormal basis for the joint law of the X_{j} over the complex numbers. So we can write f(X_{1},\ldots,X_{n})=\sum_{u\in\mathcal{U}}c_{u}\chi_{u} for some coefficients c_{u} . We also have f(Y_{1},\ldots,Y_{n})=\sum_{u\in\mathcal{U}}\eta_{u}c_{u}\chi_{u}, where \eta(u)=\prod_{j}\eta_{j}^{u_{j}} , \eta_{j}=\exp(2\pi/k_{j}) . We have Z_{n}-Z_{0}=\sum_{u\in\mathcal{U}}(1-\eta_{u})c_{u}\chi_{u}. Similarly, we have Z_{j}-Z_{j-1}\stackrel{{\scriptstyle d}}{{=}}f(X_{1},\ldots,X_{n})-f(X_{1},\ldots,X_{j-1},Y_{j},X_{j+1},\ldots X_{n})=\sum_{u\in\mathcal{U}}(1-\eta_{j}^{u_{j}})c_{u}\chi_{u}. Squaring, taking expectations and using orthonormality, the desired inequality reads \sum_{u\in\mathcal{U}}|c_{u}|^{2}|1-\prod_{j}\eta_{j}^{u_{j}}|^{2}\leq\rho(k)\sum_{u\in\mathcal{U}}|c_{u}|^{2}\sum_{j}|1-\eta_{j}^{u_{j}}|^{2}, which follows by summing |c_{u}|^{2} times the inequality |1-\prod_{j}\eta_{j}^{u_{j}}|^{2}\leq\rho(k)\sum_{j}|1-\eta_{j}^{u_{j}}|^{2}, which

Read the complete text