The prophet inequality is related to the following scenario:

Suppose there are $n$ independent positive random variables $X_1,\dots,X_n$. They might not be identically distributed. We reveal them one at a time. When we see $X_i$, we have a choice between stopping with the value $X_i$, or continuing to search. If we reject all variables we get $0$.

How well can we do compared to a prophet who gets to see all variables before choosing a maximum? The prophet inequality says that there is a threshold $k$ such that the strategy where we stop whenever the value is at least $k$ gives expected value at least half of the expected value for the prophet.

Let $X$ be the random variable denoting the maximum of the $n$ values drawn. It is known that the threshold $k$ can be chosen in at least two ways:

  1. Choose $k_1$ so that $P(X>k_1)=\frac{1}{2}$, and
  2. Let $k_2=\frac12E[X]$.

These can be pretty different values. Are there other values of $k$ that work? For example, does any value of $k$ between $k_1$ and $k_2$ work?


In section D.2 of the appendix of Chawla et al. (2010), it is proven that you can take as your threshold any value $c$ in $[a,b]$, where $a= E[X]/2$ (following your notation) and $b$ is the unique solution of $$b=\sum_{i=1}^n E(X_i -b) ^+$$ with $x^+ = \max(x,0)$.

Actually, they reference the result to Samuel-Cahn, but they extend it to the setting where you can pick more than one value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.