Prophet inequalities and order selection in optimal stopping problems

Hill, T. P.

doi:10.1090/S0002-9939-1983-0691293-4

Prophet inequalities and order selection in optimal stopping problems
HTML articles powered by AMS MathViewer

by T. P. Hill PDF

Proc. Amer. Math. Soc. 88 (1983), 131-137 Request permission

Abstract:

A complete determination is made of the possible values for $E\left ( {\sup {X_n}} \right )$ and $\sup \left \{ {E{X_t}:t\;{\text {a}}\;{\text {stop rule}}} \right \}$ for ${X_1},{X_2}, \ldots$ independent uniformly bounded random variables; this yields results of Krengel, Sucheston, and Garling, and of Hill and Kertz as easy corollaries. In optimal stopping problems with independent random variables where the player is free to choose the order of observation of these variables it is shown that the player may do just as well with a prespecified fixed ordering as he can with order selections which depend sequentially on past outcomes. A player’s optimal expected gain if he is free to choose the order of observation is compared to that if he is not; for example, if the random variables are nonnegative and independent, he may never do better than double his optimal expected gain by rearranging the order of observation of a given sequence.

References

Antoine Brunel and Ulrich Krengel, Parier avec un prophète dans le cas d’un processus sous-additif, C. R. Acad. Sci. Paris Sér. A-B 288 (1979), no. 1, A57–A60 (French, with English summary). MR 522020
Y. S. Chow, Herbert Robbins, and David Siegmund, Great expectations: the theory of optimal stopping, Houghton Mifflin Co., Boston, Mass., 1971. MR 0331675
Theodore P. Hill and Robert P. Kertz, Ratio comparisons of supremum and stop rule expectations, Z. Wahrsch. Verw. Gebiete 56 (1981), no. 2, 283–285. MR 618276, DOI 10.1007/BF00535745
T. P. Hill and Robert P. Kertz, Additive comparisons of stop rule and supremum expectations of uniformly bounded independent random variables, Proc. Amer. Math. Soc. 83 (1981), no. 3, 582–585. MR 627697, DOI 10.1090/S0002-9939-1981-0627697-3
T. P. Hill and Robert P. Kertz, Comparisons of stop rule and supremum expectations of i.i.d. random variables, Ann. Probab. 10 (1982), no. 2, 336–345. MR 647508
Theodore P. Hill and Victor C. Pestien, The advantage of using nonmeasurable stop rules, Ann. Probab. 11 (1983), no. 2, 442–450. MR 690141
Ulrich Krengel and Louis Sucheston, Semiamarts and finite values, Bull. Amer. Math. Soc. 83 (1977), no. 4, 745–747. MR 436314, DOI 10.1090/S0002-9904-1977-14378-4
Ulrich Krengel and Louis Sucheston, On semiamarts, amarts, and processes with finite value, Probability on Banach spaces, Adv. Probab. Related Topics, vol. 4, Dekker, New York, 1978, pp. 197–266. MR 515432