i
i
“Vidmar” — 2017/5/29 — 11:01 — page 1 — #1 i
i
i
i
i
i
PROBLEM IZBIRE NAJBOLJŠE TAJNICE
MATIJA VIDMAR
Fakulteta za matematiko in fiziko, Univerza v Ljubljani
Inštitut za matematiko, fiziko in mehaniko
Math. Subj. Class. (2010): 60G40, 62L15
V problemu izbire najbolǰse tajnice zaporedoma intervjuvamo za eno samo odprto
delovno mesto n ∈ N≥2 kandidatov s ciljem, da izberemo najbolǰsega med njimi. O
zavrnitvi ali sprejemu kandidata se moramo odločiti takoj po njegovem intervjuju. Za
velike n je, v približku, optimalno zavrniti prvih n/e kandidatov in nato vzeti prvega, ki
je bolǰsi od vseh preǰsnjih; najbolǰsega tako izberemo z verjetnostjo 1/e. Problem ima
natančno in eksplicitno rešitev za vse n.
SECRETARY PROBLEM
In the secretary problem we consecutively interview, for a single open position, n ∈
N≥2 applicants, with the goal of choosing the best. The decision of whether to reject or
accept a given applicant must be made immediately following his interview. For large n,
approximately, it is optimal to decline the first n/e candidates and then to hire the first
one that is better than all his predecessors; the best being thus chosen with probability
1/e. The problem admits a precise and explicit solution for arbitrary n.
Uvod in zamejitev problema
Pričnimo z natančnim opisom klasičnega problema izbire tajnice.
(i) Na voljo je eno prosto delovno mesto (tajnice).
(ii) Imamo n kandidatov, n ∈ N≥2 je znan a priori (je neslučajen). Nobena
dva kandidata nista enako sposobna. Stopnja sposobnosti kandidatov
nam ni znana a priori.
(iii) Kandidate intervjuvamo zaporedoma, pri čemer so vsi vrstni redi enako
verjetni.
(iv) Po vsakem intervjuju lahko že intervjuvane kandidate linearno uredimo
od najbolǰsega do najslabšega. Pravkar intervjuvanega kandidata ta-
koj bodisi zavrnemo ali sprejmemo na delovno mesto in odločitve ne
moremo več spremeniti. Na koncu ni nujno, da mesto zapolnimo.
(v) Odločitev o tem, ali kandidata sprejeti ali zavrniti, je odvisna samo od
relativne razvrstitve kandidatov, ki so že bili intervjuvani.
(vi) Maksimizirati želimo verjetnost, da izberemo najbolǰsega kandidata.
Obzornik mat. fiz. 64 (2017) 1 1
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 2 — #2 i
i
i
i
i
i
Matija Vidmar
Opisano je dobro znan problem iz teorije optimalnega ustavljanja, ležeč
na preseku verjetnosti in optimizacije. Klasična monografija s tega podro-
čja je [1]. Natančneje ga uvrščamo na področje optimalnega ustavljanja
verig Markova v diskretnem času, glej npr. [5, str. 135, primer 8.16], [7,
str. 485]. Problem ima relativno kratko, a bogato zgodovino, katere obja-
vljeni začetki segajo v drugo polovico 20. stoletja. Originalno avtorstvo ni
jasno. Bralca, ki ga zanima natančneǰsi zgodovinski opis, napotimo npr. na
pregledna članka [8, razdelek 3] in [9, razdelek 1.2]. V tem pogledu nave-
dimo še, da je problem poznan tudi pod drugimi imeni: problem poroke oz.
dote, problem lepotnega tekmovanja, problem najbolǰse izbire, če jih nave-
demo le nekaj. Njegova privlačnost je v tem, da ima preprosto, elementarno
in eksplicitno rešitev. Zares imamo sledečo trditev, ki jo bomo dokazali v
naslednjem razdelku.
Trditev 1. Definirajmo
rn := min
{
r ∈ {1, . . . , n− 1} :
n−1∑
i=r
1
i
≤ 1
}
in
Pn : =

1/2, za n = 2
rn − 1
n
n−1∑
i=rn−1
1
i
, za n ≥ 3
.
Potem je
»Zavrni prvih rn − 1 kandidatov in nato izberi prvega, ki je bolǰsi
od vseh svojih predhodnikov, če ta obstaja.«
optimalna strategija za obravnavani problem; pri tem je verjetnost, da izbe-
remo najbolǰsega kandidata, enaka Pn. Zaporedje (Pn)n∈N≥2 pada proti in
ima člene strogo večje od e−1. Zaporedje ( rnn )n∈N≥2 pa ima člene prav tako
strogo večje od e−1 in konvergira proti e−1. Na kratko: e−1 < Pn ↓ e−1 in
e−1 < rnn → e
−1.
Intuitivno je dokaj jasno, da Pn pada z naraščajočim n. Morda prese-
netljivo pa je, da verjetnost Pn ne pada proti nič (marveč proti e
−1).
Problem je bil študiran v številnih razširitvah in variantah: število kan-
didatov je lahko slučajno namesto deterministično; na voljo je lahko več kot
eno mesto in posledično želimo izbrati nekaj najbolǰsih kandidatov; kvalitete
2 Obzornik mat. fiz. 64 (2017) 1
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 3 — #3 i
i
i
i
i
i
Problem izbire najboljše tajnice
kandidatov so lahko merljive in njihove vrednosti (vendar ne pripadnost po-
sameznemu kandidatu) poznane a priori ; odločitve lahko z določenim stro-
škom spreminjamo za nazaj; maksimiziramo lahko kvaliteto izbranega kan-
didata, kadar je ta merljiva; intervjuvamo v zveznem času itd.: glej članka
[8, razdelki 4–7] in [9, razdelki 2–9] za nadrobneǰsi opis (v ruščini je dostopna
tudi knjiga [4], ki je v celoti posvečena problemu tajnice in njegovim variaci-
jam). Nekaj zanimivih verzij bo bralec našel v člankih [10, 11, 13, 6, 2, 14].
Posebej zabavna je primerjava s problemom podoktoranda, v katerem
želimo, ceteris paribus, izbrati drugega najbolǰsega kandidata (»najbolǰsi bo
šel na univerzo Harvard«). Naj bo
kn := [n/2] =
{
n/2, če je n sod
(n− 1)/2, če je n lih
.
Optimalna strategija v tem primeru je:
»Zavrni prvih kn kandidatov in nato izberi prvega, ki je drugi naj-
bolǰsi od vseh svojih predhodnikov, če ta obstaja.«
Pri tem je verjetnost, da izberemo drugega najbolǰsega kandidata, enaka
kn(n−kn)
n(n−1) ≈ 1/4. Lažje je izbrati najbolǰsega kot drugega najbolǰsega kandi-
data! Za dokaz glej [15] ali [13].
Rešitev problema izbire najbolǰse tajnice in njena analiza
Začnimo z nekaj uvodnimi opažanji in dogovori.
• Ker je odločitev, ali izbrati kandidata (in ustaviti intervjuje) ali na-
daljevati intervjuje, odvisna samo od relativnega ranga kandidatov, ki so
že bili intervjuvani, je različnih možnih pravil ustavljanja (tj. pravil izbire
kandidata za odprto delovno mesto) končno mnogo. V posebnem optimalno
pravilo obstaja.
• Za intervjuvanega kandidata bomo rekli, da je relativno najbolǰsi, če
je bolǰsi od vseh kandidatov, ki so bili intervjuvani pred njim. Kadar pa
bomo rekli, da je kandidat najbolǰsi, bomo imeli v mislih, da je on najbolǰsi
izmed sploh vseh kandidatov. Razvidno je, da lahko v optimalni strategiji
izbiramo vedno samo relativno najbolǰse kandidate.
• Denimo, da je j-ti kandidat relativno najbolǰsi. Potem bomo v opti-
malni strategiji le-tega izbrali, če bo, pogojno glede na informacijo, ki smo
jo prejeli do vključno njegovega intervjuja, verjetnost, da je on najbolǰsi –
označimo jo s Pj – vsaj tako velika kot verjetnost – označimo jo s Qj –,
1–9 3
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 4 — #4 i
i
i
i
i
i
Matija Vidmar
da izberemo najbolǰsega kandidata, če z intervjuji nadaljujemo (in izbiramo
optimalno). Sledi, da obstaja optimalna strategija oblike:
»Izberi kandidata j, če je ta relativno najbolǰsi in je Pj ≥ Qj , sicer
nadaljuj.«
• Končno trdimo, da obstaja optimalno pravilo oblike:
S(r): »Zavrni prvih r−1 kandidatov in nato izberi prvega relativno
najbolǰsega, če ta obstaja.«
za neki r ∈ {1, . . . , n}. (Vsa možna pravila ustavljanja seveda niso take
oblike. Za i ∈ {1, . . . , n} lahko npr. vedno izberemo po vrsti i-tega ali pa
i-tega relativno najbolǰsega kandidata.)
Res. Po eni strani lahko izrazimo
Pj = P(j-ti kandidat je najbolǰsi|j-ti kandidat je relativno najbolǰsi)
=
P(j-ti kandidat je najbolǰsi)
P(j-ti kandidat je relativno najbolǰsi)
=
1/n
1/j
= j/n.
Po drugi strani je Qj preprosto enak optimalni (tj. maksimalni, uporabljajoč
najbolǰso strategijo) verjetnosti, da izberemo najbolǰsega kandidata, če se že
na začetku omejimo na strategije, v katerih izbiramo samo med kandidati
z zaporednimi številkami j + 1, . . . , n: namreč če nam za i ∈ {1, . . . , n}
slučajna spremenljvka Xi pove relativni rang i-tega kandidata med pr-
vimi i kandidati, potem je (ker so vsi vrstni redi enako verjetni) porazde-
litev Xj+1, . . . , Xn, pogojno na X1, . . . , Xj , enaka brezpogojni porazdelitvi
Xj+1, . . . , Xn.
V posebnem vidimo, da sta Pj in Qj odvisna samo od j in n in gotovo
je Qj+1 ≤ Qj za j < n. Naj bo še S := {j ∈ {1, . . . , n} : Pj ≥ Qj}. Če je
j ∈ S in je j < n, potem je Qj ≤ Pj = j/n in zato toliko bolj Qj+1 ≤ Qj ≤
j/n < (j + 1)/n = Pj+1, torej j + 1 ∈ S. Sledi, da je S = {r, . . . , n} za neki
r ∈ {1, . . . , n + 1}. Primer, ko je r = n + 1, torej strategija ne-izbire sploh
kateregakoli kandidata, je očitno strogo suboptimalna (saj npr. že strategija
»izberi prvega kandidata« da strogo pozitivno verjetnost izbire najbolǰsega
kandidata).
Do sedaj smo torej identificirali relativno preprost enoparametričen ra-
zred {S(r) : r ∈ {1, . . . , n}} pravil ustavljanja, v katerem leži tudi (neko,
morda jih je več) optimalno pravilo. Pot naprej je jasna: določiti verjetnost,
označili jo bomo s Pnr , da zmagamo (tj. da izberemo najbolǰsega kandidata)
uporabljajoč pravilo S(r), in poiskati maksimum Pnr za r ∈ {1, . . . , n}.
4 Obzornik mat. fiz. 64 (2017) 1
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 5 — #5 i
i
i
i
i
i
Problem izbire najboljše tajnice
V ta namen naj bo r ∈ {1, . . . , n} in denimo, da zasledujemo strategijo
S(r). Očitno je Pn1 = P(prvi kandidat je najbolǰsi) = 1/n. Naj bo r > 1.
Dogodek, da zmagamo, razpade na disjunktno unijo dogodkov, da izberemo
i-tega kandidata po vrsti in da je ta najbolǰsi; seveda izbiramo samo kandi-
date z indeksi i ∈ {r, . . . , n}. Iz končne aditivnosti verjetnosti sledi
Pnr =
n∑
i=r
P(izberemo i-tega kandidata in ta je najbolǰsi).
Denimo, da je i-ti kandidat najbolǰsi za neki i ∈ {r, . . . , n}. Potem je, na
dogodku, da je i-ti kandidat najbolǰsi, to, da ga izberemo, istovetno s tem,
da noben izmed kandidatov z indeksi r, . . . , i − 1 ni bil izbran, tj. da je
najbolǰsi izmed prvih i−1 kandidatov med prvimi r−1 kandidati. Dobimo,
da je
Pnr =
n∑
i=r
P(i-ti kandidat je najbolǰsi in najbolǰsi izmed prvih
i− 1 kandidatov je med prvimi r − 1 kandidati)
=
n∑
i=r
P(najbolǰsi izmed prvih i− 1 kandidatov je med prvimi
r − 1 kandidati|i-ti kandidat je najbolǰsi)·
· P(i-ti kandidat je najbolǰsi)
=
n∑
i=r
r − 1
i− 1
· 1
n
=
r − 1
n
n∑
i=r
1
i− 1
=
r − 1
n
n−1∑
i=r−1
1
i
.
Torej je
Pnr =
{
r−1
n
∑n−1
i=r−1
1
i , za r ∈ {2, . . . , n}
1/n, za r = 1
.
Razǐsčimo odvisnost Pnr od r. Naj bo  ∈ {>,=}. Potem je za vse r ∈
{2, . . . , n− 1}:
Pnr+1  Pnr ⇔
r
n
n−1∑
i=r
1
i
 r − 1
n
n−1∑
i=r−1
1
i
⇔ (r − 1 + 1)
n−1∑
i=r
1
i

(
1 + (r − 1)
n−1∑
i=r
1
i
)
⇔
n−1∑
i=r
1
i
 1.
1–9 5
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 6 — #6 i
i
i
i
i
i
Matija Vidmar
Ekvivalenca Pnr+1 Pnr ⇔
∑n−1
i=r
1
i  1 velja tudi pri r = 1, saj je
1
n
∑n−1
i=1
1
i 
1
n ⇔
∑n−1
i=1
1
i 1. Če povzamemo: za vse r ∈ {1, . . . , n−1} velja P
n
r+1 > P
n
r ,
če in samo če je
∑n−1
i=r
1
i > 1, in velja P
n
r+1 = P
n
r , če in samo če je
∑n−1
i=r
1
i =
1.
Sedaj imamo, kot sledi. Za n = 2 sta optimalna r dva, 1 = r2 in 2,
verjetnost zmage je 1/2. Za n > 2 vsota
Sn,r :=
n−1∑
i=r
1
i
ni enaka 1 za noben r ∈ {1, . . . , n − 1} (segmenti harmonične vrste se ne
seštejejo v ena, razen prvega člena: glej [12, str. 157], [3]), strogo pada v r,
je strogo večja od 1 za r = 1 in je enaka 1n−1 (torej strogo manǰsa od 1) za
r = n− 1. Sledi, da je edini optimalen r enak
min
{
r ∈ {1, . . . , n− 1} :
n−1∑
i=r
1
i
< 1
}
=
min
{
r ∈ {1, . . . , n− 1} :
n−1∑
i=r
1
i
≤ 1
}
= rn.
0 5 10 15 20 25 30
2
4
6
8
10
12
Slika 1. Optimalen rn kot funkcija n: raste, vsakič največ za 1.
6 Obzornik mat. fiz. 64 (2017) 1
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 7 — #7 i
i
i
i
i
i
Problem izbire najboljše tajnice
Prvih nekaj vrednosti rn s pripadajočimi optimalnimi verjetnostmi P
n
rn =
Pn je zbranih v spodnji tabeli.
n 2 3 4 5 6 7 8 9 10
rn 1 2 2 3 3 3 4 4 4
Pn 0,500 0,500 0,458 0,433 0,428 0,414 0,410 0,406 0,399
Končno razǐsčimo nekaj lastnosti optimalne rešitve in tako zaključimo
dokaz trditve iz uvoda.
(A) Funkcija N≥2 3 n 7→ rn narašča z n, vsakič največ za 1 (tj. 0 ≤
rn+1− rn ≤ 1 za vse n ∈ N). To sledi neposredno iz definicije rn: vsota Sn,r
narašča v n in Sn+1,r+1 ≤ Sn,r.
(B) Funkcija N≥2 3 n 7→ Pn = Pnrn pada, strogo na N≥3. Naj bo n ∈ N
in označimo r := rn. Velja P2 = 1/2 = P3; preveriti moramo še, da je
Pn > Pn+1 za n ≥ 3. V slednjem primeru je r > 1. Iz (A): rn+1 = r
ali pa rn+1 = r + 1. Naj bo najprej rn+1 = r. Pokazati moramo, da je
r−1
n
∑n−1
i=r−1
1
i >
r−1
n+1
∑n
i=r−1
1
i , kar sledi iz
1
n
n−1∑
i=r−1
1
i
>
1
n + 1
(
n−1∑
i=r−1
1
i
+
1
n
)
⇐
n−1∑
i=r−1
1
i
> 1,
5 10 15 20 25 30
0.4
0.5
0.6
0.7
Slika 2. Optimalno razmerje rn/n kot funkcija n: konvergira k, in je strogo nad, e
−1
(horizontalna linija).
1–9 7
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 8 — #8 i
i
i
i
i
i
Matija Vidmar
in to je res po definiciji rn. Naj bo sedaj rn+1 = r + 1. Pokazati moramo,
da je r−1n
∑n−1
i=r−1
1
i >
r
n+1
∑n
i=r
1
i , kar sledi iz
r − 1
n
(
1
r − 1
+ Sn,r
)
>
r
n + 1
(
Sn,r +
1
n
)
⇐
(
1
n
− r
n (n + 1)
)
> Sn,r
(
r
n + 1
− r − 1
n
)
⇐ 1 > Sn,r,
in to je res po definiciji rn.
(C) Imamo: e−1 < rn/n
n→∞−→ e−1. Res, vsoto Sn,r =
∑n−1
i=r
1
i moremo
za r ∈ {1, . . . , n− 1} takole oceniti:
ln
(n
r
)
=
∫ n
r
dx
x
≤ Sn,r ≤
∫ n
r
dx
x− 1
= ln
(
n− 1
r − 1
)
,
kjer razumemo ln(a/0) = ∞ za a > 0. Ker po definiciji rn velja Sn,rn ≤ 1,
sledi iz zgornje ocene, da je ln
(
n
rn
)
≤ 1, torej n/e ≤ rn. Po drugi strani
za r := dn−1e + 1e (tu je za x ∈ R, dxe := min{k ∈ Z : k ≥ x}) velja
ln
(
n−1
r−1
)
≤ 1 in zato iz zgornje ocene (če je le r ≤ n−1) Sn,r ≤ 1, od koder,
spet po definiciji rn sledi rn, rn ≤ dn−1e +1e. Skratka, n/e ≤ rn ≤ d
n−1
e +1e
5 10 15 20 25 30
0.38
0.40
0.42
0.44
0.46
0.48
0.50
Slika 3. Optimalna verjetnost Pnrn kot funkcija n: strogo pada na N≥3 proti e
−1 (hori-
zontalna linija).
8 Obzornik mat. fiz. 64 (2017) 1
i
i
“Vidmar” — 2017/5/29 — 11:01 — page 9 — #9 i
i
i
i
i
i
Problem izbire najboljše tajnice
in želena konvergenca optimalnega razmerja rn/n sledi. Stroga neenakost
e−1 < rn/n velja preprosto zaradi iracionalnosti e.
(D) e−1 < Pn
n→∞−→ e−1. Konvergenca sledi iz (C), ker za n > 2 velja
Pnrn =
rn−1
n
∑n−1
i=rn−1
1
i in ker po definiciji rn velja
∑n−1
i=rn−1
1
i → 1 (saj
rn → ∞ po (C)), ko gre n → ∞. Da je e−1 < Pn, lahko potem ugotovimo
iz (B).
Rezultate si naposled predstavimo še grafično: glej slike 1, 2 in 3.
LITERATURA
[1] A. B. Aries in A. N. Shiryaev, Optimal stopping rules, Stochastic Modelling and
Applied Probability, Springer Berlin Heidelberg, 2007.
[2] J. N. Bearden, A new secretary problem with rank-based selection and cardinal payo-
ffs, Journal of Mathematical Psychology 50 (2006), 1, 58–59.
[3] H. Belbachir in A. Khelladi, On a sum involving powers of reciprocals of an arithme-
tical progression, Annales Mathematicae et Informaticae 34 (2007), 29–31.
[4] B. A. Berezovskiy in A. V. Gnedin, Problemi najbolǰse izbire (v ruščini), Akademia
Nauk USSR, 1984.
[5] P. Billingsley, Probability and measure, Wiley Series in Probability and Statistics,
Wiley, 2012.
[6] F. R. Bruss, Sum the odds to one and stop, The Annals of Probability 28 (2000), 3,
1384–1391.
[7] E. B. Dynkin, The optimum choice of the instant for stopping a Markov process,
Selected Papers of E. B. Dynkin with Commentary (A. A. Yushkevich, G. M. Se-
itz, in A. L. Onishchik, ur.), CWorks / American Mathematical Society, American
Mathematical Society, 2000.
[8] T. S. Ferguson, Who solved the secretary problem?, Statistical Science 4 (1989), 3,
282–289.
[9] P. R. Freeman, The secretary problem and its extensions: A review, International
Statistical review 51 (1983), 2, 189–206.
[10] J. P. Gilbert in F. Mosteller, Recognizing the maximum of a sequence, Journal of the
American Statistical Association 61 (1966), 313, 35–73.
[11] M. Hlynka in J. N. Sheahan, The secretary problem for a random walk, Stochastic
Processes and their Applications 28 (1988), 2, 317–325.
[12] P. Hoffman, The man who loved only numbers: The story of Paul Erdos and the
search for mathematical truth, Hyperion Books, 1998.
[13] J. S. Rose, A problem of optimal choice and assignment, Operations Research 30
(1982), 1, 172–181.
[14] D. A. Sardelis in T. M. Valahas, Decision making: A golden rule, The American
Mathematical Monthly 106 (1999), 3, 215–226.
[15] R. J. Vanderbei, The postdoc variant of the secretary problem, 2012, dostopno
na: www.princeton.edu/~rvdb/tex/PostdocProblem/PostdocProb.pdf, ogled: 5. 2.
2017.
1–9 9