Simulieren einer Poisson-Verteilung am Computer durch Gleichverteilung

Neue Frage »

Hubert1965 Auf diesen Beitrag antworten »
Simulieren einer Poisson-Verteilung am Computer durch Gleichverteilung
Ich stehe vor der Aufgabe, für einen Softwaretest das Verhalten mehrerer Menschen zu simulieren, die eine Internetseite mit einer temporären Fehlermeldung aufrufen. Es geht um die Dauer, die gewartet wird, bis der Mensch die Seite neu lädt. Also:

  1. Mensch lädt eine Seite aus dem Internet
  2. es erscheint die Meldung »Fehler! Versuchen sie später erneut«
  3. Mensch wartet
  4. Mensch lädt die Seite erneut


Diese Wartedauer (Dauer von Punkt 3) ist das Ergebnis eines Zufallsprozesses, der einen bestimmten Erwartungswert und eine bestimmte Varianz bzw. Standardabweichung hat. Wären die zu erwartenden Wartedauern innerhalb eines bestimmten Intervalls gleichverteilt, könnte ich die Wartedauer ganz einfach durch



berechnen, wobei und die Grenzen des Intervalls und, und wo eine Computerfunktion ist, die bei jedem Aufruf mit gleichverteilter Wahrscheinlichkeit eine rationale Zahl zwischen 0 und 1 ausspuckt.

Einen normalverteilten Zufallsprozess kann ich mit Hilfe der Zwölferregel in ausreichender Qualität simulieren:



Dabei wird die Funktion zwölfmal hintereinander aufgerufen und die 12 Ergebnisse werden summiert. Da jeder Aufruf einen Erwartungswert von 0,5 hat, hat diese Summe einen E.w. von 6, der abgezogen wird um ihn auf 0 zu setzen. Die Standardabweichung dieser Summe ist bereits genau 1, diese Verteilung ist also normiert. Eine beliebige andere Normalverteilung erhält man nun, indem man dieses Ergebnis mit der gewünschten Standardabweichung multipliziert und dann den gewünschten Erwartungswert addiert.

In der Formel steht übrigens absichtlich zwölfmal , weil im Fall von die Funktion nur einmal (anstatt 12-mal) aufgerufen wird, und das Ergebnis dann nicht annähernd normalverteilt, sondern gleichverteilt wäre.

Nun ist aber die Verteilung der Wartezeiten eines realen Users weder gleichverteilt noch normalverteilt. Ich halte eine Poissonverteilung für besser geeignet, weil damit keine Werte kleiner als 0 geliefert werden können, und weil ihre Schiefe auch besser dem entspricht, was ich von der zu modellierenden Verteilung annehme.

Allerdings ist eine Poissonverteilung keine stetige Verteilung, sondern eine diskrete, was mich wieder zweifeln lässt, ob sie tatsächlich ein geeignetes Model ist.

Dessen ungeachtet habe ich aber leider keine Ahnung, durch welchen Algorithmus ich auf einem Computer ohne großen Aufwand eine solche Verteilung in ähnlich guter Qualität annähern kann, wie oben beschrieben im Fall der Normalverteilung.

Ich suche einen solchen Algorithmus und würde gerne wissen, ob die Poissonverteilung tatsächlich ein geeignetes Modell ist.
rg Auf diesen Beitrag antworten »
RE: Simulieren einer Poisson-Verteilung am Computer durch Gleichverteilung
Mit einer Poisson-Verteilung koennte man modellieren, wie viele Reload-Requests (sagen wir pro Minute) beim Server eintreffen. Da kommen ja diskrete Werte (0, 1, 2, ...) bei raus. Die Zeit zwischen zwei Reload-Requests waere dann exponentialverteilt.

Einen einfachen Algorithmus nach Knuth findet man hier:

en.wikipedia.org/wiki/Poisson_distribution

Eine ganze Sammlung fertiger Routinen zur Erzeugung von Zufallszahlen mit vorgegebener Verteilung gibt's hier:

boost.org/doc/libs/1_55_0/doc/html/boost_random/reference.html
HAL 9000 Auf diesen Beitrag antworten »

Genau so ist es, Exponentialverteilung. Die kann man z.B. per Inversionsmethode simulieren:

Ist stetig gleichverteilt auf , so ist eine -verteilte Zufallsgröße.

Aber Obacht, für einfach im Programm rand() einsetzen, kann ziemlich schiefgehen: Während in der Theorie ist, besteht bei Zufallszahlengeneratoren (je nach Implementierung) der rand()-Funktion die Gefahr, dass dort tatsächlich 0 erscheint - und das wäre bei x=-ln(rand())/lambda ja ziemlich blöd. Und diese Gefahr ist sehr real, z.B. haben primitive Implementierungen von rand() nur eine Periode von bzw. , allerdings sollte man derartige Zufallszahlengeneratoren bei einer Simulation eh nicht nehmen. Augenzwinkern
Hubert1965 Auf diesen Beitrag antworten »
RE: Simulieren einer Poisson-Verteilung am Computer durch Gleichverteilung
Eine Menge von vielen Ereignissen, bei denen die Zeit, die zwischen einem willkürlich gewählten Nullpunkt und dem Auftreten eines einzelnen Ereignisses exponentialverteilt ist (z.B. radioaktiver Zerfall einzelner Atome) führt in ihrer Gesamtheit zu poissonverteilten Zählungen pro Zeiteinheit (Ticks pro Sekunde beim Geigerzähler). Das heißt aber nicht, dass die zeitlichen Abstände zwischen zwei aufeinanderfolgenden Ereignissen (also zwischen zwei Ticks) exponentialverteilt sind. Denn eine Exponentialverteilung würde bedeuten, dass der häufigste zeitliche Abstand 0 ist, und dass die Wahrscheinlichkeit, einen bestimmten Zeitabstand zu messen, umso kleiner ist, je größer dieser Abstand ist.

Das trifft auf die Verteilung der zeitlichen Abstände aber nicht zu. Wenn ich eine Probe eines radioaktives Material habe, das aus nur 10 Atomen besteht, wobei die Atome eine Halbwertszeit von einem Jahr haben, ist die Wahrscheinlichkeit, dass zwei aufeinanderfolgende Zerfallsereignisse innerhalb von 59 Minuten stattfinden nicht größer als die Wahrscheinlichkeit, dass sie innerhalb einer Stunde stattfinden, sondern kleiner. Umgekehrt ist die Wahrscheinlichkeit, dass zwischen zwei aufeinanderfolgenden Ereignissen 100 Jahre vergehen größer als die Wahrscheinlichkeit, dass 101 Jahre vergehen. Es gibt also irgendwo zwischen 1 Stunde und 100 Jahre ein Maximum in der Wahrscheinlichkeitsverteilung (nämlich in der Größenordnung von 1 Monat). Eine Exponentialverteilung hätte ihr Maximum aber bei genau 0 Sekunden.

Mein Denkfehler war, dass ich die (stetige) Verteilung der zeitlichen Abstände zweier aufeinanderfolgenden Signale fälschlicherweise für eine (diskrete) Poissonverteilung gehalten habe, weil ihre Graphen eine ähnliche Form haben.

Ich möchte das zeitliche Verhalten eines Users mit dieser (oder einer ähnlichen) Verteilung simulieren. Also mit einer Verteilung, die bei 0 kein Maximum hat, sondern bei 0 (und bei allen negativen Werten) den Wert 0 hat, von dort zu einem Maximum ansteigt, und danach wieder stetig fällt, bis sie bei unendlich großen Zeitdauern wieder auf 0 zurückfällt.

Welche Verteilung hat diese Eigenschaften?

Danke übrigens für die Links, aber sie helfen mir leider nicht weiter. Der Wikipedia-Link beschreibt nur die Poisson-Verteilung (die ja leider nicht die gesuchte Verteilung ist), und liefert auch keinen Anhaltspunkt der mit bei der Simulation dieser Verteilung helfen könnte. Der andere Link ist die Beschreibung einer Programmbibliothek, in der beschrieben ist, wie man fertig programmierte Module in ein C++-Programm einfügen kann. Da ich nicht in C++ (sondern in diesem Fall in Perl) programmiere, nützt mir diese Bibliothek nichts. Was ich bräuchte, wäre eine Beschreibung, wie man solche Verteilungen mit einfachen Mitteln selbst programmieren kann, nicht wie man fertige Module, die das können, in ein Programm einbindet. Aufgrund der Aufgabenstellung ist auch eine exakte Nachbildung einer bestimmten Verteilung gar nicht erforderlich. Es genügt, wenn sie die oben genannten Bedingungen erfüllt.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Hubert1965
Wenn ich eine Probe eines radioaktives Material habe, das aus nur 10 Atomen besteht, wobei die Atome eine Halbwertszeit von einem Jahr haben, ist die Wahrscheinlichkeit, dass zwei aufeinanderfolgende Zerfallsereignisse innerhalb von 59 Minuten stattfinden nicht größer als die Wahrscheinlichkeit, dass sie innerhalb einer Stunde stattfinden, sondern kleiner.

Ja klar, das ist einfach die Monotonie des W-Maßes, das trifft auf jede Verteilung zu - auch die Exponentialverteilung. Was du hier also anführst, spricht in keinster Weise gegen die Exponentialverteilung. unglücklich

Was du hättest vergleichen müssen ist die Wahrscheinlichkeit, ob die Zeit zwischen zwei Zerfallsereignissen

a) zwischen 0 und 1 Stunde,
b) zwischen 1 und 2 Stunden

liegt. Und da ist die Wahrscheinlichkeit bei a) größer - auch bei deinem Zerfallsbeispiel, wo im übrigen (auch wenn du es nicht wahrhaben willst) tatsächlich Exponentialverteilung vorliegt.


Zitat:
Original von Hubert1965
Eine Menge von vielen Ereignissen, bei denen die Zeit, die zwischen einem willkürlich gewählten Nullpunkt und dem Auftreten eines einzelnen Ereignisses exponentialverteilt ist [...] Das heißt aber nicht, dass die zeitlichen Abstände zwischen zwei aufeinanderfolgenden Ereignissen (also zwischen zwei Ticks) exponentialverteilt sind.

Doch, das bedeutet es! Zumindest wenn die Ereignisse i.i.d. exponentialverteilt sind, d.h. unabhängig und mit demselben Parameter:

Sind die Einzelzeiten -verteilt, so ist die Zeitdauer zwischen dem -letzten und dem -letzten Ereignis -verteilt.


Das heißt, folgende beiden Vorgehensweisen bei einer Simulation sind vollkommen äquivalent:

(A) Simuliere Realisierungen einer -verteilten Zufallsgröße. Dann ordne diese Werte aufsteigend, dies seien dann mit .

(B) Simuliere gemäß , dann gemäß und setze , dann gemäß und setze usw. letztlich gemäß und setze .

Dann haben die Vektoren und dieselbe Verteilung. smile
Huggy Auf diesen Beitrag antworten »
RE: Simulieren einer Poisson-Verteilung am Computer durch Gleichverteilung
Welcher Verteilung die Wartezeit in der Realität (näherungsweise) folgt, lässt sich sicher nur experimentell feststellen. Es würde mich nicht wundern, wenn die Zeit bis zum ersten neuen Versuch näherungsweise exponentialverteilt wäre. Bei der Wartezeit für weitere Versuche mag das anders aussehen.

Zitat:
Original von Hubert1965
Ich möchte das zeitliche Verhalten eines Users mit dieser (oder einer ähnlichen) Verteilung simulieren. Also mit einer Verteilung, die bei 0 kein Maximum hat, sondern bei 0 (und bei allen negativen Werten) den Wert 0 hat, von dort zu einem Maximum ansteigt, und danach wieder stetig fällt, bis sie bei unendlich großen Zeitdauern wieder auf 0 zurückfällt.

Welche Verteilung hat diese Eigenschaften?

Es gibt diverse Verteilungen, die deiner Vorstellung genügen, manchmal zumindest innerhalb gewisser Parameterbereiche. Eine davon ist die Lognormalverteilung. Rechnerisch lässt sich eine lognormalverteilte Zufallsgröße leicht aus einer normalverteilten Zufallsgröße erzeugen. Ist normalverteilt, dann ist



lognormalverteilt.

Normalverteilte Zufallszahlen lassen sich nicht nur nach der von dir erwähnten 12-er-Regel erzeugen. Weitere Methoden findest du hier:

https://de.wikipedia.org/wiki/Normalvert...r_Zufallszahlen
 
 
Hubert1965 Auf diesen Beitrag antworten »

Du hast recht. Nachdem ich meinen Kommentar geschrieben hatte, habe ich aus ausführlich darüber nachgedacht, ob das stimmt was ich geschrieben habe, und bin zu dem Schluss gekommen, dass es nicht stimmt. Auch die Zeitabstände sind exponentialverteilt.

Danke für deine Erklärungen.

Trotzdem möchte ich meine Simulierten Test-User nicht exponentialverteilt feuern lassen.

Nocheinmal die Aufgabenstellung:
  1. Mensch lädt eine Seite aus dem Internet
  2. es erscheint die Meldung »Fehler! Versuchen sie später erneut«
  3. Mensch wartet
  4. Mensch lädt die Seite erneut

Ich glaube nicht, dass die Zahl der User, die zwischen 0 und 0,1 Sekunden lang warten, größer ist als die Zahl jener, die zwischen 0,1 und 0,2 Sekunden lang warten. Ich suche eine Verteilung, dis bei 0 den Wert 0 hat, dann monoton und stetig auf ein Maximum ansteigt (wobei ich die Lage des Maximums durch einen Parameter steuern kann), und dann ebenso monoton und stetig abfällt.
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Hubert1965
Ich suche eine Verteilung, dis bei 0 den Wert 0 hat, dann monoton und stetig auf ein Maximum ansteigt (wobei ich die Lage des Maximums durch einen Parameter steuern kann), und dann ebenso monoton und stetig abfällt.

Ein Beispiel für eine solche Verteilung habe ich dir doch genannt, nämlich die Lognormalverteilung.
Hubert1965 Auf diesen Beitrag antworten »

Danke Huggy!

Sonderbarerweise habe ich deinen Beitrag nicht bemerkt als ich auf HALs Posting geantwortet habe. Aber jetzt habe ich ihn gelesen, und bedanke mich dafür, denn er löst mein Problem. Danke!


Noch ein Nachsatz zu den im Link behandelten Methoden zur Erzeugung einer annähernd normalverteilten Zufallsvariable:

Bei einem Aufruf der Funktion rand() wird - abgesehen vom notwendigen Aufwand für den Funktionsaufruf selbst - im Wesentlichen nur eine Restklassenmultiplikation durchgeführt:



Zwölf Aufrufe dieser Funktion erfordern also nur 12 Restklassenmultiplikationen. Die anderen Methoden kommen zwar mit weniger Aufrufen von rand() aus, erfordern danach aber die Berechnung transzendenter Funktionen (Wurzelziehen, Logarithmus, Winkelfunktion usw.) die in der Durchführung wesentlich mehr Aufwand als nur 12 Multiplikationen machen.

Die fehlende Unabhängigkeit aufeinanderfolgender Pseodozufallszahlen ist natürlich in vielen Fällen ein Problem, doch für die vorliegende Aufgabe ist das kein Problem.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Hubert1965
erfordern danach aber die Berechnung transzendenter Funktionen (Wurzelziehen, Logarithmus, Winkelfunktion usw.)

Du redest von der Box-Muller-Methode ? Ich bevorzuge die verwandte Polar-Methode von Marsaglia:

Hier genügen ein Logarithmus- und ein Wurzelfunktionsaufruf zur Erzeugung zweier normalverteilter Werte. Allerdings muss man ggfs. mehrfach gleichverteilte auswürfeln, bis man welche mit gefunden hat. Schlechter worst-case im Zeitverhalten, aber sehr viel besserer mid-case gegenüber Box-Muller. Augenzwinkern

Zitat:
Original von Hubert1965
Bei einem Aufruf der Funktion rand() wird - abgesehen vom notwendigen Aufwand für den Funktionsaufruf selbst - im Wesentlichen nur eine Restklassenmultiplikation durchgeführt:


Leider haben lineare Kongruenzgeneratoren eine ganze Reihe negativer Eigenschaften. Ich favorisiere momentan eher den Mersenne-Twister: Etwas mehr Rechenbedarf, und deutlich mehr Speicherbedarf (2,5kByte, was im PC aber kein Problem sein dürfte), aber deutlich bessere "Qualität".


Zitat:
Original von Hubert1965
Die fehlende Unabhängigkeit aufeinanderfolgender Pseodozufallszahlen ist natürlich in vielen Fällen ein Problem, doch für die vorliegende Aufgabe ist das kein Problem.

Das ist sehr wohl ein Problem: Die Aussage, dass 12 aufeinander folgende rand() in der Summe (und dann -6) näherungsweise eine standardnormalverteilte Zufallsgröße ergeben, basiert auf der Unabhängigkeit der 12 Werte...
rg Auf diesen Beitrag antworten »

@Hubert1965: Auch fuer Perl-Programmierer gibt es fertige, schon getestete und optimierte Zufallszahlengeneratoren in allen moeglichen Geschmacksrichtungen. Ideal zum Rumspielen und Experimentieren. Guckst Du z.B. hier:

search.cpan.org/~grommel/Math-Random-0.72/Random.pm

search.cpan.org/~cgpan/Math-Random-MTwist-0.17/lib/Math/Random/MTwist.pm
Neue Frage »
Antworten »



Verwandte Themen

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