Zufallszahl mit Wahrscheinlichkeit

simuletsplay

Neues Mitglied
Hallo zusammen,

ich habe folgendes Problem, dass ich die Zahlen 1-6 (wie bei einem Würfel) ZUFÄLLIG ausgeben möchte.

Jedoch, soll der Algorithmus manipulierbar sein, indem man die Wahrscheinlichkeit zu jedem Wert angeben kann.
Damit das Mathematisch korrekt ist, ergibt die Summe der Wahrscheinlichkeiten immer 1.

Wie lässt sich das als Algorithmus umsetzen?

Meine "unsaubere Idee" wäre ein Array mit 1000 Elementen, in dem die Ziffern 1-6 je nach Wahrscheinlichkeit verteilt sind.
Bin aber selber nicht überzeugt davon.
Am liebsten hätte ich eine Rechnung dafür.

Hat jemand Ideen?

Grüße
Ben
 

DrPils

Bekanntes Mitglied
Math.Random gibt dir eine komma Zahl >0 und <1, die wahrscheinlichkeit dass die Zahl in dieser Range ist ist 1.
Die Wahrscheinlichkeit, dass die zahl kleine als 0.5 ist ist 0.5.
 

simuletsplay

Neues Mitglied
Ja ich habe ja somit immer eine Gleichverteilung.

Aber wie sieht es denn aus, wenn ich folgendes Prinzip habe:

Zahl-Wahrscheinlichkeit
1 10%
2 10%
3 10%
4 10%
5 10%
6 50%

???
Also sehen wir das nicht als Zahl, sondern als Wert
1 w1
2 w2
... ...
an. Dann brauche ich ja irgendwie nen Algorithmus, der das errechnet.
Und ja: Ausgehend von einer gleichverteilten Random-Zahl über die von dir oben beschriebene Möglichkeit!
 

httpdigest

Top Contributor
Du hast eine diskrete Zufallsvariable X mit x in {1, 2, 3, 4, 5, 6} und den entsprechenden diskreten Wahrscheinlichkeiten. Hierfür ist die "Alias method" oder auch "Alias table" eine geeignete Lösung, um in O(1) und mit geringem Speicherverbrauch entsprechend gewichtete Zufallswerte zu ziehen.
Tatsächlich habe ich vor einiger Zeit die Alias Table mal selber implementiert (brauchte ich zu der Zeit auch mal), hier ist es:
Java:
import java.util.*;
/**
 * Alias table for efficiently sampling from discrete distributions.
 *
 * @author Kai Burjack
 */
public final class AliasTable {
    private final int[] a;
    private final float[] p;

    /**
     * @param w the probabilities (will be modified by this constructor)
     */
    public AliasTable(float... w) {
        int N = w.length;
        this.p = new float[N];
        this.a = new int[N];
        float avg = 1.0f / N;
        ArrayDeque<Integer> s = new ArrayDeque<>(), l = new ArrayDeque<>();
        for (int i = 0; i < N; ++i)
            if (w[i] >= avg)
                l.add(i);
            else
                s.add(i);
        while (!s.isEmpty() && !l.isEmpty()) {
            int sm = s.poll(), lg = l.poll();
            p[sm] = w[sm] * N;
            a[sm] = lg;
            w[lg] = w[lg] + w[sm] - avg;
            if (w[lg] >= avg)
                l.add(lg);
            else
                s.add(lg);
        }
        while (!s.isEmpty())
            p[s.poll()] = 1.0f;
        while (!l.isEmpty())
            p[l.poll()] = 1.0f;
    }

    public int next(Random r) {
        int column = r.nextInt(p.length);
        return r.nextFloat() < p[column] ? column : a[column];
    }
}
 
Zuletzt bearbeitet:

Oneixee5

Top Contributor
Die Idee mit dem Array finde ich gar nicht so schlecht. Möglicherweise ist aber die starre Anzahl von 1000 Elementen etwas zu einfach gedacht. Die Anzahl musste so gwählt werden, dass wirklich die korrekte Verteilung erreicht wird.
 

DrPils

Bekanntes Mitglied
Java:
private static int rollDice(double[] probabilities) {
        double random = Math.random();
        for (int i = 0; i < probabilities.length; i++) {
            if (random < probabilities[i]) return i +1;
        }
        return 0;
    }

Ist doch wesentlich einfacher?
 

httpdigest

Top Contributor
Java:
private static int rollDice(double[] probabilities) {
        double random = Math.random();
        for (int i = 0; i < probabilities.length; i++) {
            if (random > probabilities[i]) return i +1;
        }
        return 0;
    }

Ist doch wesentlich einfacher?
Das funktioniert offensichtlich nur mit einer kumulativen Wahrscheinlichkeitsverteilungsfunktion (CDF).
Du müsstest also zuerst einmal aus der diskreten Wahrscheinlichkeitsverteilung eine kumulative Verteilung erzeugen (und den Verglich zu < ändern).
Und nein: So einfach ist das Problem des effizienten Ziehen aus einer gewichteten diskreten Wahrscheinlichkeitsfunktion nicht, sonst gäbe es die Alias Methode nicht.

Angenommen, deine Wahrscheinlichkeiten sind: {.01, .01, .01, .01, .01, .95}
Dann würde deine Funktion in 95% der Ziehungen immer 0 als Ergebnis liefern, weil die Random Variable in 0..1 ist und häufig immer größer als 0.01 ist. Das ist aber nicht gewünscht.
 

temi

Top Contributor
Erzeuge eine Zahl zwischen 1 und 100.

1 - 10 => 1
11 - 20 => 2
usw

wie die Verteilung ist, kannst du leicht bestimmen, denn die größte zufällige Zahl ist 100, was 100% entspricht.
 
Zuletzt bearbeitet:

temi

Top Contributor
Alternative:

"Fülle" eine Collection mit 100 Zahlen in der gewünschten Verteilung, mische und ziehe eine Zahl daraus. Das ist dann die "Bällebad"-Methode ;)

50 rote Bälle, 20 Grüne, 20 Gelbe und 10 Blaue.
 

DrPils

Bekanntes Mitglied
ja das wäre ja aber eine Falsche Übergabe, muss man dann halt abfangen. Die wahrscheinlichkeit dass eine Zahl von 1 - 6 gewuerfelt wird ist
Das funktioniert offensichtlich nur mit einer kumulativen Wahrscheinlichkeitsverteilungsfunktion (CDF).
Du müsstest also zuerst einmal aus der diskreten Wahrscheinlichkeitsverteilung eine kumulative Verteilung erzeugen (und den Verglich zu < ändern).
Und nein: So einfach ist das Problem des effizienten Ziehen aus einer gewichteten diskreten Wahrscheinlichkeitsfunktion nicht, sonst gäbe es die Alias Methode nicht.

Angenommen, deine Wahrscheinlichkeiten sind: {.01, .01, .01, .01, .01, .95}
Dann würde deine Funktion in 95% der Ziehungen immer 0 als Ergebnis liefern, weil die Random Variable in 0..1 ist und häufig immer größer als 0.01 ist. Das ist aber nicht gewünscht.
Ja hast vollkommen recht.
Aber wenn ich jetzt noch die Bedingung so abändere, dass die Summe aller vorherigen Wahrscheinlichkeiten und der Aktuellen genommen wird.
Scheint es zu passen.

Java:
    public static int rollDice(double... probabilities) {
        double random = Math.random();
        double bound = 0;
        for (int i = 0; i < probabilities.length; i++) {
            bound += probabilities[i];
            if (random < bound) return i + 1;
        }
        throw new RuntimeException();
    }

Bei 100.000 Durchläufen:

1: 1042
2: 1038
3: 970
4: 994
5: 1025
6: 94931
 
K

kneitzel

Gast
Ja, spielen wir es doch einfach einmal durch. Die Idee mit dem Array ist ja schon einmal gut, um sich eine Lösung zu überlegen.

Der Würfelwurf hat alles mit der Gewichtung 1, daher hat man ein Array, in dem alle Elemente einmal vorkommen:
1, 2, 3, 4, 5, 6
Eine Zufallszahl von [0,5] und schon hat man eine Zufallszahl.

Jetzt soll die eins die Gewichtung zwei bekommen. Also haben wir nun ein Array:
1, 1, 2, 3, 4, 5, 6
Da 7 Elemente kommt nun eine Zufallszahl des Bereiches [0,6]

Jetzt ist die Frage: Muss man ein solches Array erstellen um füllen, um dies zu machen? Ganz offensichtlich hat man ja hier immer eine Addition der Gewichtung:
die 1 geht von [0,<Gewichtung 1>[
die 2 geht von [2, <Gewichtung 2>[ ==> [<Gewichtung 1>, <Gewichtung 2>[
die 3 geht von [3, <Gewichtung 3>[ ==> [<Gewichtung 1 & 2>, <Gewichtung 2>[
u.s.w.

Damit hat man einfach:
- Die Summe aller Gewichtungen wird benötigt.
- Zufallszahl von [0, SummeGewichtungen[

Nun geht man durch:
zwischenSumme := 0
Für jede Möglichkeit:
--> zwischenSumme := zwischenSumme + Gewichtung Möglichkeit
--> falls zwischenSumme > Zufallszahl, dann ist die Möglichkeit gezogen worden

Somit benötigt man kein Array oder ähnliches sondern kann rein vom Ablauf her heran gehen.

Bei dem ganzen Post bitte aufpassen: Bereiche sind mit [ bzw ] (Grenze gehört zu dem Bereich) oder ] bzw [ (Grenze gehört nicht zum Bereich!) angegeben worden!
 

httpdigest

Top Contributor
Für dieses Problem (also |X| = 6) ist das lineare Durchsuchen der kumulativen Wahrscheinlichkeitsverteilung eine gute Wahl.
Nur, ist dies nicht mehr der Fall, wenn es z.B. um eine Million diskrete Werte mit ihren Warscheinlichkeiten geht.
Denn das lineare Suchen ist ja immer noch O(n).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
E Zufallszahl mit Wahrscheinlichkeit Java Basics - Anfänger-Themen 4
krgewb Immer dieselbe Zufallszahl Java Basics - Anfänger-Themen 4
M Zufallszahl generieren mit einer linken und rechten Grenze Java Basics - Anfänger-Themen 3
J for Schleife kleinste Zufallszahl finden Java Basics - Anfänger-Themen 25
brypa Zufallszahl Java Basics - Anfänger-Themen 9
C Zufallszahl + Werte bereich einstellen Java Basics - Anfänger-Themen 2
N Bereich Zufallszahl bestimmen (50 und 100 / 80 und 90) Java Basics - Anfänger-Themen 2
J Zufallszahl funktioniert nicht Java Basics - Anfänger-Themen 27
T Random soll Zufallszahl beibehalten. Java Basics - Anfänger-Themen 11
F Immer wieder gleiche Zufallszahl? Java Basics - Anfänger-Themen 4
D Zufallszahl zwischen 10 und 99? Java Basics - Anfänger-Themen 5
M Vierstellige Zufallszahl Java Basics - Anfänger-Themen 3
B Methoden Per Buttonklick eine Zufallszahl in ein Numberfield geben Java Basics - Anfänger-Themen 2
S Zufallszahl-Generatoren (Schnittstellen) Java Basics - Anfänger-Themen 14
S Zufallszahl (Statische Attribute und Methoden) Java Basics - Anfänger-Themen 10
M Erste Schritte Zufallszahl Spiel Problem Java Basics - Anfänger-Themen 7
N Zufallszahl beim Eintragen Java Basics - Anfänger-Themen 2
B Methoden Die Sache Mit der Zufallszahl Java Basics - Anfänger-Themen 3
I immer die gleiche Zufallszahl Java Basics - Anfänger-Themen 9
F Zufallszahl ohne Wiederholung Java Basics - Anfänger-Themen 7
R Zufallszahl Java Basics - Anfänger-Themen 5
P Typecasting für Ganzzahlige Zufallszahl (Math.random) Java Basics - Anfänger-Themen 2
S Zufallszahl erzeugen in 50er Schritten Java Basics - Anfänger-Themen 2
S Gerade bzw. Ungerade Zufallszahl generieren Java Basics - Anfänger-Themen 5
P Erste Schritte Zufallszahl in Ascii-Code umwandeln ?!? Java Basics - Anfänger-Themen 6
M Exception bei Zufallszahl Java Basics - Anfänger-Themen 15
M neue Zufallszahl in Schleife Java Basics - Anfänger-Themen 2
TheKing Zufallszahl die man durch 15 dividieren kann Java Basics - Anfänger-Themen 6
Luk10 Zufallszahl "ohne" eine bestimmte Zahl(en) Java Basics - Anfänger-Themen 8
N zufallszahl Java Basics - Anfänger-Themen 3
D Java Zufallszahl Java Basics - Anfänger-Themen 5
N Zufallszahl Java Basics - Anfänger-Themen 2
A Eingabe und Zufallszahl Java Basics - Anfänger-Themen 12
S Zufallszahl -> Schleife Java Basics - Anfänger-Themen 10
TheKing ZufallsZahl im negativbereich Java Basics - Anfänger-Themen 2
S Zufallszahl mit 6 Stellen erzeugen Java Basics - Anfänger-Themen 4
D bei Zufallszahl immer 2 Java Basics - Anfänger-Themen 12
K Zufallszahl Java Basics - Anfänger-Themen 4
Z Alle 15 sek eine Zufallszahl auf Bildschirm Java Basics - Anfänger-Themen 10
M Zufallszahl - kleine Frage Java Basics - Anfänger-Themen 4
S Zufallszahl Java Basics - Anfänger-Themen 9
I Zufallszahl ziwschen 0 und 7 Java Basics - Anfänger-Themen 3
F Zufallszahl in einem bestimmten Intervall Java Basics - Anfänger-Themen 9
B Befehl zum erstellen einer Zufallszahl. Java Basics - Anfänger-Themen 8
S 4-stellige Zufallszahl Java Basics - Anfänger-Themen 4
P Methode funzt nicht => Zufallszahl darf nicht 2x erschein Java Basics - Anfänger-Themen 4
M zufallszahl ohne doppelvorkommen Java Basics - Anfänger-Themen 2
H Zufallszahl Java Basics - Anfänger-Themen 2
K [Java] Zufallszahl als ganze Zahl Java Basics - Anfänger-Themen 5
G Zufallszahl zwischen 2 und n Java Basics - Anfänger-Themen 10
R Zufallszahl random Java Basics - Anfänger-Themen 8
E zufallszahl zwischen 1 und 6 Java Basics - Anfänger-Themen 6
J eigene methode erstellen die eine Zufallszahl generiert. Java Basics - Anfänger-Themen 12
J Zufallszahl ohne Math.random Java Basics - Anfänger-Themen 4
S Spiel: Wer ist näher an der Zufallszahl? Java Basics - Anfänger-Themen 4
N Überprüfung der ZufallsZahl? Java Basics - Anfänger-Themen 2
S Zufallszahl ermitteln Java Basics - Anfänger-Themen 2
C Zufallszahl zwischen... Java Basics - Anfänger-Themen 10
H zufallszahl Java Basics - Anfänger-Themen 2
F Wahrscheinlichkeit von Strings Java Basics - Anfänger-Themen 3
N java.util.Random - Zwei Zahlen mit festgesetzter Wahrscheinlichkeit? Java Basics - Anfänger-Themen 15
B Variablen Mehrere Zahlen mit unterschiedlicher Wahrscheinlichkeit mit Random auswählen Java Basics - Anfänger-Themen 17
F Wie rechne ich bei meinem Code, die Wahrscheinlichkeit von Fall X aus? Java Basics - Anfänger-Themen 3
Q Formel für Wahrscheinlichkeit in Java Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben