Gilbert–Shannon–Reeds modell

Inom matematiken för att blanda spelkort är Gilbert -Shannon-Reeds-modellen en sannolikhetsfördelning på riffle shuffle-permutationer som har rapporterats vara en bra matchning för experimentellt observerade resultat av mänsklig shuffling, och som ligger till grund för en rekommendation att en Kortleken bör slumpas sju gånger för att den ska kunna slumpas ut ordentligt. Det är uppkallat efter verk av Edgar Gilbert , Claude Shannon och J. Reeds, rapporterat i en teknisk rapport från Gilbert 1955 och i ett opublicerat manuskript från 1981 av Reeds.

Modellen

En riffel-shuffle-permutation av en sekvens av element erhålls genom att dela upp elementen i två sammanhängande delsekvenser och sedan godtyckligt interfoliera de två delsekvenserna. Detta beskriver till exempel många vanliga sätt att blanda en kortlek genom att skära upp kortleken i två korthögar som sedan rullas ihop. Gilbert-Shannon-Reeds-modellen tilldelar en sannolikhet till var och en av dessa permutationer. På detta sätt beskriver den sannolikheten för att erhålla varje permutation, när en shuffle utförs slumpmässigt. Modellen kan definieras på flera likvärdiga sätt, och beskriver alternativa sätt att utföra denna slumpmässiga blandning:

Mest likt sättet som människor blandar kort, beskriver Gilbert-Shannon-Reeds-modellen sannolikheterna som erhålls från en viss matematisk modell för att slumpmässigt klippa och sedan kasta en kortlek. Först skärs kortleken i två paket. Om det finns totalt ${\displaystyle n} kort, så$ definieras sannolikheten att välja $k$ kort i den första kortleken och ${\displaystyle nk} i den andra kortleken som$ ${\tbinom {n}{k}}/2^{n}$ . Sedan flyttas ett kort i taget upprepade gånger från botten av ett av paketen till toppen av den blandade kortleken, så att om $x$ -kort finns kvar i ett paket och $y$ -kort finns kvar i det andra paketet, då är sannolikheten för att välja ett kort från det första paketet $x/(x+y)$ och sannolikheten för att välja ett kort från det andra paketet är $y/(x+y)$ .
En andra, alternativ beskrivning kan baseras på en egenskap hos modellen, att den genererar en permutation av den initiala kortleken där varje kort är lika sannolikt att ha kommit från det första eller andra paketet. För att generera en slumpmässig permutation enligt denna modell, börja med att vända ett rättvist mynt $n$ gånger, för att för varje position av den blandade kortleken avgöra om det kommer från det första paketet eller det andra paketet. Dela sedan upp i två paket vars storlekar är antalet svansar och antalet vända huvuden och använd samma myntvändningssekvens för att avgöra från vilket paket du ska dra varje kort i den blandade kortleken.
En tredje alternativ beskrivning är mer abstrakt, men lämpar sig bättre för matematisk analys. Generera en uppsättning av $n$ -värden från den enhetliga kontinuerliga fördelningen på enhetsintervallet och placera dem i sorterad ordning. Sedan mappar dubbleringskartan $x\mapsto 2x{\pmod {1}}$ från teorin om dynamiska system detta poängsystem till en permutation av de punkter där den permuterade ordningen lyder Gilbert-Shannon-Reeds-modellen, och positionerna för de nya punkterna är återigen enhetligt slumpmässiga.

Bland alla möjliga riffle shuffle-permutationer i en kortlek ger Gilbert-Shannon-Reeds-modellen nästan alla riffler lika sannolikhet, $displaystyle 1/2^{n}}$ , att inträffa. Det finns dock ett undantag, identitetspermutationen , som har en större sannolikhet $(n+1)/2^{n}$ att inträffa.

Omvänd

Den omvända permutationen av ett slumpmässigt gevär kan genereras direkt. För att göra det, börja med en kortlek med n kort och dela sedan ut det nedersta kortet på en av två högar upprepade gånger, och välj slumpmässigt med lika sannolikhet vilken av de två högarna som varje kort ska delas ut på. Sedan, när alla kort har delats ut, stapla de två högarna ihop igen.

Effekten av upprepade rifflar

Bayer & Diaconis (1992) analyserade matematiskt det totala variationsavståndet mellan två sannolikhetsfördelningar på permutationer: den enhetliga fördelningen där alla permutationer är lika sannolika, och fördelningen som genereras av upprepade tillämpningar av Gilbert-Shannon-Reeds-modellen. Det totala variationsavståndet mäter hur lika eller olika två sannolikhetsfördelningar är; den är noll endast när de två fördelningarna är identiska och uppnår ett maximalt värde på ett för sannolikhetsfördelningar som aldrig genererar samma värden som varandra. Bayer och Diaconis rapporterade att för kortlekar med n blandade kort ${\tfrac {3}{2}}\log _{2}n+\theta$ gånger, där θ är en godtycklig konstant är det totala variationsavståndet nära ett när θ är signifikant mindre än noll, och nära noll när θ är signifikant större än noll, oberoende av n . Särskilt deras beräkningar visade att för n = 52 ger fem rifflar en fördelning vars totala variationsavstånd från uniform fortfarande är nära ett, medan sju rifflar ger totalt variationsavstånd 0,334. Detta resultat rapporterades allmänt som antydde att kortlekar borde slumpas sju gånger för att grundligt randomisera dem.

Liknande analyser har utförts med användning av Kullback–Leibler-divergensen , ett avstånd mellan två sannolikhetsfördelningar definierade i termer av entropi ; avvikelsen mellan en fördelning och uniform kan tolkas som antalet informationsbitar som fortfarande kan återställas om kortlekens initiala tillstånd. Resultaten är kvalitativt olika: snarare än att ha en skarp tröskel mellan slumpmässigt och icke-slumpmässigt vid ${\tfrac {3}{2}}\log _{2}n$ blandas, som händer för totalt variationsavstånd avtar divergensen mer gradvis och minskar linjärt när antalet blandningar varierar från noll till ${\displaystyle \log _{2}n} ($ vid vilken punkt antalet återstående informationsbitar är linjärt , mindre med en logaritmisk faktor än dess initiala värde) och sedan minskande exponentiellt tills, efter ${\tfrac {3}{2}}\log _{2}n$ , bara en konstant blandas antalet bitar av information kvarstår.