Back to Search
Start Over
Why do these quite different best-choice problems have the same solutions?
- Source :
- Advances in Applied Probability. 36:398-416
- Publication Year :
- 2004
- Publisher :
- Cambridge University Press (CUP), 2004.
-
Abstract
- The full-information best-choice problem, as posed by Gilbert and Mosteller in 1966, asks us to find a stopping rule which maximizes the probability of selecting the largest of a sequence of n i.i.d. standard uniform random variables. Porosiński, in 1987, replaced a fixed n by a random N, uniform on {1,2,…,n} and independent of the observations. A partial-information problem, imbedded in a 1980 paper of Petruccelli, keeps n fixed but allows us to observe only the sequence of ranges (max - min), as well as whether or not the current observation is largest so far. Recently, Porosiński compared the solutions to his and Petruccelli's problems and found that the two problems have identical optimal rules as well as risks that are asymptotically equal. His discovery prompts the question: why? This paper gives a good explanation of the equivalence of the optimal rules. But even under the lens of a planar Poisson process model, it leaves the equivalence of the asymptotic risks as somewhat of a mystery. Meanwhile, two other problems have been shown to have the same limiting risks: the full-information problem with the (suboptimal) Porosiński-Petruccelli stopping rule, and the full-information ‘duration of holding the best’ problem of Ferguson, Hardwick and Tamaki, which turns out to be nothing but the Porosiński problem in disguise.
- Subjects :
- Statistics and Probability
Applied Mathematics
010102 general mathematics
01 natural sciences
Combinatorics
010104 statistics & probability
Stopping time
Compound Poisson process
Optimal stopping
Fractional Poisson process
0101 mathematics
Equivalence (measure theory)
Random variable
Odds algorithm
Secretary problem
Mathematics
Subjects
Details
- ISSN :
- 14756064 and 00018678
- Volume :
- 36
- Database :
- OpenAIRE
- Journal :
- Advances in Applied Probability
- Accession number :
- edsair.doi.dedup.....9011b63afbecb784f9ab3e7fdfd65047