Prophet inequalities for bounded negatively dependent random variables (Q1181108)

Let \((X_ k)\) be a finite or infinite sequence of [0,1]-valued random variables which are negatively dependent in the sense that \(P(X_ k<a_ k\mid X_ 1<a_ 1,\dots,X_{k-1}<a_{k-1})\) is non-decreasing in \(a_ 1,\dots,a_{k-1}\). It is proved that \(E(\sup X_ k)\leq 2V - V^ 2\), where \(V=\sup E X_ t\), the supremum taken over all stopping rules. One can replace \(V\) by the corresponding supremum over all threshold rules.