Prophet inequalities for optimal stopping rules with probabilistic recall
type: Item
instance of: scholarly article
title: Prophet inequalities for optimal stopping rules with probabilistic recall
zbMATH Open document ID: 1006.60036
author: David Assaf
author: Ester Samuel-Cahn
published in: Bernoulli
publication date: 2003-02-24T00:00:00Z
review text: 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.).
Mathematics Subject Classification ID: 60G40
Mathematics Subject Classification ID: 62L15
zbMATH DE Number: 1786692
zbMATH Keywords: optimal stopping
zbMATH Keywords: prophet regions
zbMATH Keywords: probabilistic recall
zbMATH Keywords: iid problem
zbMATH Keywords: backward solicitation
zbMATH Keywords: balayage technique
reviewed by: Krzysztof J. Szajowski
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1786692