Prophet inequalities for bounded negatively dependent random variables

It is shown that if Xk satisfy P(Xk < ak|X1 < a1,..., Xk-1 < ak-1) is nondecreasing in a1,..., ak-1, a negative dependence condition slightly weaker than CDS, and 0 [less-than-or-equals, slant] Xk [less-than-or-equals, slant] 1, then E[max Xk] [less-than-or-equals, slant] 2V - V2, where V = sup EXt, t, a stopping rule, holds both for finite and infinite sequences X1, X2,.... Actually, here V can be replaced by the optimal value attainable by threshold rules.