Comparisons of Optimal Stopping Values and Prophet Inequalities for Negatively Dependent Random Variables

Let Y = (Y₁, ⋯, Yₙ) be random variables satisfying the weak negative dependence condition: P(Yᵢ < aᵢ Y₁ < a₁, ⋯, Yᵢ₋₁) ≤ P(Yᵢ < aᵢ) for i = 2, ⋯, n and all constants a₁, ⋯, aₙ. Let X = (X₁, ⋯, Xₙ) have independent components, where Xᵢ and Yᵢ have the same marginal distribution, i = 1, ⋯, n. It is shown that V(X) ≤ V(Y), where V(Y) = ₜ: t is a stopping rule for Y₁,⋯, Yₙ\. Also, the classical inequality which for nonnegative variables compares the expected return of a prophet E₁ ⋯ Yₙ\ with that of the statistician V(Y), i.e., E₁ ⋯ Yₙ\ < 2V(Y), holds for nonnegative Y satisfying the negative dependence condition. Moreover, this inequality can be obtained by an explicitly described threshold rule $t(b)$, i.e., E₁ ⋯ Yₙ\ < 2EYt(b). Generalizations of this prophet inequality are given. Extensions of the results to infinite sequences are obtained.