Min specialitet inom matematiken är sannolikhetsteori. Ibland säger jag lite skämtsamt att sannolikhetsteori handlar om slantsingling. Ett korn av sanning finns det i detta, då snart sagt allt vi sysslar med i sannolikhetsteorin byggs upp med slantsinglingarna som grund.1 För det mesta syns dock inte slantsinglingarna bakom de modeller vi studerar - Isingmodeller, diffusionsprocesser, interagerande partikelsystem och vad det vara må - lite grand på samma sätt som vi inte ser de enskilda atomer som bygger upp oss själva och världen omkring oss. Därför känner jag mig lite glad över att slantsinglingarna i min senaste matematiska uppsats Rigorous computer analysis of the Chow-Robbins game, författad tillsammans med Chalmerskollegan Johan Wästlund2, hamnar i omedelbart fokus. Back to basics!
I det så kallade Chow-Robbinsspelet singlar vi en slant upprepade gånger och får sluta när vi vill, utan någon begränsning på hur länge vi får hålla på. När vi slutar belönas vid med ett penningbelopp motsvarande den andel krona som erhölls, dvs antalet krona dividerat med antalet slantsinglingar. Om vi till exempel väljer att sluta efter sekvensen "klave, krona, klave, krona, krona", dvs efter tre krona av fem möjliga så att andelen krona blir 3⁄5, blir vår belöning 60 öre.
Vad är en optimal strategi för detta spel, om syftet är att erhålla så stor förväntad (dvs genomsnittlig) belöning som möjligt?
En första gissning skulle kunna vara att eftersom varje slantsingling ger krona eller klave med sannolikhet 1⁄2 vardera så spelar det ingen roll hur vi gör - och vi får i snitt 50 öre hur vi än beter oss. Detta stämmer emellertid inte. Här är en strategi som ger mer än 50 öre i snitt:
Singla slanten en första gång. Avsluta om du får krona. Om du får klave, singla slanten en gång till, och avsluta sedan.
Denna strategi ger utfallet "krona" med sannolikhet 1⁄2, och "klave, krona" respektive "klave, klave" med sannolikhet 1⁄4 vardera. Förväntad belöning blir därför 1⁄2×1 + 1⁄4×1⁄2 + 1⁄4×0 kr = 62,5 öre.
Strategin kan förbättras ytterligare. T.ex. är det ju så att vi efter "klave, klave" har en hel del att vinna men inget att förlora på att gå vidare. Den som kombinerar ett visst mått av klurighet med dito händighet i bråkräkning kan roa sig med att arbeta vidare och finna successivt bättre strategier.3
Chow-Robbinsspelet har funnits i litteraturen sedan 1964, men något slutgiltigt svar på frågan om optimal strategi har inte kunnat ges. Johans och mitt bidrag består i utarbetandet av en datormetod som i given situation ger svar (med matematisk visshet) på om man bör gå vidare eller inte. Så t.ex. vet vi att med 100 gjorda slantsinglingar så bör vi avbryta om vi har minst 54 krona, men fortsätta om vi har högst 53. Datorberäkningarna blir dock ganska omfattande, och det finns vissa gränsfall där vi inte förmått avgöra huruvida det är lönsamt att gå vidare; det första fall vi inte lyckats knäcka är då vi har 116 krona av 220 möjliga. Läsaren inbjudes härmed att försöka förbättra vår metod.
Fotnoter
1) För den matematiskt litterate: Antag att vi har en obegränsad följd av oberoende kast med ett symmetriskt mynt. Skriv upp siffran 1 då vi får krona, och siffran 0 då vi får klave. Den sifferföljd vi då får (t.ex. 0011110101001...) kan alternativt beskrivas som binärutvecklingen hos ett tal valt enligt likformig fördelning (Lebesguemåttet) på intervallet [0,1]. Med hjälp av decimalsaxning kan vi i själva verket få oändligt många sådana slumptal, och från vart och ett av dessa kan vi konstruera en stokastisk variabel med vilken som helst fördelning vi önskar, och härifån kan vi bygga vidare våra stokastiska modeller av godtycklig komplexitetsgrad.
2) Johan är en av matematikersveriges vassaste tänkare, känd bland annat för sitt i samarbete med Svante Linusson utarbetade bevis av Parisis förmodan och för sitt banbrytande arbete om det stokastiska handelsresandeproblemet.
3) Ett klurigt fall är det ovan nämnda där vi har tre krona av fem möjliga. Jag roade mig under en julkonsert med Bo Kaspers Orkester i förra månaden med att i huvudet bevisa att i det fallet är det lönsamt att fortsätta. En trevlig övning - dock räknar jag inte med att alla läsare kommer att instämma i min uppfattning att dylika huvudräkningar är en bra metod att förhöja en konsertupplevelse.
I det så kallade Chow-Robbinsspelet singlar vi en slant upprepade gånger och får sluta när vi vill, utan någon begränsning på hur länge vi får hålla på. När vi slutar belönas vid med ett penningbelopp motsvarande den andel krona som erhölls, dvs antalet krona dividerat med antalet slantsinglingar. Om vi till exempel väljer att sluta efter sekvensen "klave, krona, klave, krona, krona", dvs efter tre krona av fem möjliga så att andelen krona blir 3⁄5, blir vår belöning 60 öre.
Vad är en optimal strategi för detta spel, om syftet är att erhålla så stor förväntad (dvs genomsnittlig) belöning som möjligt?
En första gissning skulle kunna vara att eftersom varje slantsingling ger krona eller klave med sannolikhet 1⁄2 vardera så spelar det ingen roll hur vi gör - och vi får i snitt 50 öre hur vi än beter oss. Detta stämmer emellertid inte. Här är en strategi som ger mer än 50 öre i snitt:
Singla slanten en första gång. Avsluta om du får krona. Om du får klave, singla slanten en gång till, och avsluta sedan.
Denna strategi ger utfallet "krona" med sannolikhet 1⁄2, och "klave, krona" respektive "klave, klave" med sannolikhet 1⁄4 vardera. Förväntad belöning blir därför 1⁄2×1 + 1⁄4×1⁄2 + 1⁄4×0 kr = 62,5 öre.
Strategin kan förbättras ytterligare. T.ex. är det ju så att vi efter "klave, klave" har en hel del att vinna men inget att förlora på att gå vidare. Den som kombinerar ett visst mått av klurighet med dito händighet i bråkräkning kan roa sig med att arbeta vidare och finna successivt bättre strategier.3
Chow-Robbinsspelet har funnits i litteraturen sedan 1964, men något slutgiltigt svar på frågan om optimal strategi har inte kunnat ges. Johans och mitt bidrag består i utarbetandet av en datormetod som i given situation ger svar (med matematisk visshet) på om man bör gå vidare eller inte. Så t.ex. vet vi att med 100 gjorda slantsinglingar så bör vi avbryta om vi har minst 54 krona, men fortsätta om vi har högst 53. Datorberäkningarna blir dock ganska omfattande, och det finns vissa gränsfall där vi inte förmått avgöra huruvida det är lönsamt att gå vidare; det första fall vi inte lyckats knäcka är då vi har 116 krona av 220 möjliga. Läsaren inbjudes härmed att försöka förbättra vår metod.
Fotnoter
1) För den matematiskt litterate: Antag att vi har en obegränsad följd av oberoende kast med ett symmetriskt mynt. Skriv upp siffran 1 då vi får krona, och siffran 0 då vi får klave. Den sifferföljd vi då får (t.ex. 0011110101001...) kan alternativt beskrivas som binärutvecklingen hos ett tal valt enligt likformig fördelning (Lebesguemåttet) på intervallet [0,1]. Med hjälp av decimalsaxning kan vi i själva verket få oändligt många sådana slumptal, och från vart och ett av dessa kan vi konstruera en stokastisk variabel med vilken som helst fördelning vi önskar, och härifån kan vi bygga vidare våra stokastiska modeller av godtycklig komplexitetsgrad.
2) Johan är en av matematikersveriges vassaste tänkare, känd bland annat för sitt i samarbete med Svante Linusson utarbetade bevis av Parisis förmodan och för sitt banbrytande arbete om det stokastiska handelsresandeproblemet.
3) Ett klurigt fall är det ovan nämnda där vi har tre krona av fem möjliga. Jag roade mig under en julkonsert med Bo Kaspers Orkester i förra månaden med att i huvudet bevisa att i det fallet är det lönsamt att fortsätta. En trevlig övning - dock räknar jag inte med att alla läsare kommer att instämma i min uppfattning att dylika huvudräkningar är en bra metod att förhöja en konsertupplevelse.
Detta problem påminner lite om Ekström och Wanntorps artikel: http://www2.math.uu.se/~henrik/artiklar/HW5.pdf
SvaraRaderadär författarna får fram ett vackert resultat om hur man stoppar en Brownsk brygga.
Kul Olle! Tills jag läste bloggposten och kollade iaf lite i artikeln hade jag kunna svära på att lösningen måste ges av den lägre gränsen i olikheten (2). Därför att medlets väntevärde minskar om a>1/2 och OM man bara singlar slant EN gång till. Men ekv. (1) måste ju förstås vara det korrekta sambandet för den optimala strategin.
SvaraRaderaHenriks länk är också intressant. Är det möjligen det analoga problemet i det kontinuerliga fallet?
Allt det här påminner väldigt mycket om optionsvärderingsmatematik.
Ekströms och Wanntorps problem är förvisso besläktat med Chow-Robbins, men jag skulle inte kalla det för "det analoga problemet i det kontinuerliga fallet", utan reservara den benämningen för det stopproblem för Brownsk rörelse som studeras bl.a. av Shepp (1969).
SvaraRadera