Mischen als stochastischer Prozess

Jede Kartenspielerin weiß, dass das Kartenglück launisch ist. An manchen Abenden scheint es wie verhext: Es will sich einfach kein gutes Blatt einstellen. Nach der dritten Runde mit nur wenigen Trümpfen auf der Hand fragt man sich dann vielleicht, ob es daran liegt, dass der Geber sich keine Mühe beim Mischen gegeben hat? Die Theorie zu stochastischen Prozessen liefert hierzu eine erstaunliche Aussage: Nach einer bestimmten Anzahl $n$ von Mischschritten kann man davon ausgehen, dass der Kartenstapel mit $N$ Karten sehr gut gemischt ist.¹ Wird die Zahl von $n$ Mischschritten aber unterschritten, bleibt der Kartenstapel sehr schlecht gemischt. $n$ ist dabei von der Ordnung $\log{N}$.

Um das zu erläutern, betrachte man das Mischverfahren Riffle Shuffle: Der Kartenstapel wird in der Mitte geteilt und dann wieder zufällig zusammengemischt. In unserem Modell wir die jeweils nächste Karte auf dem Zielstapel zufällig entweder aus dem ersten oder aus dem zweiten Teilstapel gezogen. Das idealisiert den Vorgang, wie er beim Mischen von Hand stattfindet, denn dort ist nicht wirklich gegeben, dass die Auswahl der Quelle einer Karte jeweils unabhängig ist von der vorhergehenden Auswahl. Dennoch dürfte das Ergebnis sehr ähnlich ausfallen.

Die Funktion splitandmix! verwendet zwei Iteratoren, von denen einer die erste Hälfte des ursprünglichen Stapels durchläuft und der andere die zweite Hälfte. Es werden solange Karten vom ersten Iterator übernommen, bis eine Zufallszahl zum ersten Mal größer als $0,5$ ist. Dann wechseln die Iteratoren. Falls schließlich einer der Iteratoren erschöpft ist, werden die restlichen Karten vom anderen Iterator übernommen.

	function splitandmix!(dest::T, source::T) where T<:Vector{Int}
		p = lastindex(source)
		hp = div(p, 2)
		itcurrent = Iterators.Stateful(source[1:hp])
		itother = Iterators.Stateful(source[hp+1:p])
		i = firstindex(dest)
		while !isempty(itcurrent)
			rand() < 0.5 || begin itcurrent, itother = itother, itcurrent end
			dest[i] = popfirst!(itcurrent)
			i += 1
		end
		itcurrent = itother
		while i <= lastindex(dest)
			dest[i] = popfirst!(itcurrent)
			i += 1
		end
		dest
	end

Ein Objekt der Struktur Pile enthält einen Vektor mit den Positionen der Karten. Durch die Definition von iterate wird aus einem Pile ein iterierbares Objekt.

	mutable struct Pile
        pilesize::Int # number of cards
        shufflesteps::Int # steps in a round of shuffling
        vpos::Vector{Int} # positions of the cards (state)
	end
	
	function Pile(pilesize::Int, shufflesteps::Int)
		vpos = collect(1:pilesize)
		Pile(pilesize, shufflesteps, vpos)
	end

	let vposlast = Int[]
		global function iterate(p::Pile)
			p.vpos = collect(1:p.pilesize)
			vposlast = p.vpos
			return(p, 1)
		end

		global function iterate(p::Pile, step)
			splitandmix!(vposlast, p.vpos)
			p.vpos, vposlast = vposlast, p.vpos
			if step >= p.shufflesteps
				return nothing
			else
				return(p, step + 1)
			end
		end
	end

Die Funktion sample legt ein dreidimensionales Array an und zählt, wie häufig eine Karte an den verschiedenen Positionen nach jedem Schritt des Mischverfahrens angetroffen wird.

	function sample(pile::Pile, ncycles::Int, nmsg = 12)
		pilesize = pile.pilesize
		field = zeros(Int, pilesize, pile.shufflesteps, pilesize)
		nmsgstep = div(ncycles, nmsg)
		steptomsg = nmsgstep

		@inbounds for cycle in 1:ncycles
			for (s, p) in enumerate(pile)
				for (pos, card) in zip(sortperm(p.vpos), 1:pilesize)
					field[pos, s, card] += 1
				end
			end
			if steptomsg == 0
				println("cycle: ", cycle)
				steptomsg = nmsgstep
			end
			steptomsg -= 1
		end
		field
	end

Die folgenden Abbildungen zeigen, wie sich die Positionen von Karten aus einem Stapel von 32 Karten verändern. Es ist die Wahrscheinlichkeit abgebildet, eine Karte an einer bestimmten Position zu finden. Im ersten Schritt, bevor das Mischen begonnen hat, trifft man die Karte immer an der Position, die ihrer Nummer entspricht, d.h. Karte 1 an Position 1, Karte 15 an Position 15, und so weiter. Schon nach zweimaligem Mischen, vor Schritt drei sind die Karten beträchtlich gewandert, vor allem, wenn ihre Ausgangsposition am Ende (Karte 32) oder in der Mitte (Karte 15) war. Bei Schritt neun sind die Karten an jeder der Positionen gleich häufig anzutreffen:

Der Abstand von der Gleichverteilung über alle Karten dient als Maß für den Erfolg des Mischvorgangs. Das Diagramm zeigt, wie sich dieser Abstand im Laufe des Mischvorgangs verändert:

Man erkennt deutlich, dass das Mischen schon nach wenigen Schritten zum gewünschten Erfolg führt. Der Stapel mit 32 Karten ist schon nach fünf Schritten sehr gut gemischt, danach lässt sich keine Verbesserung mehr erzielen. Vergrößert man den Stapel, erhöht sich die Zahl der benötigten Schritte zum Mischen. Die Zahl der Karten wurde von Stapel zu Stapel um den Faktor 6,25 vervielfacht. Die Verschiebung der Kurve von Stapel 2 zu Stapel 1 ist aber in etwa gleich groß wie die Verschiebung der Kurve von Stapel 3 zu Stapel 2. Damit bestätigt der Versuch die Vorhersage der Theorie, dass die Zahl der benötigten Schritte propotional ist zum Logarithmus der Zahl der Karten.

	julia> VERSION
	v"1.1.0"

Startseite

1. Michael Scheutzow: Stochastische Modelle. Vorlesungsskript. TU Berlin 2017. ↩