Gleichverteiltes Ziehen

18/01/2010 - 16:17 von Robert Hartmann | Report spam
Hallo zusammen,

Wahrscheinlich stehe ich auf einem sehr stochastischen Schlauch.

Folgende Zeile eines Pseudocodes zum stochastischen Zàhlen
làsst mich grübeln:


a <- uniform(M)
/*Für eine Menge X liefert uniform(X) ein Element e gleichverteilt aus
X, ohne an X etwas zuàndern*/


Wie kann wohl uniform(M) implementiert werden,
wenn M eine nicht leere endliche Menge ist,
deren Màchtigkeit man nicht kennt?


Gruß Robert
 

Lesen sie die antworten

#1 Markus Wichmann
18/01/2010 - 17:14 | Warnen spam
Robert Hartmann () schrieb:
Hallo zusammen,

Wahrscheinlich stehe ich auf einem sehr stochastischen Schlauch.

Folgende Zeile eines Pseudocodes zum stochastischen Zàhlen
làsst mich grübeln:


a <- uniform(M)
/*Für eine Menge X liefert uniform(X) ein Element e gleichverteilt aus
X, ohne an X etwas zuàndern*/


Wie kann wohl uniform(M) implementiert werden,
wenn M eine nicht leere endliche Menge ist,
deren Màchtigkeit man nicht kennt?




do {
I = $RANDOM; //Annahme: RANDOM_MAX > |M|
} while (!exists(M[I]));
return M[I];

Aber was hat deine Frage mit dem Kommentar zu tun? Man kann auch bei
Kenntnis der Màchtigkeit uniform() so implementieren, dass die Menge
nicht geàndert wird.

Wo wir gerade dabei sind: Ich habe eine Zufallsgröße X, die über die
natürlichen Zahlen bis X_max gleichverteilt ist. Jetzt möchte ich eine
Zufallsgröße Y erzeugen, die über die natürlichen Zahlen bis Y_max
gleichverteilt ist. Wie mache ich das?

Natürlich weiß ich: Falls Y_max > X_max ist, ist die Aufgabe nicht
lösbar, denn es gibt nicht genug Werte im Wertebereich von X um den
Wertebereich von Y mit Werten zu füllen. Man könnte natürlich X mehrfach
ziehen und die Ergebnisse addieren, aber das würde ja zu einer
Ungleichverteilung führen (siehe zweimal Würfeln, wo die 7 die hàufigste
Zahl ist). Mit Multiplikation werden die Primzahlen > X_max nicht
erwischt.

Und bevor einer vorschlàgt, für Y_max < X_max doch einfach den Rest zu
benutzen (also Y := X mod Y_max): Geht nur für X_max mod Y_max = Y_max - 1.
Ansonsten gibt es für die Zahlen zwischen 0 und X_max mod Y_max ein X
mehr, für das gilt: Y = X mod Y_max.


Gruß Robert



Tschö,
Markus
Progress (n.): Process through which USENET evolved from smart people in
front of dumb terminals to dumb people in front of smart
terminals.

news://freenews.netfront.net/ - complaints:

Ähnliche fragen