An Efron-Stein Inequality for Nonsymmetric Statistics

If S(x1,x2,⋯,xn) is any function of n variables and if Xi,X̂i,1 ≤ i ≤ n are 2n i.i.d. random variables then varS ≤ ½ E ∑i=1n (S - Si)2 where S = S (X1,X2,⋯,Xn) and Si is given by replacing the ith observation with X̂i, so Si=S(X1,X2,⋯,X̂i,⋯,Xn). This is applied to sharpen known variance bounds in the long common subsequence problem.