Geodesic
Secretary problem with vanishing objects
Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 12 (2020) no. 2, pp. 63-81.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a version of the secretary problem where elements may vanish during the selection and become unchoosable. We construct a selection strategy and identify the probability to select the best element, which turns out to be asymptotically maximal as number of elements increases indefinitely. As an auxiliary result of independent interest we establish large deviation probability estimates for sums of independent variables with distinct geometric distribution.
Keywords: optimal selection problem, secretary problem, vanishing objects, large deviation probability. 
@article{MGTA_2020_12_2_a3,
     author = {Sergey I. Dotsenko and Georgiy M. Shevchenko},
     title = {Secretary problem with vanishing objects},
     journal = {Matemati\v{c}eska\^a teori\^a igr i e\"e prilo\v{z}eni\^a},
     pages = {63--81},
     publisher = {mathdoc},
     volume = {12},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MGTA_2020_12_2_a3/}
}
TY  - JOUR
AU  - Sergey I. Dotsenko
AU  - Georgiy M. Shevchenko
TI  - Secretary problem with vanishing objects
JO  - Matematičeskaâ teoriâ igr i eë priloženiâ
PY  - 2020
SP  - 63
EP  - 81
VL  - 12
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MGTA_2020_12_2_a3/
LA  - ru
ID  - MGTA_2020_12_2_a3
ER  - 
%0 Journal Article
%A Sergey I. Dotsenko
%A Georgiy M. Shevchenko
%T Secretary problem with vanishing objects
%J Matematičeskaâ teoriâ igr i eë priloženiâ
%D 2020
%P 63-81
%V 12
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MGTA_2020_12_2_a3/
%G ru
%F MGTA_2020_12_2_a3
Sergey I. Dotsenko; Georgiy M. Shevchenko. Secretary problem with vanishing objects. Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 12 (2020) no. 2, pp. 63-81. http://geodesic.mathdoc.fr/item/MGTA_2020_12_2_a3/

[1] Dynkin E. B., Yushkevich A. A., Teoremy i zadachi o protsessakh Markova, Nauka, M., 1967 | MR

[2] Gusein-Zade S. M., Razborchivaya nevesta, Biblioteka «Matematicheskoe prosveschenie», M., 2003, 24 pp.

[3] Gusein-Zade S. M., “Zadacha vybora i optimalnoe pravilo ostanovki posledovatelnosti nezavisimykh ispytanii”, Teoriya veroyatnostei i ee primeneniya, 11:3 (1966), 534–537

[4] Dotsenko S. I., Zakusilo O. K., “Zadacha optimalnogo vybora s «zaminirovannymi» ob'ektami”, Kibernetika i vychislitelnaya tekhnika, 2012, no. 170, 51–58

[5] Mazalov V. V., Matematicheskaya teoriya igr i prilozheniya, Lan, SPb., 2010

[6] Peshkov N. V., Svoistva optimalnogo momenta ostanovki v zadache nailuchshego vybora, Dissertatsiya na soisk. uch. step. kand. f.-m.n., Petrozavodsk, 2003 | Zbl

[7] Presman E. L., Sonin I. M., “Zadacha nailuchshego vybora pri sluchainom chisle ob'ektov”, Teoriya veroyatnostei i ee primeneniya, 17:4 (1972), 695–706 | Zbl

[8] Samuel-Cahn E., “The best-choice secretary problem with random freeze on jobs”, Stochastic Processes and their Applications, 55 (1995), 315–327 | DOI | MR | Zbl