Ereignisse mit unterschiedlichen Eintrittswahrscheinlichkeiten

[AllesMeins]

Hi,

ich grübele seit einigen Tagen über einem Problem. Die Lösung soll in PHP umgesetzt werden, mir würden aber auch allgemeine Lösungsideen helfen. Und zwar suche ich nach einer effektiven Möglichkeit verschiedene Ereignisse mit einer bestimmten Wahrscheinlichkeit eintreten zu lassen. Also Beispielhaft es gibt die Ereignisse A, B, C und D. A soll in 22% der Fälle eintreten, B in 3%, C in 17% und D in 42%.
Das ganze würde ich gerne so flexibel bauen, dass ich es mit einer beliebigen Anzahl von Ereignissen nutzen kann. Solche simplen Konstrukte wie:

a = rand(0,100)
if(a <= 22){
 Ereigniss A
} elseif (a > 22 && a <= 25){
 Ereigniss B
...

sind also nichts. Das ganze dürfte ja auch kein so spezielles Problem sein, gibt es dafür schon irgendwelche gute und bewährte Lösungsansätze? Oder hat irgendwer eine Idee wie sich das möglichst effektiv und "schön" lösen lässt?

Grüße

Marc

[Julian von Mendel]

Hi,

a = rand(0,100)

das sind dann ja schon 101 Möglichkeiten...

if(a <= 22){
Ereigniss A
} elseif (a > 22 && a <= 25){

Das a > 22  ist nutzlos, wenn das nicht zutreffen würde hätte schließlich das if vorher gegriffen.

Ereigniss B

Wieso erzeugst du diese Abfragen nicht dynamisch in in einer Schleife?

  
    $moeglichkeiten = array("Ergebnis A" => 33, "Ergebnis B" => 44, "Ergebnis C" => 23);  
    $rand = rand(1, 100);  
    $offset = 0;  
    foreach($moeglichkeiten as $name => $moeglichkeit)  
    {  
        $offset += $moeglichkeit;  
        if ($rand > $offset) continue;  
        $found = $name;  
        break;  
    }  
    // Weiterverarbeitung  
    echo $found."\n";  

Schöne Grüße
Julian

[Daniel Thoma]

Hallo Julian und Marc,

Die Variante ist schon recht gut, man kann das aber noch verbessern. Das ist vor allem interessant, wenn man sehr viele verschiedene Ereignisse hat.

Man ordnet die n Ereignisse in einer beliebigen aber festen Reihenfolge an.
Dann berechnet man ein Array mit n - 1 Einträgen. Eintrag i enthält die Summe der Wahrscheinlichkeiten der ersten i Ereignisse (Einen n. Eintrag braucht man nicht, da wäre die Summe ja immer 1)
Nun kann man eine Zufallszahl zwischen 0 und 1 ziehen und mit binärer Suche das i bestimmen, so dass array(i - 1) < zahl <= array(i) wobei die nicht vorhandenen Einträge als array(0) = 0 und array(1) = 1 definiert werden.

Grüße

Daniel

[seth]

gudn tach!

Nun kann man eine Zufallszahl zwischen 0 und 1 ziehen

gibt's dafuer in php eigentlich eine fertige funktion? denn rand() arbeitet anders als in den meisten anderen grossen sprachen, liefert naemlich nur integers.
man koennte zwar was basteln a la
  floatval('.'.mt_rand(0,9).mt_rand(0,9).mt_rand(0,9).mt_rand(0,9)),
aber besonders huebsch ist das ja nun nicht.

und mit binärer Suche das i bestimmen, so dass array(i - 1) < zahl <= array(i) wobei die nicht vorhandenen Einträge als array(0) = 0 und array(1) = 1 definiert werden.

kleiner tippfehler: s/array(1)/array(n)/

prost
seth

[Daniel Thoma]

Hallo seth,

gibt's dafuer in php eigentlich eine fertige funktion? denn rand() arbeitet anders als in den meisten anderen grossen sprachen, liefert naemlich nur integers.

Ich habe keine Erfahrung mit PHP und auf die schnelle konnte ich in der Doku auch nichts finden. Es wäre aber schon etwas jämmerlich, wenn man keine Zufallszahlen zwischen 0 und 1 (gleich- und normalverteilt) bekommen würde.
So bald man irgendwie mit kontinuierlichen Wahrscheinlichkeiten arbeitet, braucht man das ja dauernd.

Gleichverteilte Zufallszahlen sollte man aber schon mal mit mt_rand() / mt_getrandmax() bekommen.
Normalverteilte Zufallszahlen (die wir für diese Anwendung ja gar nicht brauchen) zu erzeugen, ist dann schon umständlicher. Da kann man eines dieser Verfahren implementieren: < http://de.wikipedia.org/wiki/Normalverteilung#Simulation_normalverteilter_Zufallsvariablen>

kleiner tippfehler: s/array(1)/array(n)/

Nein kein Tippfehler. Der Array-Index läuft von 1 bis n - 1, das ist richtig. Allerdings steht ja am Index 1 die Wahrscheinlichkeit, des ersten Elements, wenn die Zufallszahl <= dieser Wahrscheinlichkeit ist, gilt die Gleichung array(0) < zahl <= array(1).
Ich habe diese zwei Werte, die nicht im Array stehen, definiert, um die Gleichung so einfach hinschreiben zu können. Bei einer Implementierung muss man das natürlich dann berücksichtigen (oder man nimmt einfach 2 Arrayeinträge mehr)

Grüße

Daniel

[Daniel Thoma]

Nein kein Tippfehler.

Äh natürlich doch ein Tippfehler. Ich hab den Text direkt im Eingabefeld gelesen und das war etwas unübersichtlich ;-)

[Andreas Görtz]

Hi seth,

gibt's dafuer in php eigentlich eine fertige funktion? denn rand() arbeitet anders als in den meisten anderen grossen sprachen, liefert naemlich nur integers.

mir ist keine bekannt.

man koennte zwar was basteln a la
  floatval('.'.mt_rand(0,9).mt_rand(0,9).mt_rand(0,9).mt_rand(0,9)),
aber besonders huebsch ist das ja nun nicht.

in der Tat nicht ;-) Es gibt allerdings noch die Funktionen mt_getrandmax() resp. getrandmax(), sodass:

  
$x = (float)rand() / (float)getrandmax();  

wahlweise mit "mt_" als prefix, eine Zufallszahl zwischen 0 und 1 liefert.

Gruß,
Andreas.

[Julian von Mendel]

Hey Daniel,

ich wäre an einer Beispielimplementation sehr interessiert. Hast du da was für mich?
Danke!

Schöne Grüße
Julian

[Daniel Thoma]

Hallo Julian,

ich wäre an einer Beispielimplementation sehr interessiert. Hast du da was für mich?

Ich hab' jetzt mal eine in Java gebastelt. Ich hoffe, es ist kein Fehler drin, bei binärer Suche haut man da gerne mal irgendwo ne 1 zu viel oder zu wenig rein.

Erstmal die Klasse RandomChooser, die die Ereignisse verwaltet und die Auswahl durchführt:

  
import java.util.Collections;  
import java.util.Map;  
  
public class RandomChooser<T> {  
  
    private Map<? extends T, Double> event2propability;  
    private T[] events;  
    private double[] probabilities;  
  
    /**  
     * Creates a new instance of RandomChooser  
     */  
    @SuppressWarnings("unchecked")  
    public RandomChooser(Map<? extends T, Double> event2propability) {  
        this.event2propability = Collections.unmodifiableMap(event2propability);  
        int pos = 0;  
        events = (T[]) new Object[event2propability.size()];  
        // Enthält die beiden "überflüssigen" Elemente. Macht die binäre Suche einfacher.  
        probabilities = new double[event2propability.size() + 1];  
        probabilities[0] = 0;  
        for (Map.Entry<? extends T, Double> entry: event2propability.entrySet()) {  
            probabilities[pos + 1] = probabilities[pos] + entry.getValue();  
            ++pos;  
        }  
        // Explizites setzen auf 1, da sich die Wahrscheinlichkeiten bei Rundungsfehleren evtl. nicht exakt aufsumiereren.  
        probabilities[probabilities.length - 1] = 1;  
    }  
  
    public Map<? extends T, Double> getEvent2propability() {  
        return event2propability;  
    }  
  
    public T choose(double d) {  
        if (d < 0 || d >= 1) {  
            throw new IllegalArgumentException();  
        }  
        int a = 0;  
        int b = probabilities.length - 1;  
        int pos = 0;  
        while (true) {  
            pos = (a + b) / 2;  
            if (probabilities[pos] > d) {  
                b = pos - 1;  
            } else if (probabilities[pos + 1] <= d) {  
                a = pos + 1;  
            } else {  
                break;  
            }  
        }  
        return events[pos];  
    }  
  
}  

Verwenden kann man das dann folgendermaßen:

  
Random rand = new Random(seed);  
Map<String, Double> events = new HashMap<String, Double>();  
events.put("A", 0.3);  
events.put("B", 0.2);  
events.put("C", 0.5);  
RandomChooser<String> chooser = new RandomChooser<String>(events);  
  
String event = chooser.choose(random.nextDouble());  

Grüße

Daniel