Wie kann ich diese Zufallsverteilung in einer Java-Methode implementieren?

 - (Mathe, Mathematik, Programmieren)

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Allerdings wird die Wahrscheinlichkeit doch so schnell so gering, dass i doch so gut wie gar nicht über 5 hinausgeht.

Das kommt drauf an, wie viele Zufallszahlen du generierst. Die 5 tritt durchaus auf.

Hast du dir mal eine Datentabelle dazu gemacht? 1 tritt mit einer Wahrscheinlichkeit von 0,5 auf. 2 mit einer Wahrscheinlichkeit von 0,25. 3 mit einer Wahrscheinlichkeit von 0,125 und so weiter. Man kann erkennen, dass die Summe aller Wahrscheinlichkeiten gegen 1 geht. Mit diesem Wissen könnte man folgenden Algorithmus nachprogrammieren.

- Generiere eine gleichverteilte Zufallszahl x zwischen (inklusive) 0 und (exklusive) 1. Also in Java-Code: x = Math.random();

- Es sei i = 0

- Solange x > 0 ist:

-- Erhöhe i um 1.

-- x = x - 2^-i

-- Ende der Schleife

- i ist deine gesuchte Zufallszahl

Ich hab das eben mal in JavaScript (hab gerade kein Java zur Hand) nachprogrammiert und folgendes Ergebnis für eine Million Durchläufe gekriegt.

{ '1': 500327,
'2': 250177,
'3': 124556,
'4': 62613,
'5': 31098,
'6': 15565,
'7': 7914,
'8': 3844,
'9': 1972,
'10': 994,
'11': 491,
'12': 233,
'13': 105,
'14': 63,
'15': 30,
'16': 8,
'17': 5,
'18': 2,
'19': 3 }

Danke. Und eine wirklich schöne Lösung!

1
@GedankenGruetze

Geht doch einfacher, da man die kumulative Verteilung berechnen kann. Kurz gesagt fängt man mit I = i ⟺ i ≤ I < i+1 ⟺ ℙ[I<i] ≤ U < ℙ[I<i+1] an, wobei U ~ U[0,1]. Da wir die Verteilung von I kennen kann man wie folgt umformen:


var u = Math.random();
var i = Math.floor(-Math.log2(1-u))+1;

2
@kreisfoermig

Das ist mathematisch korrekt und eleganter (und mir nach dem Schreiben dieser Antwort auch eingefallen), aber nicht so performant. Um die gesuchte Verteilung eine Million mal anzuwenden, braucht dein Algorithmus auf meinem Rechner etwa 50ms, meiner nur etwa 16ms. Das liegt daran, dass die Logarithmus-Funktion ziemlich aufwändig ist. ;)

Entscheidend ist aber in diesem Falle denke ich mal weniger die Performance, sondern dass der Fragesteller den Algorithmus versteht.

2
@ceevee

Stimmt, solange er versteht, dass Algorithmen etwa auf der Überlegung

I = i ⟺ i ≤ I < i+1 ⟺ ℙ[I<i] ≤ U < ℙ[I<i+1]

o. Ä. basieren, so kann er ja entscheiden, wie er das algorithmisch umsetzt. Die Schleife-Methode finde ich im Übrigen besser, da man sie unter allen Umständen (d. h. für alle Verteilungen) verwenden kann. Mein kürzer (aber ja langsamer) Code geht leider nur in diesem Falle und hilft einem i. A. nicht weiter.

1
@ceevee

hab gerade kein Java zur Hand

Du kannst übrigens direkt im Browser das implementieren (außer man ist am Handy ; ) Einfach Konsole öffnen und deinen Code eingeben:

var ZV = function(u) {
var i = 0;
var Pr = 0;
var pot = 1;
// erhöhe i bis Pr[I<i] ≤ U < Pr[I<i+1]
while(Pr <= u) {
pot = pot/2;
Pr = Pr + pot;
i++;
}
return i;
};

// Befehl ausführen:
var i = ZV(Math.random());
console.log('ZV = '+i);
2

Wieso generierst du nicht eine beliebige positive Zahl und übergibst sie der Potenz?

Woher ich das weiß:Studium / Ausbildung – Abi 1,0

Weil, wenn ich das Bild richtig verstehe, die bestimmte Zahl ja nur mit der Wahrscheinlichkeit 2^-1 auftreten darf. Generiere ich einfach nur eine Zahl und übergebe sie der Potenz, dann ist die Zahl i im besten Fall gleichverteilt, aber unterliegt eben nicht der oben gegebenen Wahrscheinlichkeit.

1
@GedankenGruetze

Du meinst aber schon 2^(-i), keine Eins im Exponenten!? :)

Okay, dann bin ich auch mal überfragt :(

0
@KnorxyThieus

Schon okay. Ich blicks ja selber nicht. Wenn die eine Aufgabe von 15 nicht habe, ist es auch nicht schlimm :D

1

Was möchtest Du wissen?