Ca. x Events auf Zeitspanne verteilen

SideWinder

Ich bin mir nicht sicher ob ich richtig liege, würde mich gerne über Korrektur/Feedback/Bestätigung freuen.

Ich möchte pro Minute ca. x Events (habe x_mean und eine Standardabweichung x_sigma) auf eine Zeitspanne von einer Minute verteilen. Kurz als Background: Das ganze soll "incoming requests" simulieren.

Das System hat eine tick()-Methode die jede Sekunde aufgerufen wird und in der ich nun entscheiden muss ob ich ein neues Event erzeuge oder nicht (oder evtl. sogar mehrere Events?).

Frage: Wie bekomme ich nun in tick() einen so verteilten boolean aus diesen Eingangsparametern der mir mitteilt ob ich ein neues Event erzeugen soll?

Ich kann mir natürlich mean/sigma per Tick statt per Minute ausrechnen.
Dann kann ich mir einen Random double holen und in die Normalverteilung einsetzen und bekomme eine Anzahl an Events in dieser Minute (=y). D.h. ich muss ein Event mit der Wahrscheinlichkeit y : 60 erzeugen?

Wie komme ich hier jemals in den Genuss zweier gleichzeitiger Events? Ist die Methode überhaupt Käse?

MfG SideWinder

SeppJ

SideWinder schrieb:

Frage: Wie bekomme ich nun in tick() einen so verteilten boolean aus diesen Eingangsparametern der mir mitteilt ob ich ein neues Event erzeugen soll?

Wenn mehrere Events pro Tick möglich sein sollen, dann solltest du wohl besser die Anzahl der Events für diesen Tick zurück geben.

Wie komme ich hier jemals in den Genuss zweier gleichzeitiger Events? Ist die Methode überhaupt Käse?

Ich nehme deine Methode mit der Tickfunktion jetzt einmal als gegeben an, bloß mit obiger Verbesserung. Ob diese gut oder schlecht ist, kommt drauf an, was du genau erreichen möchtest. Jedenfalls ist es auch mit dieser Methode möglich, die gewünschte Verteilung zu erzeugen, wenn du nur wüsstest, welche Verteilung du möchtest. Leider sagst du nicht, wie die Events verteilt sein sollen. Um eine diskrete Zufallszahl mit einer bestimmten (berechenbaren) Verteilung zu erzeugen würde ich eine Zufallszahl R zwischen 0 und 1 erzeugen. Dann

double P = 1;
unsigned number_of_events = 0;
do
 P -= Probability(number_of_events++, x_mean, x_sigma);
while (P > R);
return number_of_events - 1;

Natürlich nur, wenn bloß eine kleine Anzahl an Events pro Ticks möglich ist. Falls die number_of_events bei deiner Verteilung groß werden kann, sollte man die Zahl der Events zum gezogenen R besser durch Nutzung der kumulativen Wahrscheinlichkeitsfunktion einkreisen.

Alles Ungetestet!

Nur mit dem Erwartungswert und der Standardverteilung hast du noch nicht deinen ganzen Prozess beschrieben. Du brauchst dazu eine ganze Verteilungsfunktion.

Für Ankunftsprozesse kannst du zb mal wiki lesen über Poisson- und Exponentialverteilung lesen:

http://de.wikipedia.org/wiki/Exponentialverteilung#Beziehung_zur_Poisson-Verteilung
http://de.wikipedia.org/wiki/Poisson-Verteilung#Kaufhauskunden

Wenn du annimmst, dass die Zeit zwischen zwei Ereignissen Exponentialverteilt ist, brauchst du auch nicht immer pollen, ob ein neues Ereignis eingetreten ist. Einfach nach jedem Ereigniss auswürfeln, wann das nächste passiert.

Im allgemeinen würde ich annehmen, dass niemals zwei Ereignisse exakt gleichzeitig eintreten. Die Wahrscheinlichkeit dafür ist 0 (weil bei allen kontinuierlichen Wahrscheinlichkeitsverteilungen die Wahrscheinlichkeit, dass ein Wert *exakt* angenommen wird, 0 ist). Falls das für dich aber eine Anforderung ist, würde ich die Zeiten zwischen zwei Ereignissen diskretisieren und entsprechend alle Zeitabstände 0 <= dt <= epsilon als "gleichzeitig" annehmen.

SideWinder

Hauptsache ich führe die Simulation 100x durch und am Ende entsprechen die insgesamt generierten Events der Simulationen der Normalverteilung die durch x_mean/x_sigma gegeben ist.

Die Events innerhalb einer Simulation sollten zufällig verteilt sein, also es kann ruhig auch mal alles in der ersten Hälfte ankommen, im Durchschnitt aber wohl irgendwas in die Richtung gleichverteilt, aber eben auch nicht immer genau gleichverteilt...

Wie geht man das an? Gleichverteilung nehmen und zufällige +/- dazurechnen?

MfG SideWinder

SeppJ

Du musst immer noch genauer definieren, was du mit zufällig verteilt meinst. Verteilungen gibt's viele und (fast) alle haben einen Durchschnitt und eine Varianz. Damit meinen ich und Mups nicht, wie die Ereignisse über die Zeit verteilt sind. Das nahmen wir schon an, dass du es nicht unnötig verkomplizieren möchtest und eine mögliche Zeitabhängigkeit der Verteilung nicht mit reinbringst. Du musst aber noch angeben, wie die Verteilung der Ereignisse pro Zeitschritt (also pro Tick) sein soll. Da du explizit nach mehreren Ereignissen pro Tick fragst, ist wohl nicht die Bernoulliverteilung gemeint. Da kann man nämlich nur 0 oder 1 pro Tick bekommen. Was wir wissen müssen ist, wie die Anzahl der Ereignisse pro Tick verteilt ist. Also wie soll sich die Wahrscheinlichkeit 2 Ereignisse pro Tick zu bekommen zu der Wahrscheinlichkeit für 1 Ereignis verhalten? Und 3? Und so weiter. Wenn du diese Verteilung benennen kannst, dann guckst du einfach Mittelwert und Varianz nach und rechnest dann rückwärts wie die Parameter der Verteilung genau aussehen müssen. Denn das was du mit dem Tick-Prozess beschreibst ist einfach nur das oftmalige ziehen aus dieser Verteilung. Dies ist nicht das Problem. Das ist genau das was Mittelwert, Varianz und die höheren Momente beschreiben. Das was interessant ist, ist die Verteilung pro Tick.

Wenn du einfach nicht weißt, was du nehmen sollst, dann sag ich mal pauschal: Nimm eine diskrete Gleichverteilung, also dass die Anzahl der Ereignisse pro Tick gleichverteilt zwischen einem wählbaren a und b liegt. Damit kannst du jeden Mittelwert und jede Varianz einstellen, da du zwei unabhängige Parameter hast. Wenn sie dir nicht passt, sag genauer warum, dann können wir dich beraten. Ein möglicher Einwand wäre beispielsweise, dass dies ein absolut unnatürlicher Prozess ist, dass beispielsweise (bei einem gewünschten Durchschnitt von 50 und einer Varianz von 850) 100 Ereignisse pro Tick genau so häufig vorkommen wie 0 Ereignisse. Aber das war dir angeblich ja egal, wenn bloß hinterher der Durchschnitt stimmt.

SeppJ hat ja die Problematik sehr fein erklärt. Ohne zu wissen, was du anwendungstechnisch simulieren willst, kann dir niemand eine wirklich gute Antwort geben.

Ein ganz wichtiger Punkt ist, zu entscheiden, ob du tatsächlich mehrere Ereignisse pro Tick zulassen willst. Das macht vieles komplizierter. Soll es eine feste Obergrenze von Ereignissen pro Tick geben? Oder sollen beliebig viele pro Tick möglich sein?

Ohne jetzt deine Anforderungen zu kennen, mache ich trotzdem mal einen Vorschlag, der wahrscheinlich für "normale" Anwendungen passen dürfte.

Ein Bernoulli-Prozess ( http://de.wikipedia.org/wiki/Bernoulli-Experiment ) geht davon aus, dass in jedem Tick mit Wahrscheinlichkeit p genau ein Ereignis eintritt und mit (1-p) nicht eintritt. Mit der Binomialverteilung kannst du dann die Wahrscheinlichkeit ausrechnen, dass k Ereignisse in n Ticks auftereten ( http://de.wikipedia.org/wiki/Binomialverteilung ). Unter bestimmten Annahmen kannst du die Binomialverteilung durch die Poisson-Verteilung ( http://de.wikipedia.org/wiki/Poisson-Verteilung ) approximieren. Wenn das geht, ist die Zeit t zwischen zwei Ereignissen exponentialverteilt ( http://de.wikipedia.org/wiki/Exponentialverteilung ).

Wenn du nun annimmst, die Zeit t sei exponentialverteilt, dann kannst du nach dem Auftreten eines Ereignisses die Zeit bis zum nächsten Ereignissen "auswürfeln". Aus dieser Abfolge von Zeitpunkten, wann Ereignisse auftreten, kannst du natürlich auch ableiten, wie viele Ereignisse im jeweiligen Tick auftreten.

Alternativ kannst du vermutlich direkt in jedem Tick mit der Poisson-Verteilung herausfinden, wie viele Ereignisse in diesem Tick auftreten. Das sollte genau das gleiche Ergebnis liefern wie der Ansatz über die Exponentialverteilung. In beiden Fällen ist die Anzahl der Ereignisse pro Tick beliebig groß, aber es ist sehr unwahrscheinlich, dass sehr viele Ereignisse auf einmal auftreten.

Falls du es einfacher magst, und eine feste Obergrenze der Ereignisse pro Tick akzeptierst, teilst du jeden Tick in "Unterticks" auf. In jedem Untertick tritt mit fester Wahrscheinlichkeit ein Ereignis ein. Das würfelst du entsprechend oft, summierst auf und bekommst das die Anzahl der Ereignisse in dem Tick.

Ein Problem bleibt: Du möchtest Erwartungswert *und* Varianz unabhängig einstellen. Das erscheint mir für Ankunftsprozesse ungewöhnlich; alle von mir vorgeschalgenen Verfahren haben nur einen unabhängigen Parameter.

Wenn du tief in die Materie einsteigen willst: Es gibt vermutlich beliebig viele verschiedene Modelle für die unterschiedlichen möglichen Anwendungen....

Prof84

Die Poisson-Verteilung wäre auch meine erste Wahl.

Noch als Nachtrag: Mit den Informationen, die wir haben, würde ich es so machen:

const double lambda = 5.0; // Rate
const double dt     = 0.1; // Zeitintervall

double next_event = 0.0;   // Zeit bis zum naechsten Ereignis

double exp_rand() // Exponentialverteilte Zufallszahl
{
   double r = - log(double(rand()) / RAND_MAX) / lambda;
	return r;
}

void tick_init()
{
	next_event = exp_rand();
}

int tick()
{
	int c = 0;
	next_event -= dt;
	while(next_event < 0.0) {
		++c;
		next_event += exp_rand();
	}
	return c;
}

lambda ist die Rate Ereignisse pro Zeiteinheit.

Bei Verwendung einer Exponentialverteilung für die Wartezeiten sollte man diese eventuell rechts und links zensieren, um extrem kurze und extrem lange Zeiten zu vermeiden. Anstatt des Zensierens von links könnte man auch einfach eine konstante Mindestzeit addieren.

Benutzername_ schrieb:

Bei Verwendung einer Exponentialverteilung für die Wartezeiten sollte man diese eventuell rechts und links zensieren, um extrem kurze und extrem lange Zeiten zu vermeiden. Anstatt des Zensierens von links könnte man auch einfach eine konstante Mindestzeit addieren.

Ob sowas sinnhaft ist, bekommen wir erst heraus, wenn SideWinder uns mehr Informationen gibt, welche Randbedingungen für seine Simulation gelten sollen. Vorher wissen wir nichtmal, ob ein Poisson-Prozess überhaupt das richtige für ihn ist.

ps: Noch ein Link zum Thema: http://de.wikipedia.org/wiki/Ereigniszeitanalyse