An Efron-Stein inequality for nonsymmetric statistics (Q1083143)

If \(S(x_ 1,x_ 2,...,x_ n)\) is any function of n variables and if \(X_ i,\hat X_ i\), \(1\leq i\leq n\) are 2n i.i.d. random variables then \[ var S\leq E\sum^{n}_{i=1}(S-S_ i)^ 2, \] where \(S=S(X_ 1,X_ 2,...,X_ n)\) and \(S_ i\) is given by replacing the ith observation with \(\hat X{}_ i\), so \(S_ i=S(X_ 1,X_ 2,...,\hat X_ i,...,X_ n)\). This is applied to sharpen known variance bounds in the long common subsequence problem.