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 uzzina par līdzšinējo kandidātu "labumu" vērtības, bet nezina neko par turpmākajiem kandidātiem. Sekretāres 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ā veidojas tādēļ, ka izvēle jāveic tūlīt pēc 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 skatītu $n$- simts vai miljons, varbūtība vēl joprojā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 pirmais kandidāts $k$, kurš tiek apskatīts, varbūtību izvēlēties vislabāko kandidātu var pierakstīt kā:

$\begin{array}{cc}P(k)& =\sum _{i=1}^{n}P(\text{kandidātu }i\text{izvēlas}\cap \text{kandidāts }i\text{ ir labākais})\\ & =\sum _{i=1}^{n}P(\text{kandidātu }i\text{ izvēlas}|\text{kandidāts }i\text{ ir labākais})\cdot P\left(\text{kandidāts }i\text{ ir labākais}\right)\\ & =[\sum _{i=1}^{k-1}0+\sum _{i=k}^{n}P\left(\begin{array}{c}\text{labākais no pirmajiem }i-1\text{ kandidātiem}\\ \text{ir starp pirmajiem }k-1\text{ kandidātiem}\end{array}|\text{kandidāts }i\text{ ir labākais}\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{array}$

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 $\underset{k}{\overset{n}{\int }}\frac{1}{i-1}di=\ln n-lnk=\ln \frac{n}{k}$

Apvienojot izteiksmes iegūst:

$P(k)=\frac{k-1}{n}\cdot \ln \frac{n}{k}$. Ja šo izteiksmi 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.

Kardinālās izmaksas versija

Ilustrācija gaidāmajai vērtībām katram kandidātam, ja ir dota tā relatīvā pozīcija.

Iespējams atrast vislabāko kandidātu ir pārāk strikts nosacījums. Viegli iztēloties, ka intervētājs redz pievienoto vērtību pieņemt vairāk vērtīgu kandidātu nekā mazāk vērtīgu kandidātu, neobligāti izvēloties labāko.

Lai modelētu šādu problēmas versiju, pieņemsim $n$ kandidātiem piemīt "patiesās" novērotās vērtības, kas ir gadījuma lielumi vienādi un neatkarīgi izvēlēti no vienveidīga sadalījuma $[0;1]$. Līdzīgi kā sekretāres problēmā, intervētājs novēro tikai vai kandidāts ir labākais līdz šim, neiegūstot informāciju par līdzšinējo labumu. Intervētājam kandidāts uzreiz pēc intervijas uzreiz ir jāakceptē vai jānoraida. Ja neviens kandidāts netiek izvēlēts, jāizvēlas pēdējais.

Tālāk gaidāmo vērtību kā funkciju katram apstāšanās punktam var pierakstīt kā iteratīvu procesu:

$V_n(t)=E(X_t|I_t=1)\cdot P(I_t=1)+V_n(t+1)$

Šo formulu var interpretēt, ka katram skaitlim $t$, kur pirmos $t-1$ kandidātus uzreiz noraida, iegūt gaidāmo vērtību nākamajam labākajam vai pēdējam kandidātam. Kad rēķina $V_n(t+1)$ jāņem vērā varbūtība, piemēram, kandidātam $t$ tikt izvēlētam, tādēļ tiek reizināts ar varbūtību, ka $t$ kandidātu neizvēlas.

Katra $t$ kandidāta gaidāmā vērtība, kad tas ir vislabākais līdz šim ir: $E_t=E(X_t|I_t=1)=\frac{t}{t+1}$. Savukārt varbūtība, ka $t$ kandidāts ir līdz šim labākais ir: $P(I_t=1)=1-\frac{t-1}{t}=\frac{1}{t}$, kas atbilst varbūtībai kandidātam $t$ būt labākam par gaidāmo maksimālo starp pirmajiem $t-1$ kandidātiem. Tiek meklēts tāds pieturas punkts $c$, kur gaidāmās vērtības funkcija $V_n(c)$ ir maksimālā. Izrakstot pirmos locekļus šai vērtības funkcijai iegūst:

$V_n(t)=\frac{t}{t+1}\cdot \frac{1}{t}+\frac{t+1}{t+2}\cdot \frac{1}{t+1}\cdot (1-\frac{1}{t})+\frac{t+2}{t+3}\cdot \frac{1}{t+2}\cdot (1-\frac{1}{t})\cdot (1-\frac{1}{t+1})+\frac{t+3}{t+4}\cdot \frac{1}{t+3}\cdot (1-\frac{1}{t})\cdot (1-\frac{1}{t+1})\cdot (1-\frac{1}{t+2})...$

$=\frac{1}{t+1}+\frac{1}{t+2}\cdot \frac{t-1}{t}+\frac{1}{t+3}\cdot \frac{t-1}{t}\cdot \frac{t}{t+1}+\frac{1}{t+4}\cdot \frac{t-1}{t}\cdot \frac{t}{t+1}\cdot \frac{t+1}{t+2}...$

Šo garo izteiksmi var pierakstīt kodolīgāk un apskatīt tās daļas atsevišķi:

$V_n(c)=\sum _{t=c}^{n-1}\left[\prod _{s=c}^{t-1}\left(\frac{s-1}{s}\right)\right]\left(\frac{1}{t+1}\right)+\left[\prod _{s=c}^{n-1}\left(\frac{s-1}{s}\right)\right]\frac{1}{2}$.

Šo var apstrādāt sekojoši: $\prod _{s=c}^{t-1}\left(\frac{s-1}{s}\right)$ apzīmē garo rindu ar varbūtību netikt izvēlētam iepriekšējiem gadījumam. Šo izrakstot kādam gadījumam $t$ iegūst: $\prod _{s=c}^{t-1}\left(\frac{s-1}{s}\right)=\frac{c-1}{c}\cdot \frac{c}{c+1}\cdot \frac{c+1}{c+2}\cdot ...\cdot \frac{t-3}{t-2}\cdot \frac{t-2}{t-1}=\frac{c-1}{t-1}$. Aizvietojot šīs lielās reizinājuma zīmes ar iznākumu un izrakstot $c-1$ konstanti ārpus summas iegūst:

$V_n(c)=(c-1)\sum _{t=c}^{n-1}(\frac{1}{t-1}\cdot \frac{1}{t+1})+\frac{c-1}{n-1}\cdot \frac{1}{2}$

Tālāk var apstrādāt summu: $\sum _{t=c}^{n-1}(\frac{1}{t-1}\cdot \frac{1}{t+1})=\frac{1}{2}\cdot \sum _{t=c}^{n-1}(\frac{1}{t-1}-\frac{1}{t+1})$, izrakstot šīs summas pirmos un pēdējos locekļus:

$\frac{1}{2}\cdot \sum _{t=c}^{n-1}(\frac{1}{t-1}-\frac{1}{t+1})=\frac{1}{c-1}-\frac{1}{c+1}+\frac{1}{c}-\frac{1}{c+2}+\frac{1}{c+1}-\frac{1}{c+3}+...+\frac{1}{n-4}-\frac{1}{n-2}+\frac{1}{n-3}-\frac{1}{n-1}+\frac{1}{n-2}-\frac{1}{n}$

$\frac{1}{2}\cdot \sum _{t=c}^{n-1}(\frac{1}{t-1}-\frac{1}{t+1})=\frac{1}{2}\cdot (\frac{1}{c-1}-\frac{1}{c+1}+\frac{1}{c}-\frac{1}{c+2}+\frac{1}{c+1}-\frac{1}{c+3}+...+\frac{1}{n-4}-\frac{1}{n-2}+\frac{1}{n-3}-\frac{1}{n-1}+\frac{1}{n-2}-\frac{1}{n})$

$=\frac{1}{2}\cdot (\frac{1}{c-1}+\frac{1}{c}-\frac{1}{n-1}-\frac{1}{n})$. Ievietojot izteiksmē iegūst:

$V_n(c)=(c-1)\cdot \frac{1}{2}(\frac{1}{c-1}+\frac{1}{c}-\frac{1}{n-1}-\frac{1}{n})+\frac{c-1}{n-1}\cdot \frac{1}{2}=\frac{2cn-c^2+c-n}{2cn}$. Tā kā mums interesē pie kura pieturas punkta $c$ šī funkcija ir maksimāla, jāatvasina un jāpielīdzina funkcija nullei:

$\frac{\delta V_n(c)}{\delta c}=\frac{1}{2c^2}-\frac{1}{2n}=0$ un $c=\sqrt{n}$, kas nozīmē pirmā kvadrātsakne no $n$ kandidātiem ir jānoraida un jāizvēlas nākamais labākais, lai sagaidāmās funkcijas vērtība būtu maksimāla. Ievietojot šo vērtību sagaidāmās vērtības funkcijā iegūst: $V_n(c=\sqrt{n})=\frac{2n\sqrt{n}-n+\sqrt{n}-n}{2n\sqrt{n}}=1-\frac{1}{\sqrt{n}}+\frac{1}{2n}$, kas ir skaitliskā vērtība izvēlētajam kandidātam.