Optimal selection problems based on exchangeable trials. (English) Zbl 0903.60034

Some considerations related to the secretary problem [cf. T. S. Ferguson, Stat. Sci. 4, No. 3, 282-296 (1989; Zbl 0788.90080)] are given. It is the class of optimal stopping problems with loss function \(q\) dependent on the rank of the stopped random variable. S. M. Samuels [“Sufficiently noninformative priors for the secretary problem; the case \(n=3\)” (Preprint, Dept. Statistics, Pardue Univ., 1994)] has called distributions of an exchangeable sequence of random variables \(X_1,\ldots,X_n\) without ties, for which the observation of the values of the \(X_i\)’s gives no advantage in comparison with the observation of just the relative ranks of the variables, \(q\)-noninformative. The following questions have been posed: (1) For a given loss function \(q\) does there exist a \(q\)-noninformative distribution for the \(\{X_i\}\) such that the minimal risk using stopping rules based on the relative ranks only is the same as that for the wider class of stopping rules adapted to the natural filtration of the sequence? (2) Is there a stopping rule, may be randomized, with respect to the larger filtration which performs better than any rule just based on the relative ranks for any distribution of the sequence?
Necessary and sufficient conditions for overall optimality of a rank rule in terms of some inequalities on predictive probabilities of relative ranks are given. It is shown that for any \(n\), there exist losses \(q\), for which the first question has a negative answer. Special attention is given to the classical problem of minimizing the expected rank: for \(n\) even, explicitly universal (randomized) stopping rules which are strictly better than the rank rules for any exchangeable sequence, have been constructed.


60G40 Stopping times; optimal stopping problems; gambling theory


Zbl 0788.90080
Full Text: DOI


[1] BEREZOVSKIY, B. A. and GNEDIN, A. V. 1984. The Best Choice Problem. Nauka, Moscow. Z. · Zbl 0579.62066
[2] CHOW, Y. S., MORIGUTI, S., ROBBINS, H. and SAMUELS, S. M. 1964. Optimal selection based on Z. relative rank the “secretary problem”. Israel J. Math. 2 81 90. Z. · Zbl 0149.14402
[3] COVER, T. M. 1987. Pick the largest number. In Open Problems in Communication and Z. Computation T. M. Cover and B. Gopinath, eds. 152. Springer, New York. Z. · Zbl 0628.68001
[4] FERGUSON, T. S. 1989. Who solved the secretary problem? Statist. Sci. 4 282 289. Z. · Zbl 0788.90080
[5] GNEDIN, A. V. 1994. A solution to the game of Googol. Ann. Probab. 22 1588 1595. Z. · Zbl 0815.60038
[6] GNEDIN, A. V. 1995. On a class of exchangeable sequences. Statist. Probab. Lett. 25 351 355. Z. · Zbl 0838.60033
[7] GNEDIN, A. V. and KRENGEL, U. 1995. A stochastic game of optimal stopping and order selection. Ann. Appl. Probab. 5 310 321. Z. · Zbl 0824.62079
[8] HILL, B. M. 1968. Posterior distribution of percentiles: Bay es theorem for sampling from a finite population. J. Amer. Statist. Assoc. 63 677 691. Z. JSTOR: · Zbl 0159.48402
[9] HILL, T. P. and KENNEDY, D. P. 1992. Sharp inequalities for optimal stopping with rewards based on ranks. Ann. Appl. Probab. 2 503 517. Z. · Zbl 0758.60041
[10] KAMAE, T., KRENGEL, U. and O’BRIEN, G. L. 1977. Stochastic inequalities on partially ordered spaces. Ann. Probab. 5 899 912. Z. · Zbl 0371.60013
[11] LANE, D. and SUDDERTH, W. 1978. Diffuse models for sampling and predictive inference. Ann. Statist. 6 1318 1336. Z. · Zbl 0398.62003
[12] SAMUELS, S. M. 1981. Minimax stopping rules when the underlying distribution is uniform. J. Amer. Statist. Assoc. 76 188 197. Z. JSTOR: · Zbl 0459.62070
[13] SAMUELS, S. M. 1989. Who will solve the secretary problem? Statist. Sci. 4 289 291. Z. Z SAMUELS, S. M. 1991. Secretary problems. In Handbook of Sequential Analy sis B. K. Ghosh. and P. K. Sen, eds.. Dekker, New York. Z.
[14] SAMUELS, S. M. 1994. Sufficiently noninformative priors for the secretary problem; the case: n 3. Preprint, Dept. Statistics, Purdue Univ. Z.
[15] SILVERMAN, S. and NADAS, A. 1992. On the game of googol as the secretary problem. Contemp. Ḿath. 125 77 83. Z. VOROB’EV, N. N. 1962. Consistent families of measures and their extensions. Theory Probab. Appl. 7 153 169.
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.