Rahapeliongelma
Jukka Liukkonen
Mat. yo. evp.
Pythonin kanssa peliongelman kimppuun
Professori Daniel Litt tutkii leipätyönään algebrallista geometriaa Toronton yliopistossa. Hän kertoo löytäneensä hyödyllisiä välineitä toiselta matematiikan osa-alueelta, lukuteoriasta. Vapaa-aikaansa Litt viettää kolmannen matematiikan osa-alueen, todennäköisyyslaskennan parissa. Hän keksii huvikseen todennäköisyysprobleemoita, jotka johtavat ihmisen intuition helposti harhaan. Tässä on yksi Littin probleemoista:
Kolikkoa heitetään sata kertaa. Alice saa pisteen aina, kun kaksi kruunaa tulee peräkkäin. Bob saa pisteen aina, kun kruunaa seuraa klaava. Eniten pisteitä kerännyt pelaaja voittaa pelin. Kumpi on todennäköisempi voittaja?
Siis hetkinen: kaikki neljä mahdollista kruunan ja klaavan järjestettyä paria ovat yhtä todennäköisiä, joten Alice ja Bob saavat sadan heittokerran pelissä kumpikin keskimäärin saman määrän pisteitä, ja tuo määrä on \(99/4=24{,}75\), sillä sadan kolikon jonossa on vain \(99\) kolikkoväliä ja saman verran kahden peräkkäisen kolikon muodostamia pareja. Tällöinhän Alice on yhtä todennäköinen voittaja kuin Bob? Varmistetaanpa asia kirjoittamalla pieni kolikonheittoa simuloiva Python-ohjelma.
No, Python-ohjelma kirjoitettiin, mutta siinä vaikutti olevan jokin bugi, sillä onnetar suosi säännöllisesti Bobia, jolla voiton todennäköisyys oli aina kolmisen prosenttiyksikköä suurempi kuin Alicella. Bugia ei sitkeistä etsinnöistä huolimatta löydetty. Heräsi epäilys, että vika on jossain muualla, esimerkiksi aritmeettis-loogisessa yksikössä otsaluun takana. Hoksattiin tutkia miten käy, jos heittosarja on paljon lyhyempi, vaikkapa neljä heittoa? Oheisesta puukaaviosta, jossa \({\rm H}\) tarkoittaa kruunaa (heads) ja \({\rm T}\) tarkoittaa klaavaa (tails), nähdään huolellisesti katsomalla, että neljän kolikonheiton tapauksessa kaikista mahdollisista 16 pelistä Alice voittaa neljä ja Bob kuusi. Jäljelle jäävät kuusi ovat tasapelejä. Python-ohjelma taisi olla kunnossa alun alkaenkin.
Peli ja peliavaruus
Kolikonheiton tulosjonoa mallinnetaan yhtä pitkällä kirjainten \({\rm H}\) ja \({\rm T}\) muodostamalla jonolla. Alice saa pisteen jokaisesta \({\rm H}{\rm H}\) -esiintymästä ja Bob jokaisesta \({\rm H}{\rm T}\) -esiintymästä. Esimerkiksi kirjainjono \({\rm H}{\rm T}{\rm T}{\rm H}{\rm H}{\rm T}{\rm H}\) vastaa erästä seitsemän kolikonheiton tulosjonoa. Siitä tulee Alicelle yksi piste ja Bobille kaksi. Täydellisyyden vuoksi otetaan mukaan myös pelaajat Cheryl, joka saa pisteen jokaisesta \({\rm T}{\rm H}\) -esiintymästä, ja Dustin, joka saa pisteen jokaisesta \({\rm T}{\rm T}\) -esiintymästä. Yleisyyttä tavoitellen sovitaan, että kolikkoa heitetään \(n\) kertaa. Tällöin puhutaan \(n\) -pelistä. Kaikkien mahdollisten \(n\)-pelien joukkoa kutsutaan \(n\)-peliavaruudeksi. Pelaajien nimet lyhennetään muotoon \({\rm A}\), \({\rm B}\), \({\rm C}\) ja \({\rm D}\). Toisesta heittokerrasta alkaen joku nelikosta saa pisteen jokaisella heittokerralla.
Oheinen suunnattu verkko esittää pelin kulkua sen jälkeen, kun kolikkoa on heitetty kaksi kertaa. Verkon solmujen nimet \({\rm A}\), \({\rm B}\), \({\rm C}\) ja \({\rm D}\) kertovat, kuka saa pisteen kyseiseen solmuun tultaessa. Kaaret tai nuolet
\[{\rm A}{\rm A},\;{\rm A}{\rm B},\;{\rm B}{\rm C},\;{\rm B}{\rm D},\;{\rm C}{\rm A},\;{\rm C}{\rm B},\;{\rm D}{\rm C},\;{\rm D}{\rm D}\]
vastaavat siirtymiä pelitilanteesta seuraavaan kolikonheiton myötä. Esimerkiksi tulosjonoa
\[{\rm H}{\rm H}{\rm T}{\rm T}{\rm H}{\rm T}{\rm T}{\rm T}\]
vastaa pelitilanne
\[{\rm A}{\rm B}{\rm D}{\rm C}{\rm B}{\rm D}{\rm D},\]
jossa Alicella ja Cherylillä on yksi piste kummallakin, Bobilla on kaksi pistettä ja Dustinilla kolme pistettä. Tulosjonot ja pelitilanteet vastaavat toisiaan kääntäen yksikäsitteisesti. Huomaa, että kaikki kirjaimista \({\rm A}\), \({\rm B}\), \({\rm C}\) ja \({\rm D}\) muodostetut jonot eivät edusta pelitilannetta: esimerkiksi \({\rm A}{\rm C}\) ei voi toteutua. Vain verkkokaavion mukaiset jonot ovat pelitilanteita.
Kun verkon solmut kootaan matriisiksi
\[\mathbf{G} = \left[\begin{array}{cc}{\rm A}&{\rm B}\\{\rm C}&{\rm D}\\\end{array}\right],\]
kaikki kaaret saadaan neliöstä
\[\mathbf{G}^2 = \left[\begin{array}{cc}{\rm A}&{\rm B}\\{\rm C}&{\rm D}\\\end{array}\right]^2 = \left[\begin{array}{cc} {\rm A}{\rm A}+{\rm B}{\rm C}&{\rm A}{\rm B}+{\rm B}{\rm D}\\{\rm C}{\rm A}+{\rm D}{\rm C}&{\rm C}{\rm B}+{\rm D}{\rm D} \end{array}\right],\]
mutta mikä parasta, kaikki \(n\) kolikonheittoa vastaavat \(n-1\) kaaren reitit saadaan matriisipotenssista \(\mathbf{G}^{n-1}\). Lukija voi tulla vakuuttuneeksi tästä laskemalla potenssin \(\mathbf{G}^3\) ja vertaamalla sitä verkkokaavioon. On tärkeää huomata, että toistaiseksi matriisialkiot ovat vain symboleja, joille tulon vaihdantalaki ei ole voimassa, joten laskutoimituksissa kannattaa olla huolellinen. Symbolien tai symbolijonojen tulo tarkoittaa vain niiden asettamista peräkkäin. Plusmerkki symbolijonojen välissä toimii erottimena, jolla kaksi jonoa erotetaan toisistaan. Tällainen “yhteenlasku” on vaihdannainen. Matriiseilla laskemisen säännöt voidaan tarvittaessa opiskella Wikipedian sivulta [6].
Huomautus. Merkkijonoilla laskeminen ei välttämättä ole epämääräistä puuhastelua. Siitä tulee aivan oikeaa matematiikkaa, kun otetaan käyttöön vapaan algebran käsite (ks. [4]). Nyt on kysymys aakkostosta \(\{{\rm A},{\rm B},{\rm C},{\rm D}\}\) muodostettujen merkkijonojen virittämästä vapaasta \({\mathbb Z}\)-algebrasta.
Pelitilanteesta pistetilanteeseen
Pistelaskentaan päästään käsiksi korvaamalla vaihdantalakia noudattamattomat symbolit \({\rm A}\), \({\rm B}\), \({\rm C}\) ja \({\rm D}\) vaihdantalakia noudattavilla symboleilla \(a\), \(b\), \(c\) ja \(d\) mainitussa järjestyksessä. Esimerkiksi Bobin pisteet pelitilanteessa \({\rm A}{\rm B}{\rm D}{\rm C}{\rm B}{\rm D}{\rm D}\) saadaan muodostamalla vastaava pistetilannetermi \(ab^2cd^3\) ja katsomalla symbolin \(b\) eksponentti: sehän on kaksi. Siirtymällä pelitilanteista pistetilanteisiin menetetään tieto siitä, missä järjestyksessä pisteet ovat kullekin kertyneet. Pelimatriisin \(\mathbf{G}\) tilalle astuu tällöin pistematriisi
\[\mathbf{S} = \left[\begin{array}{cc}a&b\\c&d\\\end{array}\right].\]
Kaikkien mahdollisten \(3\)-pelien pistetilanteet nähdään matriisista
\[\mathbf{S}^2 = \left[\begin{array}{cc}a^2+bc&ab+bd\\ac+cd&bc+d^2\end{array}\right].\]
Matriisialkioiden summasta
\[\mathbf{1}^T\mathbf{S}^2\mathbf{1} = a^2+bc+ab+bd+ac+cd+bc+d^2,\]
missä
\[\mathbf{1} = \left[\begin{array}{c}1\\1\end{array}\right],\quad \mathbf{1}^T = \left[\begin{array}{cc}1&1\end{array}\right],\]
havaitaan Alicen saavan yhdestä pelistä keskimäärin \((2+0+1+0+1+0+0+0)/8=1/2\) pistettä, ja Bobin vastaava keskiarvo on \((0+1+1+1+0+0+1+0)/8=1/2\). Keskiarvojen yhtäsuuruus ei ole yllätys. Ensimmäisen kappaleen lukemisen jälkeen ei enää yllätä sekään, että Alice voittaa Bobin kahdessa pelissä, kun taas Bob voittaa Alicen kolmessa pelissä. Miten käy, kun kolikkoa heitetään kolmen heiton sijaan sata kertaa? Tulosjonoja on aika monta. Niiden lukumäärä on \(31\)-numeroinen kokonaisluku.
Huomautus. Siirtyminen pelitilanteista pistetilanteisiin merkitsee siirtymistä vapaasta \({\mathbb Z}\)-algebrasta vastaavaan polynomialgebraan \({\mathbb Z}[a,b,c,d]\) (ks. [7]).
Fokus Aliceen ja Bobiin
Kuten lukija varmaan jo huomasi, parivaljakoiden (Alice, Bob) ja (Dustin, Cheryl) kesken vallitsee symmetria; toisin sanoen, kun verkkokaaviossa \({\rm A}\) ja \({\rm D}\), \({\rm B}\) ja \({\rm C}\) sekä \({\rm H}\) ja \({\rm T}\) vaihdetaan keskenään, kaavion informaatiosisältö ei muutu lainkaan. Sama vaikutus, siis ei vaikutusta ollenkaan, saadaan aikaan kiertämällä kaaviota \(180^\circ\).
Kun ollaan kiinnostuneita pelkästään Alicen ja Bobin keskinäisestä taistosta, pistetilannetermeissä \(c\) ja \(d\) korvataan ykkösillä. Silloin
\[\mathbf{S} = \left[\begin{array}{cc}a&b\\1&1\\\end{array}\right],\quad \mathbf{S}^2 = \left[\begin{array}{cc}a^2+b&ab+b\\a+1&b+1\end{array}\right],\]
ja kahden muuttujan \(a\) ja \(b\) pistetilannepolynomi saa muodon
\[\mathbf{1}^T\mathbf{S}^2\mathbf{1} = a^2+b+ab+b+a+1+b+1 = a^2+ab+a+3b+2.\]
Tästä riisutustakin versiosta nähdään Alicen ja Bobin pisteet sekä heidän kaksintaistelussa voittamiensa pelien määrät.
Huomautus. Kun \(c\) ja \(d\) korvataan ykkösillä, polynomialgebra \({\mathbb Z}[a,b,c,d]\) samalla projisoidaan alialgebraksi \({\mathbb Z}[a,b]\).
Fokus voitettujen pelien lukumäärään
Jos kiinnostuksen kohteena on pelkästään artikkelin alussa mainittu kysymys siitä, kumpi on todennäköinen voittaja, Alice vai Bob, pistetilannetermejä modifioidaan edelleen sopimalla, että \(ab=1\), jolloin tasapelit redusoituvat ykkösiksi. Esimerkiksi peliin \({\rm A}{\rm B}{\rm D}{\rm C}{\rm B}{\rm D}{\rm D}\) liittyvä pistetilannetermi \(ab^2cd^3\), joka on jo degeneroitunut muotoon \(ab^2\), pelkistyy sopimuksen jälkeen pelkäksi alkioksi \(b\). Tästä nähdään, että Bob voittaa Alicen yhdellä pisteellä kyseisessä pelissä. Polynomi
\[\begin{split} \mathbf{1}^T\mathbf{S}^2\mathbf{1} &= a^2+ab+a+3b+2 \\ &= a^2+1+a+3b+2 \\ &= a^2+a+3b+3 \end{split}\]
kertoo meille, että kolmesta kolikonheitosta voi syntyä kaikkiaan \(8=1^2+1+3\cdot 1+3=2^3\) (sijoita \(a=b=1\)) erilaista peliä. Niistä Alice voittaa yhden kahdella pisteellä (\(a^2\)) ja yhden yhdellä pisteellä (\(a\)), kun Bob puolestaan voittaa kolme peliä yhdellä pisteellä (\(3b\)). Alicen ja Bobin keskinäisessä kisassa tasapelejä on kolme (\(3\)). Degeneroitunutkin polynomi on täten sangen informatiivinen.
Huomautus. Sopimus \(ab=1\) merkitsee, että polynomialgebra \({\mathbb Z}[a,b]\) ensin projisoidaan polynomialgebraksi \({\mathbb Z}[a]\) ja sen jälkeen lokalisoidaan Laurentin polynomialgebraksi \({\mathbb Z}[a,a^{-1}]\) (ks. [5]).
Heittojen lukumäärä \(n+1\)
Polynomi \(\mathbf{1}^T\mathbf{S}^n\mathbf{1}\) monimutkaistuu vauhdikkaasti, kun \(n\) kasvaa. Sen aste kasvaa lineaarisesti, mutta kertoimet eksponentiaalisesti, minkä todistaminen jätetään lukijalle. Esimerkiksi
\[\begin{split} \mathbf{1}^T\mathbf{S}^6\mathbf{1} &= a^6+a^5+2a^4+8a^3+12a^2 \\ &\quad\; +18a+30+32b+19b^2+5b^3. \end{split}\]
Tässä termit on kirjoitettu alkion \(a\) alenevien potenssien mukaan, kun otetaan huomioon sopimus eli yhtälö \(ab=1\), jonka mukaan \(b=a^{-1}\) on alkion \(a\) käänteisalkio. Matriisipotenssien laskemista on mahdollista helpottaa diagonalisoimalla. Menetelmään tarkemmin puuttumatta todetaan, että matriisi \(S\) voidaan esittää hajotelmana
\[\mathbf{S} = \mathbf{P}\mathbf{\Lambda}\mathbf{P}^{-1},\]
missä \(\mathbf{P}^{-1}\) on matriisin \(\mathbf{P}\) käänteismatriisi, so.
\[\mathbf{P}\mathbf{P}^{-1} = \mathbf{P}^{-1}\mathbf{P} = \mathbf{I},\quad \mathbf{I} = \left[\begin{array}{cc}1&0\\0&1\\\end{array}\right],\]
ja \(\mathbf{\Lambda}\) on lävistäjämatriisi eli muotoa \[\left[\begin{array}{cc}\lambda_1&0\\0&\lambda_2\\\end{array}\right].\]
Silloin on voimassa
\[\mathbf{S}^n = \mathbf{P}\mathbf{\Lambda}^n\mathbf{P}^{-1},\]
ja keskimmäinen matriisipotenssi on helppoa laskea, sillä
\[\mathbf{\Lambda}^n = \left[\begin{array}{cc}\lambda_1^n&0\\0&\lambda_2^n\\\end{array}\right].\]
Lukija voi verifioida nämä kaksi yhtälöä harjoitustehtävänä. Osoittautuu, että hajotelma \(\mathbf{S}=\mathbf{P}\mathbf{\Lambda}\mathbf{P}^{-1}\) toteutuu, kun lävistäjäalkioina ovat
\[\begin{split} \lambda_1 &= \frac{1}{2}\left(a+1+\sqrt{(a-1)^2+4b}\right), \\ \lambda_2 &= \frac{1}{2}\left(a+1-\sqrt{(a-1)^2+4b}\right), \end{split}\]
ja kerroinmatriisit ovat esimerkiksi
\[\begin{split} \mathbf{P} &= \left[\begin{array}{cc} \lambda_1-1 & \lambda_2-1 \\ 1 & 1 \end{array}\right], \\ \mathbf{P}^{-1} &= \frac{1}{\lambda_1-\lambda_2} \left[\begin{array}{rc} 1 & 1-\lambda_2 \\ -1 & \lambda_1-1 \end{array}\right]. \end{split}\]
Tämänkin toteen näyttäminen normaaliin tapaan laskemalla jätetään lukijalle harjoitustehtäväksi.
Huomautus. Symbolien \(a\) ja \(b\) olemuksesta tiedetään vain, että \(ab=1\). Ei ole tarkoituksenmukaista esitellä uusia algebrallisia struktuureja aikaisemmissa huomautuksissa esiteltyjen lisäksi, joten edellä mainittujen neliöjuurten olemus ja olemassaolo jäävät hämärän peittoon. Kun tavoitteena on matriisitulon \(\mathbf{1}^T\mathbf{S}^n\mathbf{1}\) esittäminen kokonaislukukertoimisena polynomina, ja neliöjuuret lopulta supistuvat lausekkeista pois, tällainen formaali eli muodollinen kaavojen pyörittely nähtäköön pelkästään keinona päästä lopputulokseen. Menettely voidaan hyväksyä ainakin silloin, kun lopputuloksen pätevyys on mahdollista verifioida laillisin keinoin. Monesti jonkin lausekkeen keksiminen on hyvin vaikeaa, mutta kun lauseke lopulta tavalla tai toisella keksitään, sen todistaminen päteväksi esimerkiksi induktiolla on hyvin yksinkertaista. Sitä paitsi: eikös joku ole joskus sanonut, että “tarkoitus pyhittää keinot”.
Yleiseen \((n+1)\)-peliin liittyvän tehtävän ratkaisun vaikeus piilee siinä, että potenssien \(\lambda_1^n\) ja \(\lambda_2^n\) ja lopulta polynomin \(\mathbf{1}^T\mathbf{S}^n\mathbf{1}\) laskeminen johtaa monimutkaisiin lausekkeisiin. Kun kyseinen polynomi on jollain keinolla saatu laskettua, se voidaan esittää kanonisessa muodossa
\[p(a,b) = \sum_{i=1}^I\alpha_ia^i + \gamma + \sum_{j=1}^J\beta_jb^j.\]
Tasapelien lukumäärä on
\[p(0,0) = \gamma.\]
Alicen ja Bobin voittamien pelien lukumäärät ovat vastaavasti
\[p(1,0)-\gamma = \sum_{i=1}^I\alpha_i \;\;\text{ja}\;\; p(0,1)-\gamma = \sum_{j=1}^J\beta_j\,.\]
Huomautus. Nollan sijoittaminen muuttujan \(a\) tai \(b\) paikalle saattaa tuntua oudolta, kun muistetaan sopimus \(ab=1\). Idea on siinä, että tuota sopimusta käytetään saatettaessa polynomin lauseketta edellä esitettyyn kanoniseen muotoon. Tämän jälkeen on enää kysymys polynomin kertoimista ja niiden summista. Jos ne saadaan selville sijoittamalla nolla muuttujan paikalle, tälle polynomin syntyhistoriaan nähden laittomalle sijoitukselle ei ole mitään estettä. Kun kanonisointiin liittyvät laskut ovat vielä kesken, nollan sijoittaminen muuttujan paikalle johtaa väärään lopputulokseen. Esimerkiksi jos yhtälöketjun
\[(a+b)^2 = a^2+2ab+b^2 = a^2+2+b^2\]
ensimmäiseen yhtälöön sijoitetaan \(a=b=0\) vakiotermin paljastamiseksi, saadaan väärä tulos 0. Sijoitus sopii tehdä vasta loppuun asti laskettuun kanoniseen muotoon. Silloin saadaan oikea tulos 2.
Eräs keino mutkikkaiden lausekkeiden hallitsemiseksi on käyttää laskentaan jotakin symbolisen laskennan ohjelmistoa. Näin on tehty mm. artikkelissa [1], vaikkakin eri lähtökohdista kuin edellä esitetty. Symbolisen laskennan lisäksi todistusvoimaa saadaan kompleksianalyysista kuten artikkelissa [3]. Itse asiassa polynomi \(p(a,b)\) voidaan kirjoittaa vastaavaksi kompleksimuuttujan \(z\) Laurentin sarjaksi
\[L(z) = \sum_{i=1}^I\alpha_iz^i + \gamma + \sum_{j=1}^J\beta_jz^{-j},\]
joka tässä tapauksessa, kun termejä on vain äärellinen määrä, on pelkkä Laurentin polynomi. Jos funktion \(L\) lauseketta ei tunneta sarjamuodossa, sarjan tuntemattomat kertoimet saadaan joskus selville kompleksista integrointia käyttäen. Vaikka se ei onnistuisikaan, integraalit saattavat kuitenkin kertoa jotain oleellista informaatiota kertoimista.
Tuloksia
Vaikka kolikonheittoprobleema johtaa pitkiin laskuihin, sitä on hyvin helppoa tutkia kokeellisesti. Sadan heiton kisaa Alicen ja Bobin välillä simuloitiin tätä artikkelia varten yksinkertaisella Python-ohjelmalla, joka käytti heittotulosten arpomiseen satunnaislukugeneraattoria. Kymmenestämiljoonasta pelistä Alice voitti \(4\,574\,682\), Bob voitti \(4\,859\,895\), ja tasapelejä tuli \(565\,423\) kappaletta. Tämän kokeen valossa Alice voittaa pelin noin \(45{,}7\) %:n todennäköisyydellä, Bob voittaa noin \(48{,}6\) %:n todennäköisyydellä, ja peli päättyy tasan noin \(5{,}7\) %:n todennäköisyydellä. Artikkelissa [1] lasketut teoreettiset arvot ovat vastaavasti \(0{,}4576402592\), \(0{,}4858327983\) ja \(0{,}0565269425\).
Eräs kollega laski Mathematica-ohjelmalla polynomin \(p(a,b)=\mathbf{1}^T\mathbf{S}^{99}\mathbf{1}\) arvot \(p(1,0)\), \(p(0,1)\) ja \(p(0,0)\), kun
\[\mathbf{S} = \left[\begin{array}{cc}a&b\\1&1\\\end{array}\right],\]
ja sai sitä kautta selville, miten monta \(2^{100}\):sta mahdollisesta pelistä päätyy Alicen tai Bobin voittoon tai tasapeliin:
Artikkelissa [3] todistetaan, että Bob voittaa \(n\)-pelin todennäköisemmin kuin Alice, kun \(n\ge 3\). Toisin sanoen Bob voittaa suuremman osan \(n\)-peliavaruuden peleistä kuin Alice, kun \(n\ge 3\). Artikkelissa todistetaan myös, että kumpikin todennäköisyys lähestyy raja-arvonaan lukua \(1/2\), kun \(n\) kasvaa rajatta, ja todennäköisyyksien erotus
\[{\mathbb P}\big(\{\text{Bob voittaa}\}\big)-{\mathbb P}\big(\{\text{Alice voittaa}\}\big)\]
vieläpä käyttäytyy asymptoottisesti kuin
\[\frac{1}{2\sqrt{n\pi}} + {\cal O}\left(n^{-3/2}\right).\]
Pohdintaa
Alicelle pisteen tuovia pareja \({\rm H}{\rm H}\) on tasan yhtä monta kuin Bobille pisteen tuovia pareja \({\rm H}{\rm T}\), kun kaikki \(n\)-pelit otetaan mukaan laskentaan. Siksi on ehkä yllättävää, että Bob kuitenkin voittaa suuremman osan yksittäisistä \(n\)-peleistä kuin Alice. Koska tarkastelu käsittää koko peliavaruuden, mukana ovat myös sellaiset pelit, joissa Alice saa yli \(n/2\) pistettä. Tällaisiin peleihin sisältyvät Alicen pisteet ovat poissa muihin peleihin sisältyvistä Alicen pisteistä. Bobin sen sijaan on mahdotonta saada yhdestäkään pelistä enempää kuin \(n/2\) pistettä. Näin ollen Bobin pisteet ovat tasaisemmin jakautuneet \(n\)-pelien kesken. Kärjistäen voidaan sanoa, että Alice voittaa pienen määrän pelejä isolla pistemäärällä, jolloin Bob saa tilaisuuden voittaa suuren määrän pelejä pienellä pistemäärällä. Tällainen heuristiikka tukee Bobin onnekkuutta, mutta kokonaan toinen asia on siihen pohjautuvan todistuksen kirjoittaminen, jos se ylipäänsä on mahdollista.
Daniel Litt haluaisi nähdä Bobin onnekkuudelle todistuksen, jossa intuitio ei peittyisi teknisten yksityiskohtien taakse. Joskus todistukset ovat sellaisia, että väite kyllä putkahtaa monimutkaisen päättelyketjun ja hirmuisten laskelmien jälkeen ulos, ja kaikki pystyvät verifioimaan todistuksen päteväksi vaihe vaiheelta, mutta kukaan ei oikeastaan ymmärrä, mitä todistuksessa tapahtuu. Littin probleema yleiselle \(n\)-pelille on sen luontoinen, että joku aiheesta kiinnostunut nuori opiskelija, jolla ei vielä ole kokemuksen painolastia harteillaan, saattaisi onnistua keksimään omintakeisen ratkaisun, johon urautuneiden ammattilaisten mielikuvitus ei ole riittänyt. Quanta Magazine -verkkolehdessä [2] on professori Littin haastattelu.
Viitteet
[1] Shalosh B. Ekhad & Doron Zeilberger: How to Answer Questions of the Type: If you toss a coin \(n\) times, how likely is HH to show up more than HT?
Kirjoitus arXiv-julkaisualustalla 22.5.2024.
https://arxiv.org/abs/2405.13561
[2] Erica Klarreich: Perplexing the Web, One Probability Puzzle at a Time.
Kirjoitus Quanta Magazine -verkkolehdessä 29.8.2024.
https://www.quantamagazine.org/
perplexing-the-web-one-probability
-puzzle-at-a-time-20240829/
[3] Simon Segert: A proof that HT is more likely to outnumber HH than vice versa in a sequence of n coin flips.
Kirjoitus arXiv-julkaisualustalla 26.5.2024.
https://arxiv.org/abs/2405.16660
[4] Wikipedia: Free algebra.
https://en.wikipedia.org/wiki/Free_algebra
[5] Wikipedia: Laurent polynomial.
https://en.wikipedia.org/wiki/Laurent_polynomial
[6] Wikipedia: Matrix (mathematics).
https://en.wikipedia.org/wiki/Matrix_(mathematics)
[7] Wikipedia: Polynomial ring.
https://en.wikipedia.org/wiki/Polynomial_ring