zbMATH — the first resource for mathematics

Embedding optimal selection problems in a Poisson process. (English) Zbl 0745.60040
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 J. Gianini and S. M. Samuels [Ann. Probab. 4, 418-432 (1976; Zbl 0341.60033)], by R. Cowan and J. Zabczyk [Theory Probab. Appl. 23, 584-592 (1979); reprinted from Teor. Veroyatn. Primen. 23, 606-614 (1978; Zbl 0396.62063)], by 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 F. T. Bruss [Ann. Probab. 12, 882- 889 (1984; Zbl 0553.60047)] and F. T. Bruss and 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.

60G40 Stopping times; optimal stopping problems; gambling theory
Full Text: DOI
[1] BrĂ©maud, P., Point processes and queues: martingale dynamics, (1981), Springer New York · Zbl 0478.60004
[2] Bruss, F.T., A unified approach to a class of best choice problems with an unknown number of options, Ann. probab., 12, 3, 882-889, (1984) · Zbl 0553.60047
[3] Bruss, F.T., Invariant record processes and applications to optimal selection modelling, Stochastic process. appl., 30, 303-316, (1988) · Zbl 0665.60049
[4] Bruss, F.T.; Samuels, S.M., A unified approach to a class of optimal selection problems with an unknown number of options, Ann. probab., 15, 2, 824-830, (1987) · Zbl 0592.60034
[5] Bruss, F.T.; Samuels, S.M., Conditions for quasi-stationarity of the Bayes rule in selection problems with an unknown number of rankable options, Ann. probab., 18, 2, (1990) · Zbl 0704.62067
[6] Cowan, R.; Zabczyk, J., (1978) an optimal selection problem associated with the Poisson process, Theory probab. appl., 23, 584-592, (1978) · Zbl 0426.62058
[7] Gaver, D.P., Random record models, J. appl. probab., 13, 538-547, (1976) · Zbl 0399.60083
[8] Gianini, J.; Samuels, S.M., The infinite secretary problem, Ann. probab., 4, 2, 418-432, (1976) · Zbl 0341.60033
[9] Goldie, C.M.; Rogers, L.C.G., The k-record processes are i.i.d., Z. wahrsch. verw. gebiete, 67, 197-211, (1984) · Zbl 0535.60037
[10] Stewart, T.J., (1981) the secretary problem with an unknown number of options, Oper. res., 29, 130-145, (1981) · Zbl 0454.90042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.