Embedding optimal selection problems in a Poisson process (Q1177212): Difference between revisions

A version of the classical ``secretary problem'' is considered, where the number \(N\) of candidates available is a random variable. The \(N\) candidates arrive at times which are independent and uniformly distributed on \((0,1)\), and the objective is to minimize a loss which is a non-decreasing function of the ranks of the candidates. This problem has been variously studied by \textit{J. Gianini} and \textit{S. M. Samuels} [Ann. Probab. 4, 418-432 (1976; Zbl 0341.60033)], by \textit{R. Cowan} and \textit{J. Zabczyk} [Theory Probab. Appl. 23, 584-592 (1979); reprinted from Teor. Veroyatn. Primen. 23, 606-614 (1978; Zbl 0396.62063)], by \textit{W. J. Stewart} [Applied probability -- computer science: the interface, Proc. Meet., Boca Raton/FL 1981, Vol. 1, Prog. Comput. Sci. 2, 275-296 (1982; Zbl 0642.60075)], and by \textit{F. T. Bruss} [Ann. Probab. 12, 882- 889 (1984; Zbl 0553.60047)] and \textit{F. T. Bruss} and \textit{S. M. Samuels} [ibid. 15, 824-830 (1987; Zbl 0592.60034)]. The main contribution of this paper is to show that by imbedding the process in a Poisson process it is possible to obtain all the distributional results necessary to obtain the optimal policy. The special case where \(N\) is geometrically distributed is particularly simple, and the optimal policy can be found explicitly, but even in the case where \(N\) has an arbitrary distribution, it is shown that routine calculus methods can be used to prove that the optimal policy is of a certain conjectured form.