Wald for non-stopping times: the rewards of impatient prophets

Alexander E Holroyd (Microsoft Research)
Yuval Peres (Microsoft Research)
Jeffrey E Steif (Chalmers University of Technology and Göteborg University)

Abstract


Let $X_1,X_2,\ldots$ be independent identically distributed nonnegative random variables. Wald's identity states that the random sum $S_T:=X_1+\cdots+X_T$ has expectation $\mathbb{E} T \cdot \mathbb{E} X_1$ provided $T$ is a stopping time. We prove here that for any $1<\alpha\leq 2$, if $T$ is an arbitrary nonnegative random variable, then $S_T$ has finite expectation provided that $X_1$ has finite $\alpha$-moment and $T$ has finite $1/(\alpha-1)$-moment. We also prove a variant in which $T$ is assumed to have a finite exponential moment. These moment conditions are sharp in the sense that for any i.i.d. sequence $X_i$ violating them, there is a $T$ satisfying the given condition for which $S_T$ (and, in fact, $X_T$) has infinite expectation.An interpretation of this is given in terms of a prophet being more rewarded than a gambler when a certain impatience restriction is imposed.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-9

Publication Date: November 12, 2014

DOI: 10.1214/ECP.v19-3609

References

  • Baum, Leonard E.; Katz, Melvin. Convergence rates in the law of large numbers. Trans. Amer. Math. Soc. 120 1965 108--123. MR0198524
  • Chow, Yuan Shih; Teicher, Henry. Probability theory. Independence, interchangeability, martingales. Second edition. Springer Texts in Statistics. Springer-Verlag, New York, 1988. xviii+467 pp. ISBN: 0-387-96695-1 MR0953964
  • Erdos, P. On a theorem of Hsu and Robbins. Ann. Math. Statistics 20, (1949). 286--291. MR0030714
  • Erdos, P. Remark on my paper "On a theorem of Hsu and Robbins.'' Ann. Math. Statistics 21, (1950). 138. MR0032970
  • Gut, Allan. Probability: a graduate course. Second edition. Springer Texts in Statistics. Springer, New York, 2013. xxvi+600 pp. ISBN: 978-1-4614-4707-8; 978-1-4614-4708-5 MR2977961
  • Hoffmann-Jorgensen, Jorgen. Sums of independent Banach space valued random variables. Studia Math. 52 (1974), 159--186. MR0356155
  • Hill, Theodore P.; Kertz, Robert P. A survey of prophet inequalities in optimal stopping theory. Strategies for sequential search and selection in real time (Amherst, MA, 1990), 191--207, Contemp. Math., 125, Amer. Math. Soc., Providence, RI, 1992. MR1160620
  • Hsu, P. L.; Robbins, Herbert. Complete convergence and the law of large numbers. Proc. Nat. Acad. Sci. U. S. A. 33, (1947). 25--31. MR0019852
  • Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169
  • Katz, Melvin L. The probability in the tail of a distribution. Ann. Math. Statist. 34 1963 312--318. MR0144369
  • Krengel, Ulrich; Sucheston, Louis. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces, pp. 197--266, Adv. Probab. Related Topics, 4, Dekker, New York, 1978. MR0515432
  • Royden, H. L. Real analysis. Third edition. Macmillan Publishing Company, New York, 1988. xx+444 pp. ISBN: 0-02-404151-3 MR1013117
  • Sokal, Alan D. A really simple elementary proof of the uniform boundedness theorem. Amer. Math. Monthly 118 (2011), no. 5, 450--452. MR2805031
  • Wald, Abraham. On cumulative sums of random variables. Ann. Math. Statistics 15, (1944). 283--296. MR0010927


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.