Erwartungswert Selectionsort

Neue Frage »

Studentu Auf diesen Beitrag antworten »
Erwartungswert Selectionsort
Hallo liebe Leute!

Ich beschäftige mich gerade mit Selectionsort und dabei stehe ich nun vor einem kombinatorischen Problem:

1) Wenn man mit einer (zufälligen) Permutation von startet, wird bei der ersten Iteration des Algorithmus das größte Element an die letzte Stelle gebracht, die Reihenfolge der anderen Elemente wird beibehalten. Dadurch erhält man , wobei eine Permutation von ist.
Zu zeigen ist nun, dass dies wieder eine zufällige Permutation ist. Dabei soll man sich überlegen, welche bzw. wieviele Permutationen nach der ersten Iteration eine vorgegebene Permutation liefern.

Meine Idee: Die Permutation, die dies liefern, sind genau jene, bei denen genau in der gewünschten Reihenfolge angeordnet sind und das größte Element n irgendwo beliebig dazwischen oder an den Rändern angeordnet ist. Es gibt also n solche Permutationen. Das es insgesamt n! Permutationen gibt, erhält man für die Wahrscheinlichkeit, dass eine bestimmte Permutation von eintritt, und das bedeutet wir haben eine Gleichverteilung, also ist die "kleinere" Permutation tatsächlich auch zufällig.


2) Durch (1) und Iterieren lässt sich schnell ein Ergebnis für die "erwartete Anzahl an Updates" beim Sortieren eines Felde der Länge n mit Selectionsort finden. Dies ist auszuführen.
Als "Update" wird dabei das Ereignis bezeichnet, dass beim Durchlauf ein zwischengepeichertes Maximum durch ein neues, größeres Maximum ersetzt wird.
Steht z.B. gleich von Beginn an das größte Element ganz rechts, so findet beim ersten Durchlauf, also dem, der das größte Element nach ganz rechts setzen soll, gar kein Update statt.

Meine Idee: Ich schaffe es leider nicht, (1) hier sinnvoll anzuwenden. Ich habe mir überlegt, wieviele Updates ich im 1. Durchlauf jeweils habe, je weiter das größte Element am Anfang links steht, aber das wird für mich ganz schnell unüberschaubar.
Daher hoffe ich, ihr habt einen Rat zu (2).

Danke im Voraus!
HAL 9000 Auf diesen Beitrag antworten »

1) Chapeau, das hast du perfekt erklärt. Freude


Zu 2) Wie du gesagt hast, gibt es Möglichkeiten für die Position der Zahl , nur eine davon ist bereits "richtig, in den anderen Fällen bedarf es eines Updates, im Mittel über alle Permutationen sind das also Updates. Das gilt ähnlich für die Positionen , usw. Daher benötigt man im Mittel



Updates (die Bezeichnung für die -te harmonische Zahl ist üblich).
Studentu Auf diesen Beitrag antworten »

1) smile Du hast mir schon mal was Ähnliches erklärt, das hat offensichtlich Früchte getragen. Augenzwinkern

2) Das ist mir jetzt leider zu schnell gegangen. Wie kommt man denn auf ? Was mir dabei unklar ist, ist, dass es ja, wenn z.B. die allergrößte Zahl an vorvorletzter Stelle steht (was Wahrscheinlichkeit 1/n hat), nicht unbedingt genau 1 Update braucht, sondern es auch sein kann, dass man zwei Updates braucht (wenn nämlich die Einträge an den letzten beiden Stellen absteigend geordnet sind)?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Wie kommt man denn auf ? Was mir dabei unklar ist, ist, dass es ja, wenn z.B. die allergrößte Zahl an vorvorletzter Stelle steht (was Wahrscheinlichkeit 1/n hat), nicht unbedingt genau 1 Update braucht, sondern es auch sein kann, dass man zwei Updates braucht (wenn nämlich die Einträge an den letzten beiden Stellen absteigend geordnet sind)?

Wir reden da erstmal nur über die richtige Positionierung der letzten Zahl - die anderen kommen später dran!

In einem von Fällen (besser gesagt: bei (n-1)! von n! Permutationen) steht die bereits richtig, d.h., in von Fällen benötigen wir ein Update (in dem einem Restfall kein Update),
die Wahrscheinlichkeit eines solchen Updates ist gleich . Dieser Wert ist auch gleichzeitig der Erwartungswert der Anzahl Updates nur für die letzte Position.

Dasselbe Spiel für die vorletzte Position: von Varianten benötigen ein Update, Erwartungswert für die Updateanzahl der -ten Position ist

usw.

Für die zweite Position benötigt 1 von 2 Varianten ein Update, das ist

Schließlich und letztlich die erste Position, die steht zwangsläufig bereits richtig, was aber auch über korrekt beschrieben wird.


Die Erwartungswerte aller Updateanzahlen für jede Position summiert ergibt den Erwartungswert der Gesamtanzahl (Linearität des Erwartungswertes).
Studentu Auf diesen Beitrag antworten »

Danke für deine Antwort!

Also lass mich das noch einmal wiederholen, weil ich kann es nicht ganz nachvollziehen:
Richtig steht die letzte Zahl, wenn sie die allergrößte ist. Die Wahrscheinlichkeit dafür beträgt (n-1)!/n!, weil für die n-1 ersten Stellen jede beliebige Permutation günstig ist. In diesem Fall findet gar kein Update statt.
Steht die allergrößte Zahl, n, aber an n-1-ter Stelle, dann findet genau ein Update statt. Da dabei die anderen n Elemente wieder jede beliebige Permutation haben können, beträgt die Wahrscheinlichkeit hierfür ebenfalls genau (n-1)!/n! und es findet genau ein Update statt. Dann ist die Wahrscheinlichkeit dafür aber doch 1/n und nicht (n-1)/n? verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Steht die allergrößte Zahl, n, aber an n-1-ter Stelle, dann findet genau ein Update statt. Da dabei die anderen n Elemente wieder jede beliebige Permutation haben können, beträgt die Wahrscheinlichkeit hierfür ebenfalls genau (n-1)!/n! und es findet genau ein Update statt. Dann ist die Wahrscheinlichkeit dafür aber doch 1/n und nicht (n-1)/n? verwirrt

Ja, und? Wenn die größte Zahl an den Stellen 1 ... (n-2) steht, ist doch auch jeweils ein Update nötig - willst du das ignorieren, oder was soll diese Versteifung auf Position (n-1). unglücklich

Naja, offenbar erkläre ich zu schlecht, das muss dann wohl ein anderer übernehmen.
 
 
Studentu Auf diesen Beitrag antworten »

Ja, ich habe gedacht, wir schauen uns erst mal das an, weil du geschrieben hast, wir reden erstmal nur über die richtige Positionierung der letzten Zahl.
Und meine Überlegung dafür war, dass ja n die letzte Zahl sein soll und wir uns daher anschauen, was für verschiedene Positionen von n passiert. Selbstverständlich ist mir klar, dass es noch unvollständig ist, wenn man nur mal n an letzter und an n-1-ter Stelle betrachtet, aber für andere Positionen von n wird es eben sehr unübersichtlich.

Nur kann es sein, dass du stattdessen gemeint hast, wir betrachten einfach erstmal nur die letzte Stelle und schauen, wieviele Updates es benötigt, um das gewünschte Element, n, dahinzubekommen? Dann ist die Wahrscheinlichkeit dafür, dass die richtige Zahl eh schon dort steht, gleich 1/n und in (n-1)/n Fällen müssen wir jedenfalls updaten.

Dann ist das schon einmal die Wahrscheinlichkeit, die du vorher geschrieben hast. (:
Für die vorletzte Position ist die Wahrscheinlichkeit, dass das richtige Element noch nicht dortsteht, dann entsprechend (n-2)/(n-1) usw.

Nur was für mich jetzt noch unklar ist, ist, warum (n-1)/n dann auch gleichzeitig der Erwartungswert der Anzahl Updates nur für die letzte Position sein muss. Wir haben ja bislang nur, dass die Wahrscheinlichkeit, dass das letzte Element auf jeden Fall durch ein anderes ersetzt werden muss, (n-1)/n ist.
Genau ein Update müssten wir für die letzte Stelle in dem Fall machen, dass n an vorletzter Stelle steht, für n an vorvorletzter Stelle muss man dann schon Fallunterscheidung bzgl. der letzten zwei Elemente machen, daher sehe ich noch nicht, wo die (n-1)/n erwarteten Updates herkommen?

EDIT: Vielleicht reden wir gerade über unterschiedliche Dinge, was ein "Update" ist. Ein Update ist nicht nur, wenn eine andere Zahl an eine Stelle geschrieben wird, sondern wenn wir z.B. 2431 haben, dann wird beim 1. Durchlauf zunächst max:=1 zwischengespeichert, dann mit 3 vergleichen, also neues max:=3 zwischengespeichert (1 Update) und und dann das max mit 4 verglichen und max:=4 zwischengespeichert (2. Update) und dann dieses mit 1 verglichen, wo kein Update mehr stattfindet, weil 4 größer ist als 1 und zum Schluss kommt 4 an die letzte Stelle.
Oder noch ein anderes Beispiel: für eine Liste mit 3 Elementen ist die erwartete Anzahl von Updates für die letzte Position 5/6, weil
123 --> kein Update
132 --> 1 Update
213 --> kein Update
231 --> 1 Update
321 --> 2 Updates
312 --> 1 Update
Insgesamt also 5 Updates, jede der Permut. hat Wahrscheinlichkeit 1/6.


P.S.: Quatsch, du bist einer der besten Erklärer, die ich "kenne"; ich stehe wohl eher gerade ziemlich auf der Leitung.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Studentu
Nur was für mich jetzt noch unklar ist, ist, warum (n-1)/n dann auch gleichzeitig der Erwartungswert der Anzahl Updates nur für die letzte Position sein muss.

Das ist bei jeder Indikator-Zufallsvariable (d.h. eine, die nur die Werte 0 oder 1 annehmen kann) so:

Aus folgt .

Im vorliegenden Fall betrachten wir die Indikator-Zufallsvariablen

... Anzahl nötiger Updates, nur um Position richtig zu stellen, unter der Voraussetzung, dass die Stellen bereits stimmen

Dann gilt für

... Anzahl nötiger Updates insgesamt

einfach und demzufolge .
Studentu Auf diesen Beitrag antworten »

Das ist mir klar, und da stimme ich dir natürlich zu. Der Erwartungswert dafür, dass ein anderer Wert an die letzte Stelle gehört als der, der zu Beginn dortsteht, ist (n-1)/n, weil das auch die Wahrscheinlichkeit ist.
Aber wie in meinem letzten Beitrag noch einmal klargestellt, haben wir eben eine Zufallsvariable, die NICHT NUR die Werte 0 und 1 annehmen kann, sondern es kann in jedem Durchgang (außer dem allerletzten, wo die unsortierte Liste nur mehr aus einem Element besteht und dem vorletzten Durchgang, wo die unsortierte Liste nur mehr aus zwei Elementen besteht) in jedem Durchgang MEHR ALS EIN UPDATE geben (nämlich für eine unsortierte Liste der Länge k beim ersten Durchgang höchstens k-1 Updates, beim zweiten Durchgang dann höchstens k-2 Updates usw. (worst case - wenn die Liste zu Beginn absteigend sortiert ist)).

Verstehst du, was ich meine? Ich habe die Definition von "Update" am Anfang des Threads wohl leider missverständlich ausgedrückt.
HAL 9000 Auf diesen Beitrag antworten »

Dann erklär doch endlich mal, wieviele Updates es benötigt, beispielsweise bei

2 5 1 3 4

die 5 an das Ende zu bringen - das hast du nämlich bisher nie getan. böse


Nach deinem Eröffnungsposting war ich davon ausgegangen, dass das nur ein Update kostet - egal ob du nun als Updateschritt einen Austausch meinst mit Ergebnis

2 4 1 3 5,

oder aber ein "nach hinten schieben" (d.h. alle dazwischen rutschen nach vorn)

2 1 3 4 5.


EDIT: Ich sehe gerade, dass du nachträglich einige deiner Beiträge oben nacheditiert hattest - das hatte ich alles nicht gelesen. Ist ja auch ein beschissener Stil, die Daten heimlich nachzuschieben. unglücklich
Studentu Auf diesen Beitrag antworten »

Hallo Hal9000,

tut mir sehr leid, dass ich da so Verwirrung gestiftet habe. Finger1
Die Beiträge habe ich jeweils noch vor deiner Reaktion darauf editiert, aber vlt. hattest du sie da schon gelesen.
Sollte ich in Zukunft lieber einen neuen Beitrag verfassen anstatt zu editieren oder wie lässt sich das kennzeichnen? Entschuldigung dafür! Ups

Also zu 2 5 1 3 4:

Im ersten Durchlauf benötigt man ein Update, weil zunächst max:=4 gesetzt wird und das dann durch max:=5 ersetzt wird und keine danach betrachtete Zahl größer ist als 5.

Beim zweiten Durchlauf (also dem für 2 4 1 3 5) benötigt man wieder ein Update, weil zunächst max:= 3 gesetzt wird und das dann durch max:=4 ersetzt wird und keine danach betrachtete Zahl größer ist als 4.

Beim dritten Durchluaf (also für 2 3 1 4 5) benötigt man wieder ein Update, weil zunächst max:= 1 gesetzt wird und das dann durch max:=3 ersetzt wird und keine danach betrachtete Zahl größer ist als 3.

Beim vierten Durchlauf (also für 2 1 3 4 5) benötigt man wieder ein Update, weil zunächst max:= 1 gesetzt wird und das dann durch max:=2 ersetzt wird.

Hier war es zufällig immer genau ein Update, aber z.B. für 2 5 1 4 3 wären es beim ersten Durchlauf zwei Updates, weil zunächst das max:=3 durch max:=4 ersetzt wird und dann max:=4 durch max:=5 ersetzt wird.
HAL 9000 Auf diesen Beitrag antworten »

Durch dieses andere Updatevorgehen (ich nehme an, bei jedem Updatevorgang wechseln die beiden Elemente ihre Plätze) ist nun natürlich auch 1) völlig in Frage gestellt: Betrachten wir dazu mal die Permutationen von 3 Elementen und betrachten die jeweils nötigen Updatevorgänge nur für das letzte Element 3, zählen diese Updatevorgänge (Anzahl in Klammern) und geben auch jeweils die erreichte Endpermutation an:

123 (0)
213 (0)
132 --> 123 (1)
231 --> 213 (1)
312 --> 213 (1)
321 --> 312 --> 213 (2)

Im Ergebnis haben wir die 5 Updatevorgänge, die du auch schon erwähnt hast, aber wir haben mitnichten für den "Rest" 1,2 vorn eine Gleichverteilung der Permutationen:

Wir haben zweimal 12 und viermal 21 - bei Gleichverteilung der Permutationen sollte je dreimal 12 und 21 herauskommen. Dadurch kann man

Zitat:
Original von Studentu
Zu zeigen ist nun, dass dies wieder eine zufällige Permutation ist.

mit einem beherzten Tritt in die Tonne befördern: Denn das hier

Zitat:
Original von Studentu
wird bei der ersten Iteration des Algorithmus das größte Element an die letzte Stelle gebracht, die Reihenfolge der anderen Elemente wird beibehalten

wird bei diesem Vorgehen nicht eingehalten. unglücklich

Das war auch einer der Hauptgründe für meine Verwirrung.
Studentu Auf diesen Beitrag antworten »

Danke für deine Antwort, Hal9000.

Aber deine Annahme, dass bei jedem Updatevorgang der Platz gewechselt wird, ist nicht richtig (das hätte ich nach alledem wohl auch noch einmal erklären sollen, tut mir leid):
Es wird zwar durchgegangen und immer wieder geupdatet, welches aktuell das gefundene max ist, aber mit diesem wird erst ganz zum Schluss vertauscht. Es findet also nur eine Vertauschung statt, nämlich mit dem Element, das nach Durchgehen der Liste gerade das max ist.
Dadurch müsste das mit der Zufälligkeit und Gleichverteilung eigentlich schon stimmen.
Nur 2) wird durch die Updates schwerer zu durchschauen.
Studentu Auf diesen Beitrag antworten »

Ich glaube, ich habe es jetzt:
Kann es sein, dass es z.B. beim 1. Durchlauf (also für die Liste n)
erwartete Updates sind, also allgemein für eine Liste der Länge m Updates (Summe der Wahrscheinlichkeiten, dass das l-te Element das Maximum der Elemente {l, ..., m} ist für l aus {1, ..., m-1}.
Und damit erhält man die Gesamtzahl erwarteter Updates als ?
Neue Frage »
Antworten »



Verwandte Themen

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