Alla inlägg av Anders Vuorijoki

Gott och blandat

Du kanske har hört att det krävs sju blandningar för att blanda en kortlek¹. Men varifrån kommer det här påståendet? Och krävs det faktiskt just sju blandningar?

Svaret på första frågan är ganska enkelt, påståendet kommer ursprungligen ur en artikel (”Trailing the Dovetail Shuffle to Its Lair”) av matematikerna Persi Diaconis och Dave Bayer. För att svara på den andra frågan måste vi titta noggrannare på artikeln.

Det jag menar med en blandning är en s.k. riffle shuffle², men i äkta matematisk anda så behandlar inte artikeln fysiska kortlekar som blandas utan en matematisk modell av detta. Modellen som används är den s.k. Gilbert-Shannon-Reeds modellen. I modellen går en blandning ut på att kortleken först delas i två ungefär lika stora högar. Högarna kombineras sedan ett kort i taget så att man slumpmässigt väljer en av högarna och placerar dess bottenkort överst i den nya kombinerade högen. Sannolikheten att en hög väljs är direkt proportionell mot hur många kort det finns i högen, ju fler kort desto sannolikare. Det har visat sig att denna modell motsvarar ganska bra hur människor i verkligheten blandar kortlekar.

Utöver en modell för kortblandning behöver man också ett mått på hur väl blandad en kortlek är. Det finns flera olika mått som går att användas men de fungerar alla så att man jämför resultaten av blandningen med en perfekt blandning (var alla arrangemang av korten är lika sannolika). Det måttet som Diaconis och Bayer bestämde sig för att använda kallas ”total variation distance” (TVD).

TVD kan definieras såhär. Låt A vara en händelse, t.ex. att första kortet är ruter tre eller något mer komplicerat som att man vinner en viss form av patiens. P1(A) är sannolikheten för händelsen enligt modellen och P2(A) är sannolikheten för händelsen om kortleken är perfekt blandad. TVD är lika med det högsta möjliga värdet på P1(A)-P2(A). Så om TVD=0.3 så finns det någon händelse som är 30 procentenheter sannolikare med en kortlek blandad enligt modellen än med en perfekt blandad kortlek. TVD=1 betyder alltså att kortleken är helt oblandad medan TVD=0 betyder att den är perfekt blandad.

I grafen ovanför ser vi att TVD hålls först nästan konstant men börjar sjunka snabbt kring 6 blandningar och efter det ungefär halveras det per blandning. För sju blandningar ser vi att TVD är ungefär 0.3 vilket är ganska lågt. Men är det tillräckligt lågt? Det tråkiga svaret är att det beror på vad man spelar. Det krävs färre blandningar för kortspel var man inte bryr sig om land. Men t.ex. finns det också en version av patiens var sannolikheten att man vinner är 30% högre om man använder en kortlek som har blandats sju gånger istället för en perfekt blandad kortlek.

Men TL;DR: Sju blandningar är helt ok för de flesta spel.

¹ T.ex. från Numberphile https://www.youtube.com/watch?v=AxJubaijQbI

² https://www.youtube.com/watch?v=Pd-71L3KoOI