If S(x₁, x₂,⋯, xₙ) is any function of n variables and if Xᵢ, X̂ᵢ, 1 ≤ i ≤ n are $2n$ i.i.d. random variables then var S ≤ 1/2 E ∑ⁿᵢ₌₁ (S - Sᵢ)² where S = S(X₁, X₂,⋯, Xₙ) and Sᵢ is given by replacing the ith observation with X̂ᵢ, so Sᵢ = S(X₁, X₂,⋯, X̂ᵢ,⋯, Xₙ). This is applied to sharpen known variance bounds in the long common subsequence problem.
No takes yet. Share an insight, caveat, or question.
John Steele (1986) studied this question.