Prophet inequalities for optimal stopping rules with probabilistic recall (Q1611561)

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 \textit{U. Krengel} and \textit{L. Sucheston}, in: Problems on Banach spaces. Adv. Probab. Relat. Top. 4, 197-266 (1978) and \textit{T. P. Hill} and \textit{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.).