Prophet inequalities for cost of observation stopping problems (Q1814046)

Consider an optimal stopping problem where a gambler observes a sequence of bounded random variables \(X_1,X_2,\ldots\), and attempts to select the largest observation, using only the information provided by previous observed values. The problem of finding the gambler's optimal stopping time and his optimal expected gain has been the subject of a large body of research. A prophet inequality gives a bound which ties the gambler's optimal expected gain to the expected maximum of the sequence of random variables (the prophet's expected gain). \textit{U. Krengel} and \textit{L. Sucheston} [Bull. Am. Math. Soc. 83, 745--747 (1977; Zbl 0336.60032)] found an inequality for the ratio of the expected gain of the prophet to the expected gain of the gambler when the random variables \(X_1,X_2,\ldots\) are independent, and \textit{T. P. Hill} and \textit{R. P. Kertz} found inequalities for the difference of the expected gains in the case of independent random variables [Proc. Am. Math. Soc. 83, 582--585 (1981; Zbl 0476.60044)] and of dependent random variables [Trans. Am. Math. Soc. 278, 197--207 (1983; Zbl 0517.60051)]. All those inequalities are sharp. In another direction, there has been some research on finding the optimal stopping time and the optimal expected gain for a problem where the gambler incurs a cost for each value observed. \textit{J. MacQueen} and \textit{R. G. Miller jun}. [Oper. Res. 8, 362--380 (1960; Zbl 0096.12102)] and \textit{Y. Chow} and \textit{H. Robbins} [Proc. 4th Berkeley Symp. Math. Stat. Probab. 1, 93--104 (1961; Zbl 0126.14002)] have considered this problem. In the present paper, sharp inequalities are given for the difference between the expected gains of the gambler and of the prophet in the case of independent random variables when there is a search cost.