Erwartungswert und Varianz von Fehlständen

Neue Frage »

mariaeck Auf diesen Beitrag antworten »
Erwartungswert und Varianz von Fehlständen
Hallo,

unser Professor hat mir die Aufgabe aufgetragen den Erwartungswert und die Varianz der Anzahl aller Fehlstände einer rein zufälligen Permutation zu ermitteln.

Ich habe gerade einige Bücher gewälzt, aber so richtig verstehe ich seine Aufgabe nicht. Hat jemand eine Idee??

Gruß
Maria
AD Auf diesen Beitrag antworten »

OK, es geht um Fehlstände (wohl das Gegenteil von Fixpunkt?) von Permutationen. Aber mal bitte ganz exakt (!):

Was beschreibt in diesem Zusammenhang deine Zufallsgröße für ?
mariaeck Auf diesen Beitrag antworten »

die Aufgabenstellung ist exakt so wie ich sie geschrieben habe. Leider nicht mehr und nicht weniger.

Habe gerade geschaut. In Wikipedia ist der Fehlstand von Permutationen gut erklärt.
http://de.wikipedia.org/wiki/Permutation

Hoffe, dass mir jetzt jemand helfen kann.
Gruß
Maria
AD Auf diesen Beitrag antworten »

Zitat:
Original von mariaeck
die Aufgabenstellung ist exakt so wie ich sie geschrieben habe. Leider nicht mehr und nicht weniger.

Das kann ich mir schlicht und einfach nicht vorstellen, dass hier Symbole verwendet werden, die weder hier noch im Umfeld der Aufgabe erklärt werden. Ein wenig mehr solltest du dich schon anstrengen, die Aufgabe ordentlich darzulegen. Ansonsten kann ich dir nicht helfen, auch wenn die Aufgabe ganz interessant klingt. Aber ich bin der Ratespielchen bei oberflächlich rübergebrachten Problemstellungen so langsam leid.
mariaeck Auf diesen Beitrag antworten »

Also im Anhang steht die Aufgabe nochmal.

Habe eine Abschnitt dazu im Script gefunden. Da sind wir überhaupt noch nicht. Scheint es aber zu sein:

Einer Permutation der Zahlen 1,....,n ordnen wir für jedes j=2,....,n ihre Zahl der Fehlstände

b_j=h_j(a):=#{i:i<j,a(i)>a(j)} zu

Nun sei X eine rein zufällige Permutation von 1,...,n und ihre Fehlstandszahlen, mit Zielbereichen Da es insgesamt n! Permutationen gibt und die Abbildung nach bijektiv ist, gilt



Nach unserem Satz folgt, dass uniform auf verteilt ist und dass unabhängig ist.
Umgekehrt kann man aus unabhängigen, uniform verteilten eine rein zufällige Permutation gewinnen.
AD Auf diesen Beitrag antworten »

Na das ist doch schon mal was, danke.

Jetzt kann man anfangen, über das Problem nachzudenken - später mehr.


EDIT ("später"):

Ok, also ist einfach die zufällige Anzahl der Fehlstände unter den Positionspaaren der Permutation.

Zitat:
Original von mariaeck
Nach unserem Satz folgt, dass uniform auf verteilt ist und dass unabhängig ist.

Na das ist doch schon mehr als die halbe Miete - wäre wirklich schade, wenn du uns das vorenthalten hättest. Augenzwinkern

Für diese diskrete Gleichverteilung auf gilt

und ,

schaut man nach oder kann es auch leicht selbst ausrechnen. Für die Summe folgen nun die gewünschten Werte einerseits aus der Linearität des Erwartungswertes



sowie andererseits für die Varianz aus der Unabhängigkeit der Größen - dann addieren sich die Einzelvarianzen zur Gesamtvarianz:

.

Bleibt nur noch einsetzen und die entstehenden Summen ein wenig vereinfachen.

-----------------------------------------------

Also alles wichtige an Infos auf den Tisch packen, umso schneller geht's. smile
 
 
Leopold Auf diesen Beitrag antworten »

Ich bin die Sache einmal elementar und naiv angegangen.

Es sei die Menge der Permutationen der ersten natürlichen Zahlen mit der Gleichverteilung.

Die Zufallsgröße ordne jedem die Anzahl der Fehlstände zu, und es sei der Erwartungswert von .

Dann gilt



Für habe ich mir einmal die Permutationen lexikographisch mit dem jeweiligen aufgeschrieben. Mit genauem Hinschauen und ein bißchen Rechnen habe ich die folgende Rekursion gefunden:



was sofort auf eine Rekursion für die führt:



Da die Differenz linear in ist, ist quadratisch in , womit man ohne großen Aufwand eine explizite Formel bekommt.

Und dasselbe Vorgehen erlaubt es auch, die Varianz der zu berechnen. Mit etwas Aufwand habe ich



erhalten. Und sollte da dasselbe herauskommen wie beim Verfahren mit den , wäre ich es zufrieden.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »