ubuntuusers.de

Hallo.

Ich habe folgendes Problem: Ich habe einen Topf, in dem sich 1000 Kugeln in 5 unterschiedlcihen Farben befinden. Diese haben jeweils eine unterschiedlcihe Wahrscheinlichkeit gezogen zu werden (z.B. weil sie unterschiedliche haufig in dem Taopf vorhanden sind oder eine unterschiedliche Groesse haben). den Wert fur die Wahrscheinlichkeit habe ich gegeben.

Nun moechte ich gerne 100 dieser Kugel ziehen, aber jedes mal nachdem ich eine kugel gezogen habe, wird diese Kugel wieder zurueckgelegt, und der Topf durchmischt. Nun moechte in entsprechend der anfanghaufigkeiten, eine zufaellig Anzahl an Kugeln jeder Farbe ziehen, so dass die Summe der Kugeln eben 100 ergibt.

Damit ich nicht 100mal ziehen muss, kann ich anhand der Haufigkeiten am Anfang eine multinomial-Verteilung errechnen, aus der ich einen Punkt (unter Beruecksichtigung der MultinomialVerteilung) rausziehe, der Dann wieder einen Satz von Haufigkeiten enthaelt. Somit bekomme ich direkt einen neuen Satz an Haufigkeiten nach dem Ziehen. Ich moechte also also einen Satz von Haufigkeiten an die Funktion uebergeben

• zustand^[1] = 10 // blau (im original 100 individuen)

• zustand^[2] = 20 // rot (im original 200 individuen)

• zustand^[3] = 30 // gruen (im original 300 individuen)

• zustand^[4] = 25 // gelb (im original 250 individuen)

• zustand^[5] = 15 // schwarz (im original 150 individuen)

zurueck bekomme ich dann einen neuen Array mit haufigkeiten der z. so aussehen koennte

• zustand_neu^[1] = 8 // blau

• zustand_neu^[2] = 21 // rot

• zustand_neu^[3] = 29 // gruen

• zustand_neu^[4] = 26 // gelb

• zustand_neu^[5] = 16 // schwarz

Ich habe das die werte jetzt mal diskret angegeben, da die binomial-verteilung ja eine diskrete verteilung ist. Man koennte ja eventuell auch wahrscheinlichkeiten uebergeben (.1, .2, .3, .25, .15) und muesste sie dann einfach mit der Zahl der zu ziehenden Kugel multiplizieren (in diesem Falle 100)

Die Multinomial-Objekte (wie z.B. die des BLOG-Packetes) die ich bisher gefunden habe, haben mir abei keine Moeglichkeit gegeben dass du berechnen, was ich moechte, bzw. es war mir nicht ersichtlich, dass es geht.

Hat jemand eine Loesung fuer das Problem?

Gruesse und Danke

Ehrlich gesagt kapiere ich nicht wirklich Dein Problem! Was genau sollst / willst Du denn nun simulieren mit dem Programm? Versuche das doch noch einmal klar und einfach auf den Punkt zu bringen.

Nur zu Deinem Verständnis, wo mein Unverständnis liegt: Bei so einem Problem denkt man eben zunächst daran, dass man mit dem PC eben möglichst viele Ziehungen machen will, um dann die Ergebnisse später zu analysieren (z.B. das Mittel über alle Ziehungen bilden). Damit kann man empirisch überprüfen, ob die theoretische Verteilung auch im Experiment nachgewiesen werden kann.

Genau das scheinst Du aber ja nicht zu wollen - daher kapiere ich nicht, was das Ziel des simulierten Ziehens sein soll!

Also, zunaechst einmal: ich moechte nur eine einzige Rechenoperation selbst durchfuehren. Diese Zahl Beschreibt mir allerdings mehrere Ziehungen (hier hatte ich 100 genannt.)

Sagen wir, in meinem Topf habe ich jetzt auch nur 100 Kugeln, die ich alle mehrfach ziehen kann.

• zustand^[1] = 10 // blau

• zustand^[2] = 20 // rot

• zustand^[3] = 30 // gruen

• zustand^[4] = 25 // gelb

• zustand^[5] = 15 // schwarz

Eigentlich wurde ich jetzt intervalle fuer die einzelnen Zustaende erzeugen,, dann einhundert (gleichverteilte) Zufallszahlen zwischen 1 und 100 erzeugen, und schauen in welches Intervall diese Zufallszahl faellt. Das sind allerdings 100 Schritte die ich durchfuehren muss. Ich kann das ganze doch in eine Mehrdimensionale Wahrscheinlichkeitsverteilung (bin mir nich ganz sicher ob man das wirklich so nennt - bin kein Mathematiker) zugrunde legen. Nach den Oben gennanten Vorraussetzungen waere das eine "Multinominale Zufallsverteilung", in der der Ort der groessten Wahrscheinlichkeit derjenige mit den Koordinaten (10, 20, 30, 25, 15) ist. Nun moechte ich Zufaellig einen Punkt in dieser Verteilung auswaehlen (Am Haufigsten wird da natuerlich der Punkt mit den Koordinaten (10, 20, 30, 25, 15) auftreten, wenn ich das "Experiment" einine male wiederhole). Von diesem Punkt moechte ich nun die Koordinaten haben.

Ich koennte jetzt z.B. auch die Koordinate (100, 0, 0, 0, 0) ziehen, aber das ist eher selten. Diese Koordinta ewurde bedeuten, dass ich von den ganz seltenen blauben 100 Stuck gezogen habe, von allen anderen aber keine Einzige.

Ich glaube die erste erklaerung war wirklich etwas verwirrend.

Gruesse

So, hatte mal Lust auf die Schnelle das Ziehen in Python zu simulieren ☺

Code

Edit: Ich habe Deine erneute Erklärung nur schnell überflogen und das auch noch nicht ganz gerafft auf die Schnelle. Werd's mir noch mal angucken die Tage.

So wie ich es beim ueberfliegen wahrgenommen habe, hast du die Kugel tatsaechlich gezogen. Bei mir muesste das in etwas so aussehen

 * zustand[1] = 10 // blau
 * zustand[2] = 20 // rot
 * zustand[3] = 30 // gruen
 * zustand[4] = 25 // gelb
 * zustand[5] = 15 // schwarz

// erzeugt die MultiNomiale Wahrscheinlichkeitsverteilung
MultinomialObject testObjekt = new MultinomialObject(zustand);

// waehlt zufaellig eine neue Koordinate in der mehrdimensionalen Verteilung aus
int neueKoordinaten[] = testObjekt.randomizeNewKoordinate();

/*
in neueKoordinaten stehen nun neue Werte fuer die einzelnen Farben der Baelle.
berucksichtigt beim ziehen wurden hierbei die Haufigkeiten der Baelle zu beginn.
*/

Gruesse

Sven

Ein interessantes Problem, fürwahr. Aber viel zu kompliziert.

Laß es uns ersmal vereinfachen. Mit 2 Farben wäre es zu einfach, denn wenn ich 10 Kugeln habe, davon 4 weiße und 6 schwarze, und ziehe 2 weiße, dann brauche ich keine weitere Information - die 8 anderen müssen dann schwarz sein.

Nehmen wir also 3 Farben, rgb, und die Anzahlen 1, 2, 3. Zusammen 6 Kugeln, und ich ziehe 3 mal.

Ich ziehe vielleicht 3*r: rrr
Oder rbb - die Reihenfolge spielt ja eigentlich keine Rolle. Ich könnte alle möglichen Kombinationen aufschreiben, und alphabetisch sortieren (hier mit Reihenfolge):

rrr
rrg
rrb
rgr
rgg
rgb
grr
...
ggg
....
bbb

Es gibt 27 Möglichkeiten, und dazu könnte ich die Wahrscheinlichkeiten schreiben.

Ich könnte stattdessen aber alle Kugeln nummerieren, und hätte so Kugel 1=r, Kugel 2, 3 = g und Kugel 4, 5, 6 sind b.

Dann sind die Möglichkeiten zu ziehen:

111
112
113
121
122
123
...
666

usw. und 112 wie 113 und 121 und 131 und 211 wie 311 bedeutet alles: 2*r, 1*g, aber ich kann sofort ablesen, daß (2*r, 1*g) in 6 Fällen (von 6^3 = 6*6*6 = 36*6 = 216) vorkommt. In 1/36 Fällen also ziehe ich ein r zwei g.

Die Zahl der Möglichkeiten ist determiniert, und die Zahl der Möglichkeiten ist determiniert. Ich könnte also einen Zufallsinteger im Intervall 0-215 incl. produzieren, und nachsehen, welche Kombination an dieser Stelle verortet ist, und müßte nicht mehr jede Kugel gesondert ziehen.

Jetzt hast Du mehr Farben, mehr Kugeln und mehr Züge. Da die Kugeln zurückgelegt werden ist für die Ziehwahrscheinlichkeit nur die ganzzahlige Proportion interessant, d.h. aus (10, 20, 30, 25, 15) können wir (2, 4, 6, 5, 3) machen, also 20 Kugeln die wir nummerieren, 2 blaue, 4 rote usw.

Bei 100 Ziehungen sind das 20^100 Möglichkeiten, wie diese 20 Kugeln gezogen werden können. Das sind 12676506002282294014967032053760000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 Möglichkeiten. Man sieht, es war keine so schlechte Idee sich zuerst auf 6 Kugeln und 3 Ziehungen zu beschränken. ☺

Jetzt weiß ich nicht, ob man mit BigInteger auch random-Funktionen zur Verfügung hat. Und ich weiß nicht, wie man für die Zufallszahl flugs berechnet, welche Verteilung sich dahinter versteckt. Theoretisch machbar ist das sicher.

Man würde natürlich die enorme Zahl deutlich vermindern, wenn es gelänge die Reihenfolge zu eliminieren, aber ist es dann noch einfach eine Position einer Zufallszahl zuzuordnen?

Schauen wir uns nochmal oben die Liste an (111, 112 ... 666). Das sind ja alle Zahlen von 111 bis 666 in denen keine 0 oder 7,8,9 vorkommt.
Wir könnten und sollten bei jeder Ziffer eins subtrahieren, und kämen dann auf (000, 001, ... 555) und könnten es als Sextalzahl betrachten, also Zahlen im 6er-System von 0 bis 215.

Liefert unser Zufallsgenerator also die Zahl 189, so ändern wir die Darstellung ins 5er-System, das ist 513(6). Die 5 steht für b, die 1 für r und die 3 für g.

Analog kann man die Zufallszahl random.nextInt (20^10) bilden (wirklich?) und ins 20er-System transformieren, und an jeder Ziffer ablesen, welche Farbe sie kodiert.

Ohne weitere Tricks ist das aber bestimmt deutlich langsamer, als 100 mal zu ziehen.

Habe ich die Idee richtig erfaßt?

user unknown schrieb:

Laß es uns ersmal vereinfachen. Mit 2 Farben wäre es zu einfach, denn wenn ich 10 Kugeln habe, davon 4 weiße und 6 schwarze, und ziehe 2 weiße, dann brauche ich keine weitere Information - die 8 anderen müssen dann schwarz sein.

Wieso das denn? Es gibt ja noch zwei weitere weiße...

@dersven Ich kapiere immer noch nicht, was Du eigentlich bezeckst. Du willst nicht 100 Mal (oder eben noch mehr) ziehen, sondern mit einer Berechnung die Wahrscheinlichkeit herausfinden?

@Lysander:

Ja, ich moechte nur eine einzige Zufallszahl bestimmen, aus einer Multinomialen Wahrscheinlichkeitsverteilung.

Der erste Schritt ist das Berechnen der Wahrscheinlichkeitsverteilung (Anhand der Wahrscheinlichkeiten/Haufigkeiten der einzelnen "Dimensionen" - also der Kugelsorten).

Dann moechte ich eine einzige Zufallszahl in diesem Raum bestimmen (die sind nicht gleichverteilt, dass ist ja der Haken an der Sache), sondern sollen unter Beruecksichtigung der Wahrscheinlichkeiten dieser Multinomialen Verteilung gezogen werden.

Wenn ich nun die "Koordinaten" innerhalb des Raumes habe, habe ich direkt auch die Verteilung meiner Kugel innerhalb des Topfes NACH dem ziehen. Und es ist dabei total egal, ob ich 10 oder 10'000'000 mal ziehe.

@user unknown:

So wie ich es verstanden habe meinen wir das gleiche, aber die Ersetzungen sind wirklich eher umstaendlich, besonders wenn ich groessere Zahlen habe. Meine Idee war auch noch, das ich (Kugeltypen-1)-mal aus einer Binomialverteilung ziehe, und dabei jeweils eine Binomialverteilung mit der Haufigkeit der entsprechend betrachteten Kugel verwende. Aus dem Rest der ersten Berechnung ziehe ich dann den naechsten Typ, usw. der Letzte Rest ist dann eben der letzte Kugeltyp. Dann ist aber die Frage:

Wie ziehe ich Zufallszahlen, die nicht gleichverteilt sind, sondern einer Bionomialen Wahrscheinlichkeitsverteilung entsprechen? Also wenn ich die gezogenen Zahlen in eine Grafik gegen ihre Haufigkeiten wie sie gezogen wurden auftrage kommt keine Konstante Funktion raus (was ja bei gleichwahrscheinlichen Zufallszahlen der Fall ist), sondern eben eine Binomial-Kurve (aehnlich einer Glockenkurve)?

Was fuer einen Fehler baue ich mir ein, wenn ich mehrfach aus unterschiedlichen verteilungen ziehe?

dersven schrieb:

@Lysander:

Ja, ich moechte nur eine einzige Zufallszahl bestimmen, aus einer Multinomialen Wahrscheinlichkeitsverteilung.

Dann führe das Experiment eben genau einmal durch!

Der erste Schritt ist das Berechnen der Wahrscheinlichkeitsverteilung (Anhand der Wahrscheinlichkeiten/Haufigkeiten der einzelnen "Dimensionen" - also der Kugelsorten).

Dann moechte ich eine einzige Zufallszahl in diesem Raum bestimmen (die sind nicht gleichverteilt, dass ist ja der Haken an der Sache), sondern sollen unter Beruecksichtigung der Wahrscheinlichkeiten dieser Multinomialen Verteilung gezogen werden.

Das ist doch das gleiche wie genau einmal das Experiment durchzuführen! Ich sehe da keinen Unterschied zu meinem Vorschlag...

Lysander schrieb:

user unknown schrieb:

Laß es uns ersmal vereinfachen. Mit 2 Farben wäre es zu einfach, denn wenn ich 10 Kugeln habe, davon 4 weiße und 6 schwarze, und ziehe 2 weiße, dann brauche ich keine weitere Information - die 8 anderen müssen dann schwarz sein.

Wieso das denn? Es gibt ja noch zwei weitere weiße...

Nein, das sollte bedeuten, daß die Ziehung bereits gelaufen ist, und ich auf die Frage "Wieviele weiße?" 2 antworte. Dann müssen die anderen 8 schwarz sein. Daher kam mir das Beispiel mit 2 Farben zu schlicht vor.

Lysander schrieb:

Das ist doch das gleiche wie genau einmal das Experiment durchzuführen! Ich sehe da keinen Unterschied zu meinem Vorschlag...

Nein, nein. Stell Dir vor die Ziehung der Lottozahlen. Es werden nicht 6 x eine Kugel gezogen, sondern vorab werden alle möglichen Ergebnisse aufgeschrieben, in Umschläge gesteckt, und dann wird nur noch ein Umschlag gezogen, in dem die 6 Zahlen drin stehen. Das geht viel schneller, wenn man die Zig-Millionen Möglichkeiten erstmal aufgeschrieben hat.

Im Lottofall ist es insofern anders, als die Kugeln nicht zurückgelegt werden, d.h. 1, 1, 1, 4, 30, 46 ist keine gültige Lottozahlenauslosung, und daß jede Kugel gleichoft da ist.

Hier sollen die Kugeln nicht gleichoft vorhanden sein, und zurückgelegt werden, aber das eigentliche Problem ist das gleiche: Es gibt so viele Möglichkeiten.

dersven schrieb:

aber die Ersetzungen sind wirklich eher umstaendlich, besonders wenn ich groessere Zahlen habe.

Was ist daran umständlich? Das Verfahren ist aufwendig, aber geistig von enormer Schlichtheit.

Schau Dir mal Random.nextGaussian () in java.util an - und zeig uns hinterher, was Du gebaut hast. Wieso willst Du es überhaupt so machen, und nicht 100 mal ziehen - glaubst Du daß das schneller ist?

user unknown schrieb:

Lysander schrieb:

Das ist doch das gleiche wie genau einmal das Experiment durchzuführen! Ich sehe da keinen Unterschied zu meinem Vorschlag...

Nein, nein. Stell Dir vor die Ziehung der Lottozahlen. Es werden nicht 6 x eine Kugel gezogen, sondern vorab werden alle möglichen Ergebnisse aufgeschrieben, in Umschläge gesteckt, und dann wird nur noch ein Umschlag gezogen, in dem die 6 Zahlen drin stehen. Das geht viel schneller, wenn man die Zig-Millionen Möglichkeiten erstmal aufgeschrieben hat.

Ok, endlich einmal klar ausgedrückt ☺ (Wenn es denn wirklich das ist, was dersven wirklich machen will!) Es ist dennoch das gleiche! Einmal Ziehen bedeutet doch nur, dass man einen dieser Umschläge erstellt. Der Inhalt ist aber derselbe, auch wenn man ihn vorher berechnet und nur irgend wo hingelegt hätte. Wenn ich ihn eben nur einmal berechne und dann gleich verwerte habe ich dennoch ein gültiges mögliches Ergebnis.

Man mag mich ja ungläubig nennen, aber es ist doch nicht praktikabel, alle möglichen Kombinationen einer Lottoziehung auszurechnen und irgend wo abzulegen ... Natürlich müßte man sich dann nur noch einen Datensatz rauspicken und auslesen, aber das steht doch nicht in Relation zum Speicherverbrauch und zur vorangegangenen Rechenzeit! Immerhin muss ich dann alle Kombinationen ausrechnen - diese Rechenzeit kann ich doch sinnvoller nutzen und sofort eine bestimmte Anzahl an Ziehungen realisieren...

Hi.

Das Lotto-Beispiel sagt es wirklich gut.

Ich habe jetzt mal versucht eine Binomial Verteilte ZufallsZahl erzeugen zu lassen. (Allerdings sieht die Verteilung merkwurdig aus,... Oder habe ich einfach ein falsches Bild von Binomial-Verteilungen in meinem Kopf?)

Im folgenden Beispiel habe ich (um bei BInomial zu bleiben) 1000 kugeln, von denen 500 schwarz und 500 weiss sind. jetzt moechte ich 1000 neue kugel haben, und ziehe 1000 mal auf dem Topf, lege eine gleichartige kugel in den neuen Topf, die gezogene lege ich aber zurueck in den ersten Topf. Das mache ich nun 1000 mal (denn ich kann ja auch 1000 mal eine schwarze ziehen - also eine Zufallszahl zwischen 1 und 1000 erzeugen, 1-500 ist schwarz, 501-1000 ist weiss). Das waeren nun 1000 Schritte. bei der Binomial-Verteilung ist es genau einer (naemlich das erzeugen der BinomialVerteilten Zufallszahl). Diesen Vorgang (einen neuen Topf fuellen) wiederhole ich nun 100'000'000 mal. also erstelle ich 10'000'000 Zufallszahlen. Wenn ich nun das ziehen simulieren wurde, waere ich schon bei zehn Milliarden schritten (was dann nicht mehr nur wenige sekunden dauert). Ist also schneller.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.Random;

import org.uncommons.maths.random.BinomialGenerator;
import org.uncommons.maths.random.MersenneTwisterRNG;


public class Main {
	
	public static void main(String[] args) {
		
		// wahrscheinlichkeit des Ereignisses
		float prob = (float) 0.5;
		
		int verteilung[] = new int[1000];
		
		Random rng = new MersenneTwisterRNG();
		BinomialGenerator gen = new BinomialGenerator(verteilung.length, prob, rng);
		
		// 10'000'000 Messpunkte
		for(int i=0; i<10000000; i++) {
			verteilung[gen.nextValue().intValue()]++;
		}
		// Verteilung ausgeben
		for(int i=0; i<verteilung.length; i++) {
			System.out.println(i + "\t" + verteilung[i]);
		}
		
	}

}

Wenn ich nun mehr als zwei kugeln haette, muesste ich das ganze Multinomial machen - und da scheitere ich derzeit noch dran,...

Kommt denn das gleiche raus, wenn ich meine menge immer in zweierGruppen aufteile (wie in meinem letzten Posting beschrieben)?

It depends.

Unter günstigen Umständen wird das Verfahren deutlich einfacher. Z.B. es gäbe 10 Farben (0-9), und nur 10 Ziehungen.

Dann könnte ich mit einer 10-stelligen Integerzahl eine Ziehung abbilden: 3451247791 würde dann heißen daß Farbe 3 1-mal kam, die 4 zweimal, 5, 2 und 9 einmal und 1 wie 7 auch zweimal. Wären die Farben gleichverteilt so könnte ich also durch eine 10stellige Zufallszahl fast unmittelbar die Anzahl der Farben abbilden, ich müßte nur auszählen und die Kodierung Ziffer-Farbe dekodieren.

Die Dekodierungsnotwendigkeit habe ich aber auch beim 10-maligen Ziehen, und auszählen muß ich da auch.

dersven

Im folgenden Beispiel habe ich (um bei BInomial zu bleiben) 1000 kugeln, von denen 500 schwarz und 500 weiss sind. jetzt moechte ich 1000 neue kugel haben, und ziehe 1000 mal auf dem Topf, lege eine gleichartige kugel in den neuen Topf, die gezogene lege ich aber zurueck in den ersten Topf.

Ok, ist mir klar. Ist quasi eine Ziehung.

Das mache ich nun 1000 mal (denn ich kann ja auch 1000 mal eine schwarze ziehen - also eine Zufallszahl zwischen 1 und 1000 erzeugen, 1-500 ist schwarz, 501-1000 ist weiss).

Das kapiere ich nicht. Wieso muss die Zahl zwischen 1 und 1000 sein? Bei schwarz und weiß gibt es doch nur 2 Alternativen. Also muss ich die doch modellieren, z.B. mit 0 und 1 oder True und False oder so.

Das waeren nun 1000 Schritte.

Das ist mir auch wieder klar.

bei der Binomial-Verteilung ist es genau einer (naemlich das erzeugen der BinomialVerteilten Zufallszahl).

Wie genau sieht die denn aus? Ich denke hier hängt sich mein Verständnisproblem auf ...

Diesen Vorgang (einen neuen Topf fuellen) wiederhole ich nun 100'000'000 mal.

Also quasi das Experiment durchführen, ok.

also erstelle ich 10'000'000 Zufallszahlen.

(Du meinst sicher 100'000'000). Was ist denn eine Zufallszahl in diesem Schritt? Wie sieht die aus?

Wenn ich nun das ziehen simulieren wurde, waere ich schon bei zehn Milliarden schritten (was dann nicht mehr nur wenige sekunden dauert).

Ok, da ich die 1000 Schritte zum Ziehen aus dem Basis-Topf ja durchführen müßte.

Entscheidend ist nun für mich: Wie sieht diese binomial verteilte Zufallszahl aus? Wie wird diese erstellt? Ich denke wenn ich das kapiert habe kapiere ich die Lösung und das Problem ☺

@user unknown

guenstige umstaende gibts meistens nicht,... Und selbst alles kodieren/dekodieren moechte ich auch nicht - das wird bei grossen zahlen und ungleichverteilung unschoen

Fuer 15 farben mueste ich 14 binomi Ziehungen machen (Wenn das Verfahren ("Aus dem Rest ziehen") so geht wie ich es will).

Also:

farbe1_neu = 1000 trials; p(Farbe 1);

farbe2_neu = 1000-farbe1neu trials; p(Farbe 2);

farbe3_neu = 1000-(fareb1neu+farbe2neu) trials; p(Farbe 3);

...

wobei das bestimmen eine Multinomialen Zufallzahl wieder in einem Schritt gemacht waere.