37% reegel

Kandidaadid saabuvad ükshaaval juhuslikus järjekorras. Igaüht saab võrrelda üksnes nendega, keda oled juba näinud. Otsus tuleb teha kohapeal ja kedagi tagasi kutsuda ei saa. Vali, mitu kandidaati kohe tagasi lükata; reegel valib seejärel esimese, kes on seninähtutest parem.

Parima tõenäosus, lükates tagasi k	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Parim lävend suure n korral	$k^*\approx\frac{n}{e}$
Selle tõenäosus	$P(k^*)\to\frac{1}{e}\approx0.3679$

Näidisarvutus — 37% reegel

Parima tõenäosus, lükates tagasi 4	39,84%
Parim lävend k*	4
Parima tõenäosus lävendi k* korral	39,84%
n/e, võrdluseks	4,05
Parima tõenäosus juhuslikul valikul	9,09%
Tõenäosus, et parim lükati tagasi	36,36%
Tõenäosus, et jõutakse viimase kandidaadini	40%
Väikseim saavutatav oodatav järk	2,6136

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — 37% reegel

Klassikalises sekretäriülesandes saabub n kandidaati juhuslikus järjekorras. Igaüht saab võrrelda üksnes seninähtutega ning otsus ta vastu võtta või lõplikult tagasi lükata tuleb teha kohapeal. Lävendireegel jätab esimesed k kandidaati kõrvale ja võtab seejärel vastu esimese, kes osutub neist kõigist paremaks.

Kust valem tuleb

Jaota juhtumid parima asukoha järgi. Tähistagu B parima kandidaadi saabumisjärjekorda ja W sündmust, et otsing lõpeb parima valimisega. B võib võrdse tõenäosusega olla mistahes väärtus vahemikus 1 kuni n.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
Esimese k seas asuv parim on kaotatud. Reegel ei vaata kunagi tagasi, mistõttu need positsioonid edule kaasa ei aita.
$B\le k:\quad P(W\mid B)=0$
Positsioonil i > k asuva parimani jõutakse vaid siis, kui kedagi vahemikus k + 1 kuni i − 1 pole valitud. See juhtub täpselt siis, kui esimese i − 1 kandidaadi parim asub esimese k sees, sest vaid sel juhul ei ületa keegi vahepealsetest senist latti. Igaüks neist i − 1 kandidaadist on parim võrdse tõenäosusega.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Liida tõenäosused üle kõigi positsioonide.
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Vaatle piirprotsessi, kui n kasvab. Suhtega x = k/n saab summast integraal ning tõenäosuseks kujuneb −x ln x. Selle tuletis −ln x − 1 võrdub nulliga punktis x = 1/e, kus tõenäosus on 1/e ≈ 36,79%.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Eeldab: Näha on üksnes suhteline pingerida, mitte tegelikud tulemused; saabumisjärjekord on ühtlaselt juhuslik; tagasilükatud kandidaati ei saa tagasi kutsuda ning heakskiidu saanu on alati nõus; iga tulemus peale absoluutselt parima loetakse kaotuseks.

Ülesanded täielikult lahendatud

Kolm kandidaati, kõik järjestused kirjas 3 sammu
Juhuslikus järjekorras saabub kolm kandidaati. Pane iga järjestus kirja saabumisjärjekorras asuvate kohtadena (1 = parim). Kui lükkad esimese tagasi ja valid seejärel esimese, kes edestab kõiki seniseid, siis mitmel juhul kuuest võimalikust järjestusest saad parima? Kontrolli vastust valemiga.

Ava see ülesanne tööriistas
1. Kuus võimalikku järjestust:
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. Esimene kandidaat seab võrdlusaluse. Järjestustes 213 ja 231 edestab parim kandidaati 2; järjestuses 312 saabub 1 teisena ja valitakse kohe ära. Järjestustes 123 ja 132 ei ületa keegi tagasilükatud 1, mistõttu lepitakse viimasega; järjestuses 321 edestab 2 eelnevat 3 ja valitakse enne, kui 1 pärale jõuab:
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. Valem väärtustega n = 3 ja k = 1:
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Vastus

3 järjestust 6-st, tõenäosusega 1/2 esimese kandidaadi valimise 1/3 vastu.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Neli kandidaati, kõik lävendid 2 sammu
Leia nelja kandidaadi korral parima leidmise tõenäosus iga lävendi k = 0, 1, 2, 3 puhul ning määra parim lävend.

Ava see ülesanne tööriistas
Näita lahendust
1. k = 0 valib esimese kandidaadi, kes on parim tõenäosusega 1/4. Kui k ≥ 1, kasuta valemit:
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Võrdle nelja võimalust:
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Vastus

Lükka üks tagasi ja vali esimene, kes teda edestab: 11/24 ≈ 45,83%.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
Kepleri üksteist 3 sammu
Aastal 1611 asus Johannes Kepler valima endale teist naist ning kaalus peaaegu kahe aasta vältel ühtteist kandidaati. Milline lävend on lävendireegli ja n = 11 korral parim, milline on selle tõenäosus ning kes on esimene kandidaat, kelle reegel võib valida?

Ava see ülesanne tööriistas
Näita lahendust
1. Arvuta valemi väärtused suhte n/e = 11/e ≈ 4,05 ümbruses:
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. k = 4 annab suurima väärtuse; nii k = 3 kui ka k = 5 annavad väiksema tulemuse:
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. Nelja tagasilükkamisel on viies kandidaat esimene, kelle reegel võib heaks kiita. Kepler abielluski viiendaga, kuid mitte selle reegli järgi: Fergusoni ülevaates Kepleri kirjast veendi teda pärast viiendaga kohtumist tegema abieluettepanek hoopis neljandale, saama korvi ning pöörduma tagasi. Reegel aga tagasipöördumist ei luba.
Vastus

Lükka neli tagasi, tõenäosus 39,84%; viies on esimene kandidaat, kelle reegel saab valida.

$k^*=4,\qquad P(4)\approx0.3984$
Palju kandidaate: kust tuleb 1/e 3 sammu
Kirjuta suure n korral tagasilükatute osakaal kujul x = k/n ning leia parim x ja selle antav tõenäosus. Seejärel kontrolli tulemust väärtusel n = 100.

Ava see ülesanne tööriistas
Näita lahendust
1. Tegemist on funktsiooni 1/t Riemanni summaga lõigul [x, 1]:
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Võrdsusta tuletis nulliga:
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. Kui n = 100, on n/e ≈ 36,79 ja täpne parim lävend 37:
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Vastus

Lükka tagasi osa 1/e ≈ 36,79%; tõenäosus läheneb väärtusele 1/e. Kui n = 100, on parim lävend 37 ja tõenäosus 37,1%.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Viimase kandidaadi hooleks 3 sammu
Sada kandidaati, esimesed 37 lükatakse tagasi. Leia tõenäosus, et parim on tagasilükatute seas, tõenäosus, et otsing jõuab viimase kandidaadini, ning tõenäosus, et viimane kandidaat ongi seejärel parim.

Ava see ülesanne tööriistas
Näita lahendust
1. Kuna parim võib asuda võrdse tõenäosusega mistahes kohal, satub ta esimese 37 sekka tõenäosusega:
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. Otsing jõuab kandidaadini number 100 täpselt siis, kui kedagi vahemikus 38 kuni 99 ei valita – teisisõnu, kui esimese 99 parim asub esimese 37 seas:
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. Vahe annab juhu, kus otsing jõuab lõpuni ja viimane kandidaat ongi parim:
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Vastus

37%, 37,37% ja 0,37%: enam kui üks otsing kolmest lõpeb viimase kandidaadiga, ja peaaegu mitte kunagi seetõttu, et viimane olnuks parim.

$0.37,\qquad 0.3737,\qquad 0.0037$
Vähim oodatav järk kolme kandidaadi korral 3 sammu
Kolm kandidaati, kusjuures eesmärk pole enam tingimata ainsa parima tabamine, vaid vähim oodatav järk (1 = parim). Leia tagasisuunalise induktsiooniga optimaalne reegel ja selle oodatav järk.

Ava see ülesanne tööriistas
Näita lahendust
1. i-ndana kohatud kandidaadil, kelle koht seninähtute seas on j, on oodatav üldine järk j(n + 1)/(i + 1). Kolmas kandidaat tuleb paratamatult vastu võtta ja tema oodatav järk on (n + 1)/2:
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. Teise kandidaadi juures võta ta vastu, kui tema oodatav järk pole suurem kui 2; vastasel juhul liigu edasi:
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. Esimese kandidaadi vastuvõtmine annab 2, mis on rohkem kui 5/3, mistõttu tuleb edasi liikuda:
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Vastus

Jäta esimene vahele, võta teine, kui ta edestab esimest, muidu lepi kolmandaga: oodatav järk 5/3 ≈ 1,67. Kolme kandidaadi korral on see täpselt lävendireegel väärtusega k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Kaks kandidaati, teadaolevad skoorid 2 sammu
Kahe kandidaadi tulemused on valitud sõltumatult ja ühtlaselt vahemikust 0 kuni 1 ning sa näed iga tulemust tema saabumisel. Leia strateegia, mis tagab kõige sagedamini kõrgema tulemusega kandidaadi, ja selle tõenäosus. Võrdle seda pelgalt järjestuse teadmisega.

Ava see ülesanne tööriistas
Näita lahendust
1. Kui jätad esimese kandidaadi (tulemusega x) vahele, pead võtma teise, kes võidab siis, kui tema tulemus on suurem: tõenäosus 1 − x. Kui võtad esimese, võidab ta siis, kui teise tulemus on väiksem: tõenäosus x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. Seega vali esimene, kui x ≥ 1/2. Võta keskmine üle x:
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Vastus

Vali esimene kandidaat, kui tema tulemus on vähemalt 1/2: tõenäosus 3/4. Pelgalt järjestuse põhjal on tõenäosus kahe kandidaadi korral alati 1/2, tee mida tahes.

$P=\frac{3}{4}>\frac{1}{2}$

Lisaülesanded, ainult vastustega

Leia viie kandidaadi korral parim lävend ja selle tõenäosus.

Näita vastust

Lükka kaks tagasi: 13/30 ≈ 43,33%.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
Näita, et kahe kandidaadi ja pelgalt järjestuse teadmise korral tagab iga reegel parima poolel juhtudest.

Näita vastust

Esimese valimine võidab tõenäosusega 1/2; tema vahelejätmine tähendab teise valimist, samuti 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
Leia kümne kandidaadi ja parima lävendi korral tõenäosus, et parim on tagasilükatute seas, ning tõenäosus, et otsing jõuab viimase kandidaadini.

Näita vastust

k = 3: 30% ja 3/9 ≈ 33,33%.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
Leia suure n piirväärtuses parima leidmise tõenäosus, kui tagasi lükatakse viiendik kandidaatidest ning kui kolm viiendikku.

Näita vastust

−0,2 ln 0,2 ≈ 32,19% ja −0,6 ln 0,6 ≈ 30,65%.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
Leia nelja kandidaadi puhul vähim oodatav järk, mida ükski reegel suudab saavutada.

Näita vastust

15/8 = 1,875.

$c_0=\frac{15}{8}=1.875$

Lükka tagasi veerand või pool: tõenäosus on sama

Kõvera hari on lame, ja just see teebki reegli praktikas kasutatavaks. Vajuta Veerand tagasi lükatud: 35,04%. Vajuta Pool tagasi lükatud: 34,91%. Saja kandidaadi parim lävend 37 annab 37,1%, seega mistahes valik veerandi ja poole vahel läheb maksma kõige rohkem 2,2 protsendipunkti. Kui n kasvab, läheneb kõver kujule −x ln x, kus x on tagasilükatute osakaal. Veerandi ja poole peal on funktsiooni väärtus täpselt sama, sest ¼ ln 4 = ½ ln 2 ≈ 34,66%. Sa ei pea seega n-i kuigi täpselt teadma: eksi oma hinnanguga kolmandik siia või sinna ja lükka 37% sellest tagasi, ikka säilib suure n korral vähemalt 34,5% tõenäosus.

Sihid vaid parimat, kuid enam kui kolmandikul kordadest pead leppima viimasega

See reegel panustab kõik ainsa parima leidmisele. Kui parim satub tagasilükatute sekka (saja kandidaadi puhul tervelt 37% kordadest), ei suuda keegi hilisematest latti ületada, otsing jõuab lõpuni ja lepib paratamatult viimase tulijaga. Vajuta Sada, 37 tagasi lükatud: valitud kandidaadi oodatav järk on 20,01. Aastal 1964 otsisid Chow, Moriguti, Robbins ja Samuels hoopis reeglit, mis tagaks võimalikult hea keskmise tulemuse. Nende strateegia valib kandidaadi, kes on seninähtute seas esirinnas, kusjuures nõudmised leebuvad nimekirja lõpu lähenedes. Tulemuseks on oodatav järk 3,60, kui n = 100. Nende reegli oodatav järk püsib alla 4 iga sellel lehel pakutava n korral ja läheneb arvule 3,8695; 37% reegli oodatav järk seevastu halveneb koos n-iga pidurdamatult, ulatudes tuhande kandidaadi juures juba 185,54-ni.

Kui skoorid on teada, tõuseb tõenäosus 58%-ni

37% reegel arvestab vaid järjestust: kes keda edestab. Oletame aga, et näed iga kandidaadi tegelikku skoori ja tead tulemuste jaotust, näiteks ühtlast jaotust 0 ja 1 vahel. Gilbert ja Mosteller lahendasid selle variandi 1966. aastal ning seal esialgne pelgalt vaatlemise etapp kaob. Esimesest kandidaadist alates võid valida igaühe, kes on senistest parim ja ületab teatud lävendi, kusjuures lävend langeb sedamööda, kuidas valikuvõimalused otsa saavad: 0,5, kui tulemata on veel üks kandidaat; 0,6899 kahe ning 0,9240 kümne puhul. Parima leidmise tõenäosus on 11 kandidaadi korral 60,6% ja 100 puhul 58,29% ning see koondub väärtusele 58,02%, samas kui pelk pingerida annab vaid 36,79%. Teadmine, milline näeb välja hea tulemus, on seega väärt umbes 21 protsendipunkti.

Õpitee

Valik nähtu põhjal

Allikad (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

7 Raven Roomi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.

37% reegel

Kust valem tuleb

Lisaülesanded, ainult vastustega

Lükka tagasi veerand või pool: tõenäosus on sama 🖖

Sihid vaid parimat, kuid enam kui kolmandikul kordadest pead leppima viimasega 🖖

Kui skoorid on teada, tõuseb tõenäosus 58%-ni 🖖

Lükka tagasi veerand või pool: tõenäosus on sama

Sihid vaid parimat, kuid enam kui kolmandikul kordadest pead leppima viimasega

Kui skoorid on teada, tõuseb tõenäosus 58%-ni