×
Kuchta, Małgorzata; Morayne, Michał

Monotone case for an extended process. (English) Zbl 1305.60030

Adv. Appl. Probab. 46, No. 4, 1106-1125 (2014).
Summary: We consider a nonnegative discrete time and bounded horizon process \(X\) for which 0 is an absorbing state and extend it by a random variable that is independent of \(X\). We find a sufficient condition for the resulting process to satisfy, after a canonical time rescaling, the hypothesis of the monotone case theorem. If \(X\) describes a secretary type search on a poset with one maximal element or, if we consider \(X\) with no extension, then this condition assumes an especially simple log-concavity type form.

Cited in 2 Documents

MSC:

60G40 Stopping times; optimal stopping problems; gambling theory

Keywords:

monotone case theorem; secretary problem; optimal stopping time
Cite Review PDF
Full Text: DOI Euclid

References:

[1] Chow, Y. S., Robbins, H. and Siegmund, D. (1971). Great Expectations: The Theory of Optimal Stopping . Houghton Mifflin, Boston, MA. · Zbl 0233.60044
[2] Freij, R. and Wästlund, J. (2010). Partially ordered secretaries. Electron. Commun. Prob. 15 , 504-507. · Zbl 1225.60019 · doi:10.1214/ECP.v15-1579
[3] Garrod, B. and Morris, R. (2013). The secretary problem on an unknown poset. Random Structures Algorithms 43 , 429-451. · Zbl 1278.90192 · doi:10.1002/rsa.20466
[4] Garrod, B., Kubicki, G. and Morayne, M. (2012). How to choose the best twins. SIAM J. Discrete Math. 26 , 384-398. · Zbl 1247.60056 · doi:10.1137/09076845X
[5] Georgiou, N., Kuchta, M., Morayne, M. and Niemiec, J. (2008). On a universal best choice algorithm for partially ordered sets. Random Structures Algorithms 32 , 263-273. · Zbl 1138.06001 · doi:10.1002/rsa.20192
[6] Gilbert, J. P. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61 , 35-73. · doi:10.1080/01621459.1966.10502008
[7] Kaźmierczak, W. (2013). The best choice problem for a union of two linear orders with common maximum. Discrete Appl. Math. 161 , 3090-3096. · Zbl 1309.60041 · doi:10.1016/j.dam.2013.06.026
[8] Kozik, J. (2010). Dynamic threshold strategy for universal best choice problem. In 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms , Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 439-451. · Zbl 1357.60043
[9] Kuchta, M. (2014). Iterated full information secretary problem. Submitted. · Zbl 1386.60154
[10] Kuchta, M. and Morayne, M. (2014). A secretary problem with many lives. Commun. Statist. Theory Meth. 43 , 210-218. · Zbl 1398.60064 · doi:10.1080/03610926.2011.654040
[11] Kumar, R., Lattanzi, S., Vassilvitskii, S. and Vattani, A. (2011). Hiring a secretary from a poset. In Proc. ACM Conf. Electron. Commerce , ACM, New York, pp. 39-48.
[12] Kurpisz, A. and Morayne, M. (2014). Inform friends, do not inform enemies. IMA J. Math. Control Inf. 31 , 435-440. · Zbl 1297.93187 · doi:10.1093/imamci/dnt021
[13] Morayne, M. (1998). Partial-order analogue of the secretary problem: the binary tree case. Discrete Math. 184 , 165-181. · Zbl 0958.60041 · doi:10.1016/S0012-365X(97)00091-5
[14] Preater, J. (1999). The best-choice problem for partially ordered objects. Operat. Res. Lett. 25 , 187-190. · Zbl 1063.91506 · doi:10.1016/S0167-6377(99)00053-X
[15] Samuels, S. M. (1991). Secretary problems. In Handbook of Sequential Analysis , Dekker, New York, pp. 381-405.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.