Ich habe ein Problem mit Daten die von Probanten sortiert wurden. Es geht dabei um 10 Sachen, die in die richtige Reihenfolge gebracht werden mussten. Soweit ich das verstehe, kann das als eine Permutation verstanden werden. Nun habe ich fuer jeden Probanten den Abstand zur richtigen Reihenfolge ermittelt und erhalte einen Durchschnittswert von ca. 25. Der moegliche Abstand von zwei 10er Permuationen liegt zwischen 0 und 50, aber der Mittelwert ist nicht 25, da bin ich mir sicher, da es weit mehr Permutationen gibt die einen grossen Abstand haben als einen kleinen. Ich wuerde gerne wissen, was der durchschnittliche Abstand der 3628800 moeglichen Permutationen bei 10 Zahlen ist.
Zur Veranschaulichung eben ein Beispiel mit 3 Zahlen. Nehmen wir an, dass die richtige Reihenfolge 123 ist. Dann haben die folgenden Permutationen folgenden Abstand: 123=0; 132=2; 213=2; 231=4; 312=4; 321=4 und der durchschnittliche Abstand ist 2.67. Gibt es eine Formel um diesen durschnittlichen Abstand zu ermitteln?
Mit freundlichen Gruessen und Dank fuer eine Antwort,
Monique
Ich habe ein Problem mit Daten die von Probanten sortiert
wurden. Es geht dabei um 10 Sachen, die in die richtige
Reihenfolge gebracht werden mussten. Soweit ich das verstehe,
kann das als eine Permutation verstanden werden.
Stimmt.
Den „Abstand“, für den auch du Zahlenwerte angibst, hast du nicht definiert und von den Ergebnissen her glaube ich auch nicht, dass es sich um eine Größe handelt, die dich weiter bringt.
Das Maß der Unordnung wird typischerweise über die Zahl der Inversionen definiert, d. h. wie oft kommt ein Element vor einem anderen, obwohl es eigentlich danach kommen sollte, bei einer Menge von 10 Elementen kann das binkoeff(10, 2) also 10*9/2 mal vorkommen (was die Anzahl der Paare angibt), bei 3 Elementen gibt es 3 solcher Paare, der Durchschnitt liegt bei 1,5 was ziemlich gut einleuchtet
I(123)= 0
I(132)= 1 (3 vor 2)
I(213)= 1 (2 vor 1)
I(231)= 2 (2 vor 1, 3 vor 1)
I(312)= 2 (3 vor 1…
I(321)= 3
die Frage ist nicht ganz trivial.
für eine gegebene Zahlenfolge der Länge n sind die positionen gegeben durch p_i. Für eine(!) Realisation einer bel. Permutation seien die Positionen derselben Zahlen gegeben durch a_i. Die Differenz ist dann d=sum(|p_i-a_i|) für i=1,…,n.
Deine gesuchte Grüße ist dann D=1/k*d_k wobei k=1,…,n! alle möglichen Permutationen abdeckt.
Man könnte jetzt einfach einen entsprechenden Datensatz simulieren und D ausrechnen oder man könnte sich überlegen, wieviele der n! Permutationen dasselbe d haben und so die Rechnung abkürzen. Dazu habe ich allerdings keine Idee, aber ein paper gefunden, dass sich in etwa mit der Frage beschäftigt und dir so vllt weitere Quellen aufzeigt: cdm.ucalgary.ca/index.php/cdm/article/viewPDFInterstitial/147/94
Grüße,
JPL
Hi Guidot,
aus dem Beispiel geht für mich klar hervor, dass es sich bei dem „Abstand“ um die minimale Anzahl der Paarvertauschungen geht durch die sich die (jede) Zielpermutation ausdrücken lässt. Offenbar wird aber _eine_ Zweierpermutation als 2 gezählt (und nicht als 1, was ein bisschen kontraintuitiv ist).
Die entscheidene Frage ist: Wievele Permutationen gibt es die sich durch m Zweiervertauschungen ausdrücken lassen? Dann muss man „nur noch“ den Mittelwert über alle möglichen m bilden.
Interessante Aufgabe, ich denke noch ein bisschen drüber nach…
Hallo
Erst einmal vielen Dank fuer die Antworten. Ich hatte auch schon ueberlegt, dass man wahrscheinlich mit einer Simulation zu dem gewuenschten Ergebnis kommen kann, aber da fehlt es mir leider auch an den noetigen Kenntnissen.
Ich habe bei meiner Internetsuche zu dem Thema auch schon festgestellt, dass man haeufig als Mass fuer die Unordnung einer Permutation die Anzahl der Paarvertauschungen angibt, aber das ist fuer Nicht-Mathematiker weniger intuitiv. Mein Forschungsgebiet ist die Sozialpsychologie und da werd ich nur leere Blicke sehen, wenn ich ein solches Mass fuer die Unordung benutze. Darum wuerde ich gerne mit dem Abstand als Mass arbeiten. Dieses Mass wird auch in manchen mathematischen Artikeln erwaehnt (siehe http://www.irstat.ir/Files/En/JIRSS/JIRSS3/7-Pan.pdf).
Die entscheidende Frage fuer mich ist also was die durchschnittliche Unordnung einer Reihe von Permutationen ist, gemessen als Abstand zur „identity permutation“.
Wenn ich diesen Wert habe, kann ich ermitteln ob meine Probanten signifikant besser abschneiden als man erwarten wuerde, wenn sie rein zufaellig antworten.
Vielen Dank fuer weitere moegliche Hinweise, wie ich diesen Mittelwert errechnen kann,
Monique
Wenn ich diesen [mittleren] Wert habe, kann ich ermitteln ob meine
Probanten signifikant besser abschneiden als man erwarten
wuerde, wenn sie rein zufaellig antworten.
Wenn du stat. testen willst reicht die Kenntnis der mittleren Unordnung nicht aus. Dazu musst du die Verteilung der Unordnung kennen. Diese kannst du mit Simaulationen recht gut herleiten. Dazu musst du nur eine programmierbare anwendung finden (z.B. R) und hier entweder für dein spezielles Problem alle Permutationen einer Kombi ausrechnen oder via Monte Carlo die Verteilng für eine vielzahl von verschiedenen möglichen Zahlenfolgen berechnen.
Grüße,
JPL
Hallo JPL
Oh, das stimmt natuerlich. Die Verteilung der Permutationen ist natuerlich keine Normalverteilung und das ist ja die Annahme der Tests die ich kenne. Hmm, dann ist das ganze wohl doch komplizierter als ich dachte .
Vielen Dank nochmal,
Monique
.