Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution

Correa, Jose ORCID: 0000-0002-3012-7622, Dutting, Paul, Fischer, Felix ORCID: 0000-0002-8403-9273 and Schewior, Kevin . Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution. Math. Oper. Res.. CATONSVILLE: INFORMS. ISSN 1526-5471

Full text not available from this repository.

DOI:10.1287/moor.2021.1167

Abstract

A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables: given a sequence of random variables X-1, ... , X-n drawn independently from the same distribution, the goal is to choose a stopping time tau such that for the maximum value of a and for all distributions, E[X-tau] >= alpha center dot E[max(t)X(t)]. What makes this problem challenging is that the decision whether tau = t may only depend on the values of the random variables X-1, ..., X-t and on the distribution F. For a long time, the best known bound for the problem had been alpha >= 1 - 1/e approximate to 0.632, but recently a tight bound of alpha >= 0.745 was obtained. The case where F is unknown, such that the decision whether tau = t may depend only on the values of the random variables X-1, ..., X-t, is equally well motivated but has received much less attention. A straightforward guarantee for this case of alpha >= 1/e approximate to 0:368 can be derived from the well-known optimal solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We showthat this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F, andwe show that, even with o(n) samples, alpha <= 1/e. On the other hand, n samples allow for a significant improvement, whereas O(n(2)) samples are equivalent to knowledge of the distribution: specifically, with n samples, alpha >= 1 - 1/e approximate to 0.632 and a <= ln (2) approximate to 0.693, and with O(n(2)) samples, alpha >= 0.745 - epsilon for any epsilon > 0.

Item Type:

Journal Article

Creators:

Creators	Email	ORCID	ORCID Put Code
Correa, Jose	UNSPECIFIED	orcid.org/0000-0002-3012-7622	UNSPECIFIED
Dutting, Paul	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED
Fischer, Felix	UNSPECIFIED	orcid.org/0000-0002-8403-9273	UNSPECIFIED
Schewior, Kevin	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED