Efron–Extended

Efron-Stein Inequality23 If Xi, 1 ≤ i ≤ n + 1, are independent identically distributed random variables and S a symmetric function then,

σ2S(X1, . . . , Xn) ≤ EQ;

where, writing S˜ = 1n+1 ∑n+1

i=1 S(X, . . . , Xi, Xi+1, . . . , Xn+1),

Q = ∑n+1

( S(X, . . . , Xi, Xi+1, . . . , Xn+1)− S˜

)2 .