Zufallszahl mit Wahrscheinlichkeit

[simuletsplay]

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]

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]

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!

 

[DrPils]

Wenn du jedes zweite mal ne 1 wuerfeln willst. Gib 1 zurueck wenn math.Random() < 0.5

 

[httpdigest]

Alias method - Wikipedia

en.wikipedia.org

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:

Spoiler

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];
    }
}

 

[Oneixee5]

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]

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]

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]

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.

 

[temi]

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]

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.

    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

 

[kneitzel]

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]

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).

 

[httpdigest]

By the way: dies hier ist eine fantastische Referenz aller Algorithmen fuer "loaded die rolling" und vieles mehr:
https://www.keithschwarz.com/darts-dice-coins/