A Difference Prophet Inequality for Bounded I.I.D. Variables, with Cost for Observations
Samuel-Cahn, Ester
Ann. Probab., Tome 20 (1992) no. 4, p. 1222-1228 / Harvested from Project Euclid
Let $X_i$ be i.i.d. random variables, $0 \leq X_i \leq 1$ and $c \geq 0$, and let $Y_i = X_i - ic$. It is shown that for all $n$, all $c$ and all such $X_i, E(\max_{i \geq 1} Y_i) - \sup_t EY_t < e^{-1}$, where $t$ is a stopping rule and $e^{-1}$ is shown to be the best bound for which the inequality holds. Specific bounds are also obtained for fixed $n$ or fixed $c$. These results are very similar to those obtained by Jones for a similar problem, where $0 \leq X_i \leq 1$ are independent but not necessarily identically distributed. All results are valid and unchanged also when $Y_i$ is replaced by $Y^\ast_i = \max_{1 \leq j \leq i} X_j - ic$.
Publié le : 1992-07-14
Classification:  Prophet inequality,  optimal stopping,  cost of observation,  60G40,  60E15
@article{1176989689,
     author = {Samuel-Cahn, Ester},
     title = {A Difference Prophet Inequality for Bounded I.I.D. Variables, with Cost for Observations},
     journal = {Ann. Probab.},
     volume = {20},
     number = {4},
     year = {1992},
     pages = { 1222-1228},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176989689}
}
Samuel-Cahn, Ester. A Difference Prophet Inequality for Bounded I.I.D. Variables, with Cost for Observations. Ann. Probab., Tome 20 (1992) no. 4, pp.  1222-1228. http://gdmltest.u-ga.fr/item/1176989689/