Gewichteter Zufall

[Luckie]

Es gibt einen neuen Artikel auf meiner Homepage zum gewichteten Zufall: http://www.michael-puff.de/Artikel/2...eterzufall.php

Zitat:

Kleine Vorgeschichte oder die Problemstellung

Vor der Zwischenprüfung zum Fachinformatiker für anwendungsentwicklung, wollte unser Lehrer mit uns noch mal ein paar Prüfungsaufgaben durchgehen. Damit nicht immer die selben Schüler drankommen nämlich, jene die die Antwort wissen und sich melden bzw. damit nicht vom Lehrer willkürlich Schüler darngenommen werden, hatte unser Lehrer eine Idee. Und zwar sollten wir in der ersten halben Stunde des Unterrichts ein Programm entwicklen, welches es ihm ermöglichte zufällig einen Schüler auszuwählen, aber mit der Einschränkung, dass ein Schüler, der gerade dran gewesen ist, mit einer geringeren Wahrscheinlichkeit noch mal von dem programm ausgewählt wird, als ein Schüler, der noch keine Frage beantworten musste.

Zusammengefasst sollte also folgendes Programm entwickelt werden: Aus einer Liste von Namen solte zufällig ein Name gezogen werden. bei wiederholtem ziehen eines Namens, soll der zuvor ermittelte Name mit einer geringeren Wahrscheinlichkeit gezogen werden, als ein Name, der noch nicht gezogen wurde.

[stahli]

Hallo Luckie,

ich wäre es über mehrfaches Random angegangen:

- Liste mit 30 Schülern
- X := Anzahl Schüler;
- N := 2;
- for I := 1 to N do X := Random(X)
- Treffer := Schüler(X)
- Treffer an das Ende de Liste

Je höher N ist um so frühere Treffer sind zu erwarten.

stahli


PS. Mathe ist mir zu kompliziert :?

[Nikolas]

Bei dieser Idee hängt aber das Ergebnis von der Initalisierung der Liste ab.
In der Aufgabenstellung wird aber verlangt, dass nur derjenige, der als letzter geantwortet hat, eine kleinere Wahrscheinlichkeit hat als alle anderen. Das ist somit nicht gegeben.
Auch ist es so, dass man nach einer Antwort für die nächsten paar Fragen immer noch eine geringere Wahrscheinlichkeit hat, da man erst wieder in den höheren Bereich der Liste geschoben werden muss.

Die Idee mit der Wurzel ist zwar nett, aber erfüllt nicht ganz die Aufgabenstellung.

[Khabarakh]

Was imo aus dem Artikel nicht ganz klar wird: deine Lösung benachteiligt ja nicht die Schüler, die sich oft gemeldet haben, sondern die, die sich vor kurzem gemeldet haben.
Ich denke einmal, dass es so auch gedacht war; um jedenfalls Ersteres zu erreichen, müsste jedem Schüler nur eine Auswahl-Wahrscheinlichkeit p zugeordnet werden, die bei n Schülern anfangs 1 / n beträgt. Wenn er dann nach einer Meldung z.B. nur noch halb so oft aufgerufen werden soll, muss natürlich erst einmal seine eigene Wahrscheinlichkeit p1 um 50% gesenkt und zusätzlich die Wahrscheinlichkeiten aller anderen Schüler um .5 * p1 / (n - 1) erhöht werden. Die Auswahlfunktion könnte dann so aussehen:

Delphi-Quellcode:

// Rückgabewert: Index des gewählten Eintrags
// Summe der Wahrscheinlichkeiten sollte 1 betragen
function RandomItem(aProbabilities: array of Real): Integer;
var
  r: Real;
begin
  r := Random;
  Result := 0;
  while Result < Length(aProbabilities) do
  begin
    r := r - aProbabilities[Result];
    if r < 0 then
    begin
      Dec(Result);
      Exit;
    end;
    Inc(Result);
  end;
  Dec(Result); // im Zweifelsfall der letzte Eintrag
end;

[add]

Zitat:

Zitat von Nikolas

In der Aufgabenstellung wird aber verlangt, dass nur derjenige, der als letzter geantwortet hat, eine kleinere Wahrscheinlichkeit hat als alle anderen. Das ist somit nicht gegeben.

Könnte man so verstehen, aber die Aufgabenstellung ist unklar:

Zitat:

dass ein Schüler, der gerade dran gewesen ist, mit einer geringeren Wahrscheinlichkeit noch mal von dem programm ausgewählt wird, als ein Schüler, der noch keine Frage beantworten musste.

Es wird nichts über die Schüler ausgesagt, die schon einmal früher dran waren. Deshalb würde ich die Aufgabenstellung auch nicht zu wörtlich nehmen, es bleibt also ein ziemlicher Spielraum für Deutungen.
[/add]

[Medium]

Bei gewichtetem Zufall habe ich spontan an eine Zuordnungsliste gedacht. Alle Personen bekommen einen je gleich großen Zahlenbereich zwischen 0 und 1 zugewiesen. Mit einer Zufallszahl geht man dann in diese Liste, und schaut in wessen Bereich sie liegt. Anschließend wird die Liste neu Aufgebaut, wobei der Bereich der zuletzt gezogenen Person um einen Faktor verkleinert wird, während die Bereiche der anderen prozentual gleichmäßig vergrößert werden, so dass alle Bereich in Summe wieder 1 ergeben.
Das System ist allerdings dann gesprengt, wenn jemand so oft hintereinander gezogen wird, dass sein Bereich 0 wird (dank Ungenauigkeiten von Floats). Die Wahrscheinlichkeit dafür dürfte aber sehr gering sein, und ließe sich durch Einführen eines Minimums leicht beheben.
Dies ließe sich sogar finetunen, da man über den Faktor bestimmen kann, wie stark ein gezogener "bestraft" werden soll, und sogar ob dies linear, prozentual, oder nach welchem Gesetz auch immer statt finden soll. Ebenso ist die Verteilung des frei gewordenen Bereichs anpassbar, so dass z.B. jemand mit großem Bereich stärker profitieren würde als jemand im Mittelfeld.

Was ein solches Verfahren generell bewirkt ist, dass die Gleichverteilung auf alle Zufallszahlen eines Seeds bereits für eine kleinere Untermenge wählbar schnell forciert wird.

[sirius]

Durch die Wurzel hast du einfach eine quadratische Verteilungsfunktion abgebildet.

Edit (wurde grad rausgerissen):
Ich wollte noch ergänzen, dass dies eine lineare Dichtefunktion ergibt. Also anstatt der Glockenkurve bei der Normalverteilung, hast du eine lineare Funktion.

[Luckie]

Zitat:

Zitat von sirius

Durch die Wurzel hast du einfach eine quadratische Verteilungsfunktion abgebildet.

Bist du da sicher? Es müsste eine nach rechts verschobene Normalverteilung sein, bei der die Werte auf der linken Seite sanft ansteigen und dann auf der rechten Seite steil abfallen.

Zitat:

Ich wollte noch ergänzen, dass dies eine lineare Dichtefunktion ergibt. Also anstatt der Glockenkurve bei der Normalverteilung, hast du eine lineare Funktion.

Hast du mal Grafiken dafür parat?

[sirius]

Grafiken? Schwer.

Wenn du dir die beiden Bilder auf Seite 1 ansiehst. Dann hast du links die dichtefunktion und rechts die Verteilungsfunktion. Von links nach rechts kommst du über Integration (was auch in der Formel untendrunter steht) und von rechts nach links über Differentation.
Wenn du für eine bestimmte Verteilung einen zufälligen Wert haben möchtest, dann nimmst du dir die Verteilungsfunktion (rechts) und einen gleichverteilten Zufallswert (random von 0 bis 1). Mit diesem Wert gehst du in die y-Achse der Verteilungsfunktion und liest den x-Wert ab. Fertig.

Das bedeutet, du bildest mathematisch die Umkehrfunktion der Verteilungsfunktion. Wenn du jetzt als Umkehrfunktion der Verteilung eine Wurzelfunktion hast, ist die Verteilungsfunktion selbst eine quadratische. Und damit ist die Dichtefunktion (Ableitung der quadratischen Funktion) linear.

[Luckie]

Ah, ok, dann habe ich jetzt zumindest eine Erklärung. Mit dem Verstehen hapert es noch ein wenig, aber das ist Licht am Horizont. ;)

[Jelly]

Jetzt bewegen wir uns bereits ganz nah am elementaren Standbein der Monte Carlo Simulation. Auch dort wird mit Verteilerfunktionen gearbeitet. Da das mal Thema meiner Diplomarbeit war, hätte ich dazu auch einiges an Dokumentation. Wenns denn interessiert, so kann ich dazu heut abend was hier ins Forum schreiben.