Eigene Zufallsverteilungen

Die Standardbibliothek bringt für fast alle Anwendungsfälle die passende [Wahrscheinlichkeitsverteilung] (https://de.wikipedia.org/wiki/Wahrscheinlichkeitsma%C3%9F) mit. Wenn es denn dann aber doch mal nicht reicht, kann man sich recht einfach eine eigene schreiben, so wie hier im Beispiel eine physikalisch “korrekte” Münze.

Video

Code

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <random>
#include <iostream>
#include <cmath>

using namespace std;

class coin_distribution
{
    public:
        template <typename engine> int operator()(engine &e)
        {
            auto engine_range = static_cast<double>(engine::max() - engine::min());
            auto max_kante = engine::min() + ceil(engine_range / 10000);
            auto remaining_range = engine_range - max_kante;
            auto max_kopf = max_kante + ceil(remaining_range / 2);

            auto engine_value = e();
            if (engine_value <= max_kante) {
                return 0;
            }
            if (engine_value <= max_kopf) {
                return 1;
            }
            return 2;
        }
};

int main()
{
    int kopf  = 0;
    int zahl  = 0;
    int kante = 0;

    random_device dev;
    mt19937 engine(dev());
    coin_distribution coin;

    for(unsigned int i = 0; i < 1000000; ++i)
    {
        switch(coin(engine))
        {
            case 0:
                ++kante;
                break;
            case 1:
                ++kopf;
                break;
            case 2:
                ++zahl;
                break;
        }
    }

    cout << "Kopf: " << kopf << " mal, Zahl: " << zahl << " mal, Kante: " << kante  << "mal\n";
}

Erklärung

Aufwändig ist eine eigene Zufallsverteilung nicht: im Grunde genommen reicht schon eine Funktion, die die zugrundeliegende Engine als Eingabeparameter nimmt und deren Ergebnisse dann wiederum in die passende Form presst. Meist sind eigene Verteilungen dann aber doch als Funktoren implementiert, um eine gewisse Konfigurierbarkeit und einen internen Zustand zu erlauben.

Hier im Beispiel ist die Klasse coin_distribution bewusst einfach gehalten: eine physikalisch “korrekte” simulierte Münze, die mit gleicher Wahrscheinlichkeit Kopf oder Zahl aufzeigt (repräsentiert durch die Ergebnisse 1 und 2) und in 0,01% der Fälle auf der Kante stehen bleibt (die Wahrscheinlichkeit des Kantenwurfes kann gern diskutiert werden).

In der C++-Standardbibliothek sind die Aufgaben bei der Generierung von Zufallszahlen klar verteilt: die zugrundeliegenden Generatoren sollen möglichst brauchbare Pseudozufallszahlen bereitstellen, die den üblichen statistischen Anforderungen genügen (gleichverteilt, hinreichend lange Periode des Generators etc.). Darauf setzen dann die Verteilungen auf, die aus den generierten Zufallszahlen eine Verteilung machen, wie sie vom Aufrufer gewünscht wird. Dreh- und Angelpunkt ist hierbei die Wahrscheinlichkeitsfunktion, die genutzt wird, um die grundlegende Gleichverteilung in die passende Form zu bringen. Die Wahrscheinlichkeitsfunktion für unsere Verteilung ist im operator() implementiert: der Wertebereich des zugrundeliegenden Generators wird in 3 ungleichgroße Teile aufgeteilt: 0,01%, 49,995% und nochmal 49,995%, die Eintrittswahrscheinlichkeiten von Kante, Kopf und Zahl. Hierfür wird mittels der statischen Methoden engine::min() und engine::max() des Generatortyps engine der tatsächliche Wertebereich bestimmt und in diesem dann quasi “Trennwände” in Form von Grenzwerten eingezogen. Die ersten 0,01% des Wertebereichs (0 bis max_kante) entsprechen dem Ergebnis “Kante”, die darauf folgenden 49,995% (max_kante bis max_kopf) dem Ergebnis “Kopf” und der Rest dem Ergebnis “Zahl”.

Basierend auf dieser Aufteilung wird mittels der Monte-Carlo-Methode ein Ergebnis ermittelt (Herzstück ist das Switch-Statement), welches bei vielen Versuchen der gewünschten Wahrscheinlichkeitsverteilung entspricht.

Der Rest des Programms ist dann nur noch Dekoration: der Münzwurf wird hinreichend oft durchgeführt und die Ergebnisse werden gezählt, um zu verifizieren, dass das Verfahren funktioniert.

Will man jetzt von hier aus etwas weiter gehen, so braucht man sich nicht den Aufwand der eigenen Implementierung zu machen. Genau für den Anwendungsfall “diskrete Verteilung mit konfigurierbaren Eintrittswahrscheinlichkeiten” stellt die Standardbibliothek – wie so oft – etwas bereit: std::discrete_distribution.