Sekretāres problēma

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  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ā  ar nosacījumu, ka pirmos  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 - 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  kandidāti tiek noraidīti un tiek izvēlēts nākamais labākais kandidāts. Ja tiek meklēts pirmais kandidāts , kurš tiek apskatīts, varbūtību izvēlēties vislabāko kandidātu var pierakstīt kā:

Summa nav definēta pie , taču tādā gadījumā tiek izvēlēts pirmais kandidāts un varbūtība tam būt labākajam ir . Šo summu no  līdz  var aptuveni iegūt ar integrāli 

Apvienojot izteiksmes iegūst:

. Ja šo izteiksmi atvasina pēc  un pielīdzina nullei, var atrast funkcijas pagrieziena punktu, kas atbilst maksimālajai varbūtībai.

, šai izteiksmei pie lieliem  kā atrisinājums der . Līdz ar to atraidot pirmos  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  varbūtības formulā:

, , kas ir vienāds ar , ja  ir liels. Šīs atbilst 37.8... % varbūtībai.

 Kardinālās izmaksas versija 
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  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 . 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:

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

Katra  kandidāta gaidāmā vērtība, kad tas ir vislabākais līdz šim ir: . Savukārt varbūtība, ka  kandidāts ir līdz šim labākais ir: , kas atbilst varbūtībai kandidātam  būt labākam par gaidāmo maksimālo starp pirmajiem  kandidātiem. Tiek meklēts tāds pieturas punkts , kur gaidāmās vērtības funkcija  ir maksimālā. Izrakstot pirmos locekļus šai vērtības funkcijai iegūst:

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

.

Šo var apstrādāt sekojoši:  apzīmē garo rindu ar varbūtību netikt izvēlētam iepriekšējiem gadījumam. Šo izrakstot kādam gadījumam  iegūst: . Aizvietojot šīs lielās reizinājuma zīmes ar iznākumu un izrakstot  konstanti ārpus summas iegūst:

Tālāk var apstrādāt summu: , izrakstot šīs summas pirmos un pēdējos locekļus:

. Ievietojot izteiksmē iegūst:

. Tā kā mums interesē pie kura pieturas punkta  šī funkcija ir maksimāla, jāatvasina un jāpielīdzina funkcija nullei:

 un , kas nozīmē pirmā kvadrātsakne no  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: , kas ir skaitliskā vērtība izvēlētajam kandidātam.

 Atsauces 

Kategorija:Lietišķā matemātika
Kategorija:Varbūtību teorija