wie misst man unordnung bzw. zufälligkeit?

    • mcmoe
      mcmoe
      Bronze
      Dabei seit: 11.04.2006 Beiträge: 3.838
      hallo,

      ich schreibe zu studienzwecken z. zt. an einem programm, welches karten-mischverfahren in livegames simuliert und das deck visualisiert.

      hier als beispiel ein einfacher riffle-shuffle:



      man kann mit dem auge bei so einer visualisierung sehr gut feststellen, wie "durcheinander" oder zufällig ein kartendeck gemischt ist. allerdings würde ich das noch gerne mit irgendwelchen zahlen stützen.

      man sieht ja z.b. dass der grad der zufälligkeit in bezug auf die ausgangssequenz bei einem riffle-shuffle eher mäßig ist. hier findet man karten ähnlichen wertes aber unterschiedlicher suits nacheinander vor.

      welche ansätze gibt es dafür? ich bin mir nämlich nicht sicher, woran ich so eine unordnung überhaupt messen sollte.

      mir ist aus dem chemie- und physik-unterricht noch der begriff "entropie" bekannt. kann man darauf irgendwie aufbauen?


      grüße
      mcmoe


      ps: mir ist natürlich klar, dass ein riffle, ein box, etc. live niemals "theoretisch perfekt" ausgeführt wird …
  • 5 Antworten
    • SlowLarry
      SlowLarry
      Bronze
      Dabei seit: 07.04.2006 Beiträge: 948
      Ja, auf dem Entropiebegriff könnte man aufbauen, aber das Ergebnis gibt dann wohl nicht ganz das wieder, was Du erwartest, da nämlich das Deck nach dem Durchlaufen eines deterministischen Algorithmus wieder in einer ganz bestimmten Ordnung vorliegt, d.h. jede Karte mit Wahrscheinlichkeit 1 an einer ganz bestimmten Position liegt.

      Mathematisch kann man die Shannon- oder Informationsentropie definieren als

      S = - Summe_k,n( p(k,n)*log2(p(k,n)) )

      wobei p(k,n) die Wahrscheinlichkeit angibt, dass die Karte k an der Stelle n im Deck liegt.

      Offenbar gilt S = 0 für alle deterministisch gemischten Decks.
      Ein echter Entropiezuwachs, bzw. Informationsverlust ist nur mit einem Mischverfahren zu erreichen, das eine Zufallskomponente enthält, so dass es Karten k gibt, mit Wkten 0 < p(k,n) < 1.

      Im perfekt gemischten Deck findet sich jede Karte mit Wkt 1/52 an jeder Position im Deck. Die maximale Entropie beträgt also

      S = - 52² * 1/52 * log2(1/52) ~ 296,4 bit
    • mrhiccup
      mrhiccup
      Bronze
      Dabei seit: 21.05.2006 Beiträge: 51
      Vielleicht könnte man die realisierte Mischung mit der perfekten Mischung vergleichen. Unter der perfekten Mischung verstehe ich ein Verfahren welches jeder Karte absolut zufällig eine neue Position zuordnet. Für die perfekte Mischung können wir Erwartungswerte berechnen und diese dann mit Durchschnittswerten unserer realisierten Mischung vergleichen.

      Man betrachtet wie viel Abstand jede Karte zu ihrer alten Position hat.

      Bei der perfekten Mischung wird bei n Karten jede Karte um erwartete n/4 Plätze verschoben. (Ob das stimmt mit n/4 bin ich mir nicht sicher, kann man bestimmt in einem Statistik Buch nachschlagen)

      Nach dem Mischen kann man nun gucken um wie viele Plätze jede Karte verschoben wurde und bildet den Durchschnitt.

      Je näher der Wert an n/4 liegt, desto besser wurden dann die Karten gemischt.

      Besser wäre noch wenn man die Abstandsänderung der Karten zueinander vergleicht. Dann vergleicht man die erwartete Abstandsänderung der perfekten Mischung und die realisierte Abstandsänderung zwischen allen Karten Paaren und bildet den Durchschnitt.

      Ich glaub im Prinzip könnte es so funktionieren, sind aber glaube ich noch Fehler drin, bin aber jetzt zu faul weiter drüber nach zu denken.
    • mcmoe
      mcmoe
      Bronze
      Dabei seit: 11.04.2006 Beiträge: 3.838
      das problem ist aber, dass man durch die messung der entfernung einer karte von ihrem ursprungsort keine sequenzen und muster erfasst.

      menschen sind eben sehr gut darin wiederkehrende muster zu erkennen und zu memorieren. wenn wir zum beispiel den riffle-shuffle 26x anwenden drehen wir das deck einmal um. d. h. karte 1 ist an position 52 und umgekehrt.
      für die "äußeren" karten würde man einen sehr hohen unordnungswert erreichen, für die in der mitte einen stetig kleineren. ein mensch erkennt bei so einer mischung aber sofort das muster und kann die dazugehörige sequenz ableiten.

      im oberen beispiel (1x riffle) sieht man in der visualisierung auch eine sehr simples muster, aus dem man sich eine sequenz herleiten kann. die karten sind aber relativ weit von ihren ursprungsorten entfernt.

      mich würde es eben sehr stark interessieren wie man auch sequenzen und muster in so eine unordnungs-analyse einbeziehen könnte.

      vielen dank aber schon einmal für eure gedanken. der input bringt mich schon mal weiter.
    • mcmoe
      mcmoe
      Bronze
      Dabei seit: 11.04.2006 Beiträge: 3.838
      *push* :)

      hat denn jemand ne idee wo ich sonst irgendwo im internetz nachfragen könnte?
    • SlowLarry
      SlowLarry
      Bronze
      Dabei seit: 07.04.2006 Beiträge: 948
      Nun, eine Wunderformel zur Mustererkennung gibt es eben nicht.
      Insgesamt geht Dein Vorhaben ja auch in Richtung Kryptoanalyse, denn Du versuchst ja, aus Klartext (geordnetes Deck) und Chiffrat (gemischtes Deck) den Verschlüsselungsalgorithmus und dem Schlüssel zu ermitteln (das Mischverfahren und ggf. dessen Parameter).
      In diesem Gebiet gibt es sicherlich einige Ansätze zur Erkennung simplerer Permutationsverfahren, habe aber nicht näher danach gesucht.

      Eine einfache Größe zur Erkennung linearer Ordnungen ist natürlich der Korrelationskoeffizient. Allerdings ist der bei nichtlinearen Mischungen unbrauchbar und scheitert z.B. schon wenn die Mischung zu gleichen Teilen aus einer auf- und absteigenden Sequenz besteht.

      Etwas besser und sehr sensibel für auf- und absteigende Sequenzen ist folgende Klasse von Verfahren:
      Man wählt (zufällig oder nach einem bestimmten System) eine bestimmte Zahl (z.B. 4 oder 1) Karten aus. Anschließend geht man von vorne bis hinten durch das Deck und legt lückenlos nach unten oder oben passende Karten an. Zum Schluß sollten sich die einzelnen Reihen zum kompletten Deck verbinden lassen.
      Zu messen ist, wie viele Durchläufe des Decks man hierzu benötigt.

      Eine etwas elaborierterer Kandidat für das "Zufallsmaß" könnte dies sein:

      http://en.wikipedia.org/wiki/Markov_chain_mixing_time

      Habe mich allerdings auch damit noch nicht näher beschäftigt.