Penney Ante is een gokspel waarbij twee spelers elk een verschillende, maar even lange reeks van opeenvolgende worpen met een muntstuk kiezen. Bijvoorbeeld kop-kop-munt of kortweg KKM. Daarna wordt herhaaldelijk een muntstuk opgeworpen, totdat één van de twee gekozen reeksen wordt waargenomen. De speler die deze reeks gekozen heeft, wint het spel.

Penney Ante

Bestaat er een strategie die de ene speler een grotere kans geeft om te winnen dan de andere speler? Vreemd genoeg bestaat die wel degelijk. John Conway vond zelfs een eenvoudige manier om de kans te berekenen dat een gekozen reeks zal winnen tegen een andere reeks. We leggen het algoritme hier uit voor tripletten (reeksen van lengte drie), maar het is algemeen toepasbaar voor reeksen van willekeurige lengte, zelfs voor reeksen van verschillende lengte.

Eerst plaatsen we de twee tripletten onder elkaar, waarbij de letters op corresponderende posities netjes onder elkaar uitgelijnd worden. We hebben dit hieronder gedaan voor de twee tripletten MKK en KKK. We vergelijken nu de twee tripletten: als ze gelijk zijn, dan plaatsen we een 1 boven de eerste letter van de eerste reeks, anders plaatsen we een 0.

0
MKK
KKK

Vervolgens verwijderen we de eerste letter van het bovenste triplet, en schuiven de overige letters één positie naar links, waardoor de beginletters weer netjes onder elkaar komen te staan. Daarna vergelijken we de twee letters van de bovenste reeks met de eerste twee letters van de onderste reeks: als ze gelijk zijn, dan plaatsen we een 1 boven de eerste letter van de eerste reeks, anders plaatsen we een 0.

1
KK
KKK

We blijven deze procedure herhalen tot en met de laatste letter van de bovenste reeks, waarbij we telkens de resterende letters van de bovenste reeks vergelijken met evenveel letters aan het begin van de onderste reeks (als de onderste reeks minder letters heeft dan de bovenste reeks, dan schrijven we per definitie een 0).

1
K
KKK

Finaal schrijven we alle bekomen enen en nullen achter elkaar, wat op de volgende manier kan voorgesteld worden:

011
MKK
KKK

De resulterende reeks van enen en nullen noemen we een bitreeks. Deze bitreeks is een maat voor de graad van overlap tussen de twee reeksen van opeenvolgende worpen, en kan geïnterpreteerd worden als een binair getal. In bovenstaand voorbeeld bekwamen we de bitreeks 011, wat als binair getal gelijk is aan de decimale waarde 3.

De bitreeksen zoals we die hierboven hebben leren bepalen, kunnen we nu gebruiken om de kansverhouding te berekenen voor twee gegeven reeksen A en B. We noteren de bitreeks die we bekomen als we de reeks A zowel bovenaan als onderaan schrijven als bAA, de bitreeks die we bekomen als we de reeks A bovenaan en de reeks B onderaan schrijven als bAB, enzoverder. De kansverhouding kA:kB als de reeksen A en B het tegen elkaar opnemen, kunnen we dan berekenen als kA=bBB−bBAkB=bAA−bAB waarbij we voor de aftrekking in het rechterlid gebruikmaken van de decimale waarde van de bitreeksen. Als we als voorbeeld nemen dat A = KKK en B = MKK, dan kunnen we eerst de bitreeksen bepalen:

  111       000
A:KKK     A:KKK
A:KKK     B:MKK

  100       011
B:MKK     B:MKK
B:MKK     A:KKK

Als we deze bitreeksen omzetten naar hun decimale waarden (het binaire getal 111 is gelijk aan 7, het binaire getal 000 is gelijk aan 0, het binaire getal 100 is gelijk aan 4 en het binaire getal 011 is gelijk aan 3) en invullen in bovenstaande vergelijkingen, dan krijgen we dat kA=(100)2−(011)2=4−3=1kB=(111)2−(000)2=7−0=7 De kansverhouding dat reeks A wint tegen reeks B is dus kA:kB=1:7. Merk op dat doorgaans niet de kansverhouding zelf gerapporteerd wordt, maar de genormaliseerde kansverhouding die we bekomen door kA en kB te delen door hun grootste gemeenschappelijke deler. We schrijven daarom niet dat de kansverhouding 4:2 is, maar 2:1.

Als we de kans dat reeks A wint noteren als pA en de kans dat reeks B wint als pB, dan bekomen we dat pA=kAkA+kB=11+7=18, pB=kBkA+kB=71+7=78 Merk op dat het bij deze kansberekeningen niet uitmaakt of we gebruikmaken van de kansverhouding of de genormaliseerde kansverhouding.

Opgave

In deze opgave stellen we de uitkomst van een worp met een muntstuk voor door een hoofdletter: K voor kop en M voor munt. Op die manier kunnen we een reeks opeenvolgende worpen voorstellen als een string die enkel bestaat uit de letters K en M. Gevraagd wordt:

De twee reeksen van worpen die aan de functies bitreeks, kansverhouding en kansen worden doorgegeven, hoeven niet even lang te zijn en mogen ook gelijk zijn.

Voorbeeld

>>> winnaar('KKK', 'MKK', 'KMKMKKKKMKKKMMMMKMKK')
2
>>> winnaar('MKM', 'MMK', 'KMKMKKKKMKKKMMMMKMKK')
1
>>> winnaar('MKK', 'KKM', 'KKKKKKKKKKKKKKKKKKKK')
0
>>> winnaar('MKK', 'MKK', 'KKKKKKKKKKKKKKKKKKKK')
Traceback (most recent call last):
AssertionError: reeksen mogen niet gelijk zijn
>>> winnaar('MKKM', 'MKK', 'KKKKKKKKKKKKKKKKKKKK')
Traceback (most recent call last):
AssertionError: reeksen moeten zelfde lengte hebben

>>> bitreeks('KKK', 'MKK')
'000'
>>> bitreeks('MKM', 'MMK')
'001'
>>> bitreeks('MKK', 'KKM')
'011'

>>> kansverhouding('KKK', 'MKK')
(1, 7)
>>> kansverhouding('MKM', 'MMK')
(1, 2)
>>> kansverhouding('MKK', 'KKM')
(3, 1)

>>> kansen('KKK', 'MKK')
(0.125, 0.875)
>>> kansen('MKM', 'MMK')
(0.3333333333333333, 0.6666666666666666)
>>> kansen('MKK', 'KKM')
(0.75, 0.25)

Bronnen