×

Prophet inequalities for optimal stopping rules with probabilistic recall. (English) Zbl 1006.60036

The paper deals with an extension of the prophet problems when statistician is able to solicit an observation not chosen in the past when it has appeared. A sequence of random variables \(X_1,X_2,\ldots,X_n\) are observed sequentially and the probability vector \({\mathbf p}=(p_1,p_2,\ldots,p_{n-1})\), where \(1\geq p_1\geq p_2\geq\ldots\geq p_{n-1}\geq 0\), is given. Two models of availability are considered. (i) If an item \(X_i\) is not available at time \(k>i\), it will remain unavailable beyond \(k\). (ii) The items are available by probabilistic recall using the vector \(({\mathbf p})\). Three modes of stopping are taken into account. Only one object may be chosen. Let \(V_{\mathbf{p}}(X_1,\ldots,X_n)\) be the optimal value to statistician. It is shown that for all non-trivial, non-negative \(X_i\) and all \(n\geq 2\) we have \[ \mathbf{E}\max(X_1,\ldots,X_n)<(2-p_{n-1})V_{\mathbf{p}}(X_1,\ldots,X_n) \] and \(2-p_{n-1}\) is the best constant [see U. Krengel and L. Sucheston, in: Problems on Banach spaces. Adv. Probab. Relat. Top. 4, 197-266 (1978) and T. P. Hill and R. P. Kertz, Z. Wahrscheinlichkeitstheorie Verw. Geb. 56, 283-285 (1981; Zbl 0443.60039) for the classical ratio prophet inequality]. It is proved also that for bounded independent random variables such that \(a\leq X_i\leq b\), \(i=1,2,\ldots,n\), we have \[ \mathbf{E}\max(X_1,\ldots,X_n)-V_{\mathbf{p}}(X_1,\ldots,X_n)\leq \left[\frac{1-\sqrt{1-p_{n-1}}}{p_{n-1}}\right]^2(1-p_{n-1})(b-a). \] It is a generalization of the result by T. P. Hill and R. P. Kertz (loc. cit.).

MSC:

60G40 Stopping times; optimal stopping problems; gambling theory
62L15 Optimal stopping in statistics

Citations:

Zbl 0443.60039
PDFBibTeX XMLCite