Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T11:03:01.861Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal processes, secretary problems and the 1/e law

Published online by Cambridge University Press:  14 July 2016

Dietmar Pfeifer
Dietmar Pfeifer*
Affiliation:
University of Oldenburg
*
∗ Postal address: Fachbereich 6 Mathematik, Universität Oldenburg, Postfach 25 03, D-2900 Oldenburg, W. Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a class of secretary problems in which the order of arrival of candidates is no longer uniformly distributed. By a suitable embedding in a time-transformed extremal process it is shown that the asymptotic winning probability is again 1/e as in the classical situation. Extensions of the problem to more than one choice are also considered.

Keywords

NON-HOMOGENEOUS POISSON PROCESSPOISSON BINOMIAL DISTRIBUTIONCOUPLINGRECORD VALUES
Type
Research Papers
Information
Journal of Applied Probability , Volume 26 , Issue 4 , December 1989 , pp. 722 - 733
Copyright
Copyright © Applied Probability Trust 1989 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ballerini, R. and Resnick, S. I. (1985) Records from improving populations. J. Appl. Prob. 22, 487–502.Google Scholar
Ballerini, R. and Resnick, S. I. (1987a) Records in the presence of a linear trend. Adv. Appl. Prob. 19, 801–828.Google Scholar
Ballerini, R. and Resnick, S. I. (1987b) Embedding sequences of successive maxima in extremal processes, with applications. J. Appl. Prob. 24, 827–837.Google Scholar
Bruss, F. T. (1984) Patterns of relative maxima in random permutations. Ann. Soc. Sci. Bruxelles 98 (I), 19–28.Google Scholar
Deheuvels, P. and Pfeifer, D. (1986) A semigroup approach to Poisson approximation. Ann. Prob. 14, 663–676.Google Scholar
Dynkin, E. B. (1963) The optimal choice of the stopping moment for a Markov process. Dokl. Akad. Nauk. SSSR 150, 238–240.Google Scholar
Freeman, P. R. (1983) The secretary problem and its extensions: A review. Internat. Statist. Rev. 51, 189–206.Google Scholar
Gilbert, J. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.Google Scholar
Kemp, R. (1984) Fundamentals of the Average Case Analysis of Particular Algorithms. Wiley, New York; Teubner, Stuttgart (Chapter 3).Google Scholar
Nevzorov, V. B. (1986) Two characterizations using records. In Stability Problems for Stochastic Models. Lecture Notes in Mathematics 1233, Springer-Verlag, 79–85.Google Scholar
Pfeifer, D. (1986) Extremal processes, record times and strong approximation. Pub. Inst. Stat. Univ. Paris XXXI, 47–65.Google Scholar
Pfeifer, O. (1987) On a joint strong approximation theorem for record and inter-record times. Prob. Theory Rel. Fields 75, 213–221.Google Scholar
Rényi, A. (1962) Théorie des éléments saillants d'une suite d'observations. Colloquium on Combinatorial Methods in Probability Theory, 104–115, Mathematisk Institut, Aarhus Universitet, Denmark.Google Scholar
Resnick, S. I. (1973) Extremal processes and record value times. J. Appl. Prob. 10, 863–868.Google Scholar
Resnick, S. I. (1974) Inverses of extremal processes. Adv. Appl. Prob. 6, 392–406.Google Scholar
Resnick, S. I. (1975) Weak convergence to extremal processes. Ann. Prob. 3, 951–960.Google Scholar
Resnick, S. I. and Rubinovitch, M. (1973) The structure of extremal processes. Adv. Appl. Prob. 5, 287–307.Google Scholar
Ross, S. M. (1982) A simple heuristic approach to simplex efficiency. European J. Operat. Res. 9, 344–346.Google Scholar
Ross, S. M. (1983) Stochastic Processes. Wiley, New York (Chapter 4).Google Scholar
Serfling, R. J. (1978) Some elementary results on Poisson approximation in a sequence of Bernoulli trials. SIAM Rev. 20, 567–579.Google Scholar
Székely, G. J. (1986) Paradoxes in Probability Theory and Mathematical Statistics. D. Reidel, Dordrecht (Chapter 3).Google Scholar
Weissman, I. (1975) Extremal processes generated by non-identically distributed random variables. Ann. Prob. 3, 172–177.Google Scholar
Zhang, Y. S. (1988) Strong Approximations in Extremal Statistics (in German). Ph. D. Thesis, RWTH Aachen.Google Scholar