A Prophet Inequality Related to the Secretary Problem

Theodore P. Hill, Georgia Institute of Technology
Ulrich Krengel, University of Gottingen

Article comments

This article was first published in Contemporary Mathematics, published by the American Mathematical Society. Copyright © 1992 American Mathematical Society.

NOTE: At the time of publication, the author Theodore Hill was not yet affiliated with Cal Poly.

Abstract

Let Z1, Z2 , .. . , Zn be independent 0-1-valued random variables. A gambler gels a. reward 1 if he stop8 a.t the time of the last success and otherwise gets no reward. A simple comparison with a Poisson process is used to show that a prophet can do at most e times as well as the gambler using an optimal stopping time. For fixed n, the best constant is (n/(n -l ))"-1.