Markov-Kette des Mischen von Karten

30.11.2016, 17:49

Dukkha

Markov-Kette des Mischen von Karten

Hallo zusammen,

Ich komme bei folgender Aufgabe nicht mehr weiter:

Sei $\begin{eqnarray*} D=\{1,2,\dots,52\} \end{eqnarray*}$ ein Deck mit 52 Karten. Wir mischen pro Zeitschritt $\begin{eqnarray*} n\in \mathbb{N} \end{eqnarray*}$ zwei Karten zufällig und gleichverteilt. Wie sieht die Markov-Kette aus? (Edit: Gemeint ist der Zustandsraum und die Übergangsmatrix)

Ich habe das ganze mal im Fall $\begin{eqnarray*} D=\{a,b,c\} \end{eqnarray*}$ betrachtet und die Markov-Kette gezeichnet. Ich kriege einen Graphen mit $\begin{eqnarray*} 6 \end{eqnarray*}$ Knoten, weil es insgesamt $\begin{eqnarray*} 3\cdot 2\cdot 1 \end{eqnarray*}$ Permutationen gibt. Das würde bedeuten, ich hätte insgesamt $\begin{eqnarray*} 52! \end{eqnarray*}$ Knoten bei $\begin{eqnarray*} 52 \end{eqnarray*}$ Karten!

Betrachte ich aber nur, wieviele Karten sich noch in der Anfangsposition befinden. Dann würde dass "nur" eine Markov-Kette von 52 Knoten ergeben. Leider ist das aber immer noch ziemlich gross.

Die dritte Sichtweise wäre wohl zu zählen, wieviele Karten noch ihre alten Nachbarn (die des Anfangszustandes $\begin{eqnarray*} S_0 \end{eqnarray*}$ ) haben, was ja das "perfekte" mischen wäre. Leider habe ich keine Ahnung, wie ich das modellieren soll.

30.11.2016, 18:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dukkha
Betrachte ich aber nur, wieviele Karten sich noch in der Anfangsposition befinden.

Hmm, die Karte kann aber durch einen Mischvorgang wieder in die Anfangsposition gelangen...

Du meinst es wahrscheinlich eher so, ob Karten überhaupt mal in einem Mischpaar waren.

Alle deine Modellierungsansatze haben was für sich - die Frage ist doch am Ende, was du dann mit der Kette beabsichtigst. Im übrigen würde ich bezweifeln, dass das Kriterium "alle Karten wurden mindestens einmal angefasst" ausreichend ist für perfektes Mischen: Nehmen wir als Beispiel mal, dass man in den ersten 26 Einzelmischvorgängen jeweils verschiedene Karten erwischt, dann hat man eine Permutation der 52 Karten vorliegen, die nur aus Zweierzyklen besteht - nicht gerade das, was man unter einer Gleichverteilung unter allen Permutationen versteht. Und auch, wenn man mehr als diese 26 Einzelmischungen benötigt, wirkt dieser Effekt nach.

Neue Frage »

Antworten »

Markov-Kette des Mischen von Karten

Verwandte Themen