Sekretāres problēma

Grafiks ar varbūtībām izvēliēties labāko kandidātu(sarkanie aplīši) un pirmais kandidāts kuru automātiski nenoraida $k$ (zilie krustiņi).

Sekretāres problēma demostrē scenāriju optimālās stāšanas teorijā, kuru pēta lietišķā matemātikā, statistikā un varbūtību teorijā. Alternatīvi nosaukumi ir laulības problēma, sultāna pūra problēma, gogoļa spēle vai labākās izvēles problēma. Problēmas atrisinājumu dēvē par 37% likumu.

Problēmas scenārijs ir šāds: administrators vēlas pieņemt darbā vienu sekretēri no $n$ kandidātiem, katra ar savu "labumu" vērtību. Kandidātes intervē pa vienai nejaušā secībā. Uzreiz pēc intervijas ir jāizlemj vai kandidāti pieņemt vai neņemt darbā. Līdz ko kandidāti noraida, pie šī kandidāta nevar atgriezties. Interviju procesā intervētājs uzzin par līdzšinējo kandidātu "labumu" vērtības, bet nezin neko par turpmākajiem kandidātiem. Sekretāras problēmas mērķis ir maksimizēt iespējas izvēlēties vislabāko sekretāri. Ja būtu iespējams atgriezties pie noraidītajiem kandidātiem, optimālā stratēģija būtu novērot visus kandidātus un pieņemt darbā vislabāko. Sarežģītība uzdevumā nāk no tā, ka izvēle jāveic tūlīt pec intervijas.

Problēmas risinājums paredz uzvaras varbūtību ne mazāku kā ${\frac {1}{e}}$ ar nosacījumu, ka pirmos ${\frac {n}{e}}$ kandidātus intervē un noraida, pēc kuriem izvēlas nākamo labāko. Pārsteidzošas sekas no rezultāta, ka šim risinājumam ir vienalga par kandidātu skatitu $n$- simts vai miljons, varbūtība vēljoprojām ir ~37% izvēlēties labāko kandidātu.

Risinājums

Problēmas risinājums meklē kādu pieturas kandidātu, līdz kuram ievākt datus par kandidātu labumu tos noraidot, tad izvēlēties nākamo labāko. Pie šiem nosacījumiem pirmie $k-1$ kandidāti tiek noraidīti un tiek izvēlēts nākamais labākais kandidāts. Ja tiek meklēts pirmai kandidātu $k$, kurš tiek apskatīts, varbūtību izvēlēties vislabāko kandidātu var pierakstīt kā:

${\begin{aligned}P(k)&=\sum _{i=1}^{n}P\left({\text{kandidātu }}i\ {\text{izvēlas}}\cap {\text{kandidāts }}i{\text{ ir labākais}}\right)\\&=\sum _{i=1}^{n}P\left({\text{kandidātu }}i{\text{ izvēlas}}|{\text{kandidāts }}i{\text{ ir labākais}}\right)\cdot P\left({\text{kandidāts }}i{\text{ ir labākais}}\right)\\&=\left[\sum _{i=1}^{k-1}0+\sum _{i=k}^{n}P\left(\left.{\begin{array}{l}{\text{labākais no pirmajiem }}i-1{\text{ kandidātiem}}\\{\text{ir starp pirmajiem }}k-1{\text{ kandidātiem}}\end{array}}\right|{\text{kandidāts }}i{\text{ ir labākais}}\right)\right]\cdot {\frac {1}{n}}\\&=\left[\sum _{i=k}^{n}{\frac {k-1}{i-1}}\right]\cdot {\frac {1}{n}}\\&={\frac {k-1}{n}}\sum _{i=k}^{n}{\frac {1}{i-1}}.\end{aligned}}$

Summu var aizstāt ar integrāli, jo starp katriem diviem kandidātiem kārtas skaitlis pieaug par viens- to var inteprētēt kā reizinājumu ar 1, kas neietekmē laukumu. Līdz ar to funkcijas augstums aptuveni precīzi apraksta laukumu zem līknes. Jo k ir lielāks, jo no taisnstūriem iegūtais laukums ir precīzāks.

Summa nav definēta pie $k=1$, taču tādā gadījumā tiek izvēlēts pirmais kandidāts un varbūtība tam būt labākajam ir $P(k=1)={\frac {1}{n}}$. Šo summu no $k$ līdz $n$ var aptuveni iegūt ar integrāli $\int _{k}^{n}{\frac {1}{i-1}}di=\ln {n}-ln{k}=\ln {\frac {n}{k}}$

Apvienojot izteiksmes iegūst:

$P(k)={\frac {k-1}{n}}\cdot \ln {\frac {n}{k}}$. Ja šo izteksmi atvasina pēc $k$ un pielīdzina nullei, var atrast funkcijas pagrieziena punktu, kas atbilst maksimālajai varbūtībai.

${\frac {dP(k)}{dk}}={\frac {1}{n}}\cdot \ln {\frac {n}{k}}-{\frac {1}{n}}+{\frac {1}{nk}}=0$, šai izteiksmei pie lieliem $n$ kā atrisinājums der $k={\frac {n}{e}}$. Līdz ar to atraidot pirmos ${\frac {n}{e}}$ kandidātus un izvēloties nākamo labāko būs vislielākā varbūtība izvēlēties labāko. Lai uzzinātu pašu skaitlisko vērtību jāievieto $k={\frac {n}{e}}$ varbūtības formulā:

$P(k)={\frac {k-1}{n}}\cdot \ln {\frac {n}{k}}$, $P(k={\frac {n}{e}})={\frac {{\frac {n}{e}}-1}{n}}\cdot \ln {\frac {n}{\frac {n}{e}}}={\frac {1}{e}}-{\frac {1}{n}}$, kas ir vienāds ar ${\frac {1}{e}}$, ja $n$ ir liels. Šīs atbilst 37.8... % varbūtībai.