Keplerin naimahuolet – optimaalinen pysäyttäminen
Markku Halmetoja
Johannes Keplerille1 tuli tarve löytää uusi vaimo, kun hänen ensimmäinen vaimonsa Barbara Muehleck kuoli vuonna 1611 ([1]). Jotakin naisen asemasta 1600-luvun Euroopassa kertoo se, että Kepler saattoi ilman yleistä paheksuntaa kokeilla useaa eri puolisoehdokasta ennen ratkaisuun päätymistään. Luonnollisesti koeteltavat olivat hänen taloudessaan yksi kerrallaan. Itsenäisyyden ja oman tahdon osoittaminen oli naisille vaarallista, sillä sellaisista elkeistä saattoi helposti joutua syytteeseen noituudesta. Syyte johti useimmiten kidutuksen kautta kuolemaan. Mika Waltari kuvaa tätä teoksessaan Mikael Karvajalka [2]. Se ei ole heikkohermoisen luettavaa.
Kaikessa omituisuudessaan Keplerin menettely johtaa mielenkiintoiseen matemaattiseen ongelmaan: kun ehdokkaita koetellaan yksi kerrallaan eikä hylättyyn luultavasti voi jälkikäteen palata, niin milloin kannattaa lopettaa ja tyytyä käsillä olevaan ehdokkaaseen? Kepler ei voinut pohtia asiaa todennäköisyyslaskennan kannalta, sillä tämäntyyppisiä ongelmia ratkova päätöksentekoteoria ja optimaalisen pysäyttämisen teoria kehittyi vasta 1900-luvulla. Kepler-historiasta johtuen pysäyttämisongelmaa kutsutaan kirjallisuudessa usein avioliitto-ongelmaksi ja yleisesti myös sihteeriongelmaksi. Ennen me-too-aikaa julkaistussa teoksessa [3, s.15] kysymys on puettu tuskin toteutettavissa olevaksi kauneuskilpailuksi, jossa neidot saapuvat yksitellen tuomariston eteen. Se joko hylkää neitosen tai valitsee hänet kauneimmaksi loppuja näkemättä. Millaisella strategialla päätös tulisi tehdä, jotta joltisellakin todennäköisyydellä kaunein tulisi valituksi? Menettely tuntuu perin epäoikeudenmukaiselta. Esimerkki on kertakaikkisen huono.
Yritämme seuraavassa kehittää ongelmalle uskottavamman kehyskertomuksen. Oletetaan, että television visailuohjelman palkintona henkilö saa osallistua leikkiin, jossa hän saa valita numerojärjestyksessä tuntemattomia rahasummia sisältäviä kirjekuoria. Kuoret on numeroitu \(1\):stä \(n\):ään, missä \(n\) on vähintään kaksinumeroinen luku. Jokaisessa kuoressa on eri rahamäärä. Niiden suuruusluokasta osallistujalla ei ole tietoa. Hän valitsee ja avaa kuoria seuraavasti: avattuaan ensimmäisen kuoren hän joko hyväksyy siinä olevan rahamäärän palkinnokseen ja leikki päättyy tai hylkää sen ja ottaa käsittelyynsä seuraavan kuoren. Näin peli jatkuu, kunnes hän hyväksyy jonkin kuoren sisällön. Hylättyihin kuoriin ja rahasummiin ei ole paluuta. Jos hän päättää ennalta pysähtyä vaikkapa horoskooppimerkkinsä mukaisen onnennumeron kohdalle, hän saa suurimman summan todennäköisyydellä \(1/n\). Osoitamme seuraavassa, että parempikin strategia on olemassa.
Tutkitaan aluksi ensimmäiset \(a\) kuorta ja laitetaan muistiin niistä löytynyt suurin rahasumma. Tämän jälkeen avataan kuoria, kunnes löytyy suurempi summa kuin alussa muistiin laitettu. Tähän kuoreen ja summaan tyydytään ja peli päättyy. Jos muistissa olevaa summaa suurempaa ei löydy, kaikki kuoret tulevat avatuiksi ja viimeisen kuoren sisältöön on tyytyminen.
Lasketaan nyt todennäköisyys sille, että jaossa oleva suurin rahasumma löytyy kuoresta n:o \(x\) (\(> a\)). Jotta näin kävisi, täytyy seuraavien asioiden toteutua: \(1^{\circ}\) kuorien \(1, 2, \ldots, (x-1)\) suurin summa on jossakin kuorista \(1, 2, \ldots, a\), ja \(2^{\circ}\) suurin rahasumma todellakin on kuoressa n:o \(x\). Tapauksessa \(1^{\circ}\) suotuisia alkeistapauksia on \(a\) kappaletta ja alkeistapauksia kaikkiaan \(x-1\) kappaletta. Tapauksen \(2^{\circ}\) todennäköisyys on sama kuin jos horoskooppimenetelmää käytettäisiin. Täten
\[\mathrm{P}(1^{\circ}) = \frac{a}{x-1}\quad\mathrm{ja}\quad\mathrm{P}(2^{\circ}) = \frac{1}{n}.\]
Tieto kuorien \(1, 2, \ldots, (x-1)\) sisältöjen järjestyksestä ei vaikuta kuoren \(x\) sisältöön, joten tapaukset \(1^{\circ}\) ja \(2^{\circ}\) ovat toisistaan riippumattomat. Niinpä kertolaskusäännön mukaan todennäköisyys saada maksimivoitto pysähtymällä kuoreen n:o \(x\)
\[\mathrm{P}(1^{\circ} \wedge 2^{\circ}) = \frac{a}{x-1}\cdot\frac{1}{n}.\]
Tämä pätee erikseen jokaiselle \(a\):n jälkeiselle kuorelle, joten laskemalla yhteen kyseiset todennäköisyydet saadaan
\[\mathrm{P}(\mathrm{max}\,\mathrm{voitto}) = \frac{1}{n}\sum_{x=a+1}^{n}{\frac{a}{x-1}} = \frac{a}{n} \sum_{x=a}^{n-1}{\frac{1}{x}}.\]
Strategian loppuunsaattamiseksi tutkitaan vielä, millä \(a\):n arvolla saatu todennäköisyys on suurimmillaan. Merkitään
\[\mathrm{P}(\mathrm{max}\,\mathrm{voitto}) = f(a) = \frac{a}{n} \sum_{x=a}^{n-1}{\frac{1}{x}}.\]
Koska \(a\) on diskreetti muuttuja, derivaatasta ei näyttäisi olevan hyötyä. Vai onko sittenkin? Summa
\[\sum_{x=a}^{n-1}{\frac{1}{x}}\]
on likimäärin jakoväliä \(\Delta x = 1\) käyttäen puolisuunnikassäännöllä laskettu integraalin
\[\int_{a}^{n}{\frac{1}{x}}\, \mathrm{d}x\]
likiarvo. Siis
\[f(a) \approx \frac{a}{n} \int_{a}^{n}{\frac{1}{x}} \, \mathrm{d}x = \frac{a}{n} \ln{\frac{n}{a}}.\]
Suurin arvo saavutetaan, kun \(a\approx n/\mathrm{e}\approx 0{,}368 n\), ja se toteutuu todennäköisyydellä \(1/\mathrm{e}\approx 0{,}368\). Päävoiton todennäköisyys on siis huomattavasti suurempi kuin jos pelkällä onnennumerolla yritettäisiin. Esitetty strategia on puhdasta arvausta parempi, mutta tämän kirjoittajalla ei ole edellytyksiä pohtia ja ratkaista, onko se paras mahdollinen.
Optimaalisen pysäyttämisen teoria sai alkunsa 1940-luvulla USAssa, kun kehitettiin tilastollisia testejä, missä otannan koko ei ole kiinteä vaan aina kun tehdään uusi havainto, päätetään hyväksytäänkö tilastollinen hypoteesi tai hylätäänkö se tai jatketaanko havainnointia. Tärkeä sovellusalue on myös optioiden hinnoittelu finanssi- ja talousmatematiikassa. Tämän aihepiirin tutkijat Robert C. Merton ([4]) ja Myron Scholes ([5]) saivat taloustieteen Nobelin palkinnon vuonna 1997. Monet pysäytysteorian yleistykset ovat edelleen aktiivisen tutkimuksen kohteina.
Keplerin ongelma ei ollut aivan tarkkaan tässä käsitelty, sillä hän ei esimerkiksi voinut aloittaessaan tietää, montako naista hän onnistuu saamaan koeajalle. Hän poikkesi ratkaisusta sikälikin, että yritettyään kahden vuoden aikana yhteiselämää yhdentoista naisen kanssa hän onnistui luomaan uudestaan suhteen Susanna Reuttingeriin, jonka hän oli hylännyt viidentenä ehdokkaana. He solmivat avioliiton ja elivät onnellisina elämänsä loppuun asti.
Kiitokset emer. prof. Paavo Salmiselle muutamista kirjoitustani täsmentäneistä kommenteista.
Viitteet
[1] https://en.wikipedia.org/wiki/Johannes_Kepler
[2] Mika Waltari: Mikael Karvajalka, WSOY 1948.
[3] H. Stark, J.W. Woods: Probability, Random Processes, and Estimation Theory for Engineers, 2. edition, Prentice-Hall 1994.
Alaviitteet
Johannes Kepler (1571–1630), saksalainen astronomi ja matemaatikko.↩︎