C++11-PRNGs

Caligulaminus

cooky451 schrieb:

Also bei mir nicht wirklich

Ich glaube, ich muß mich korrigieren, meine std::uniform_int_distribution scheint doch nicht stateful zu sein.
Morgen muß ich noch mal genauer schauen...

Fytch

volkard schrieb:

Haste die std::uniform_int_distribution lange leben lassen oder für jede Zahl eine neue genaut, wie es so oft hier im Form vorgeschlagen wird?

Ich hab eine Distribution für alle Werte genommen. Ehrlich gesagt habe ich nie Diesbezügliches im Forum gelesen.

Also bei meinem Visual C++ 2013 Express ist std::uniform_int_distribution auch zustandslos implementiert.

Mal außen vor, dass der Generator keine vereinfachte std::shuffle_order_engine und natürlich nicht gleichverteilt ist (wie hoch ist die Wahrscheinlichkeit, mit ihm dreimal hintereinander die gleiche Zahl zu ziehen?) und eine uniform_int_distribution keinerlei Verpflichtung hat, damit sinnvoll klarzukommen -- irgendwie sieht mir das Ergebnis so aus, als sei eine PermutationEngine<10> als Generator für eine uniform_int_distribution(0, 100) verwendet worden. Das könnte natürlich nicht gutgehen.

@asfdlol: Zeig doch mal den kompletten Code, der das Verhalten erzeugt.

hustbaer

seldon schrieb:

Mal außen vor, dass der Generator keine vereinfachte std::shuffle_order_engine und natürlich nicht gleichverteilt ist (wie hoch ist die Wahrscheinlichkeit, mit ihm dreimal hintereinander die gleiche Zahl zu ziehen?)

Es sind keine guten Zufallszahlen wenn man nicht 3x hintereinander die selbe Zahl ziehen kann. Aber inwiefern soll das die (1 dimensionale) Gleichverteilung stören? Die ist ja gerade perfekt bei dem Generator.

und eine uniform_int_distribution keinerlei Verpflichtung hat, damit sinnvoll klarzukommen -- irgendwie sieht mir das Ergebnis so aus, als sei eine PermutationEngine<10> als Generator für eine uniform_int_distribution(0, 100) verwendet worden. Das könnte natürlich nicht gutgehen.

Keine Ahnung, ist das so?
Was sind denn die Anforderungen die eine Distribution an den übergebenen Generator stellen darf?

SeppJ

hustbaer schrieb:

Was sind denn die Anforderungen die eine Distribution an den übergebenen Generator stellen darf?

26.5.1.3 Uniform random number generator requirements

A uniform random number generator g of type G is a function object returning unsigned integer values such
that each value in the range of possible results has (ideally) equal probability of being returned. [ Note: The
degree to which g’s results approximate the ideal is often determined statistically. — end note ]

Die Anforderungen werden hier also tatsächlich erfüllt. Es gibt, wie du schon anmerkst, keinen mathematischen Grund es anders zu verlangen. Die Zufallszahlen sind zwar schlecht (sowohl vor als auch nach dem man sie durch die Verteilungsfunktion gejagt hat), aber ihre Verteilung sollte richtig sein.

P.S.: Die Distributionen verlangen dann auch einen eben solchen uniform random number generator (§ 26.5.1.6, 2f). Nur um das nochmal klar zu stellen, falls es nicht offensichtlich war.

hustbaer

Danke

Und was sind die Anforderungen an min/max?

SeppJ

hustbaer schrieb:

Und was sind die Anforderungen an min/max?

min < max

Zumindest beim GCC klappt das auch wie man erwartet, d.h. es wird gewartet, bis genügend Information gesammelt wurde:

#include <random>
#include <iostream>
#include <functional>
#include <map>

struct poor_mans_device
{
  std::mt19937 gen; 
  std::uniform_int_distribution<int> dis = std::uniform_int_distribution<int>(1, 6);
  typedef int result_type;
  static constexpr result_type min() {return 1;}
  static constexpr result_type max() {return 6;}
  result_type operator()() { return dis(gen); }
};

int main()
{
  poor_mans_device gen;
  std::uniform_int_distribution<> dis(10, 36);
  std::map<int, int> map;

  for (int n=0; n<1000000; ++n)
    ++map[dis(gen)];
  for(int i = 10; i < 37; ++i)
    std::cout << i << ' ' << map[i] << '\n';
}

Sollte Gleichverteilung ergeben.

Oder, um es noch extremer zu machen:

#include <random>
#include <iostream>
#include <functional>
#include <map>

struct poor_mans_device
{
  int min_, max_;
  std::mt19937 gen; 
  std::uniform_int_distribution<int> dis;
   typedef int result_type;
  result_type min() const {return min_;}
  result_type max() const {return max_;}
  result_type operator()() { return dis(gen); }
  poor_mans_device(int min, int max): min_(min), max_(max), dis(min_, max_) {}
};

int main()
{
  poor_mans_device poor(0,1);
  poor_mans_device intermediate(0,1000);
  poor_mans_device good(0,1000000);

  std::uniform_int_distribution<> dis(10, 36);
  std::map<int, int> map_poor, map_intermediate, map_good, map_mixed;

  for (int n=0; n<1000000; ++n)
    {
      for(int i = 1; i < 3; ++i)
        {
          ++map_poor[dis(poor)];
          ++map_intermediate[dis(intermediate)];
          ++map_good[dis(good)];
        }
      ++map_mixed[dis(poor)];
      ++map_mixed[dis(intermediate)];
      ++map_mixed[dis(good)];
    }

  for(int i = 10; i < 37; ++i)
    std::cout << i << '\t' << map_poor[i] << '\t'
              << map_intermediate[i] << '\t' 
              << map_good[i] << '\t'
              << map_mixed[i] << '\n';
}

Die Distribution muss also dynamisch mit sich ändernden Generatoren auskommen.

P.S.: Ein bisschen Overengineered ist das schon :p . Wenn Geschwindigkeit eine kritische Rolle spielen würde, würde ich mir den Einsatz nochmal überlegen. Da ist mindestens eine Abfrage drin, ob min und max vom Generator ausreichen oder ob mehrere Ziehungen nötig sind, die man in 99.9% aller Fälle nicht braucht und die immer die gleiche Antwort hat.

Fytch

seldon schrieb:

@asfdlol: Zeig doch mal den kompletten Code, der das Verhalten erzeugt.

Den habe ich leider nicht mehr (es erschliesst sich jedoch alles aus dem OP bis auf den Bereich vom Generator). Ich habe es auch nicht hinbekommen es zu reproduzieren, sondern bekomme stattdessen Verteilungen wie sie auch cooky451 etwa erhalten hat. Wie gesagt, vielleicht hatte ich irgendwo einen kleinen Fehler drin

seldon schrieb:

Mal außen vor, dass der Generator keine vereinfachte std::shuffle_order_engine

Sicher? Meine Engine nimmt doch immer einen Range -grossen Block von einer hypothetischen Engine, die konsequtive Werte modulo Range liefert, und gibt diese durchgemischt wieder.

seldon schrieb:

natürlich nicht gleichverteilt ist (wie hoch ist die Wahrscheinlichkeit, mit ihm dreimal hintereinander die gleiche Zahl zu ziehen?)

Der von dir genannte Fall ist kein Kriterium für Gleichverteilung. Für meinen Generator gilt die Laplace-Formel, womit er gleichverteilt ist.

Nein, die PermutationEngine ist nicht gleichverteilt. Die erste gezogene Zahl kommt noch mit gleicher Wahrscheinlichkeit für alle Werte daher, die zweite schon nicht mehr -- der eben gezogene Wert kann nicht wieder kommen, und die anderen Werte werden entsprechend wahrscheinlicher. Die Laplace-Bedingung ist dann auch nicht erfüllt.

Eine shuffle_order_engine funktioniert so, dass aus einem bestehenden Array von Zufallszahlen zufällig eine ausgewählt wird (die ist dann der Rückgabewert) und ihr Slot mit einer aus einem gewrappten Zufallszahlengenerator neu gezogenen Zahl überschrieben wird. Sowohl kann aus dem gewrappten Generator die selbe Zahl erneut gezogen werden als auch der selbe Slot zweimal hintereinander ausgewählt. Die shuffle_order_engine ist gleichverteilt, wenn der gewrappte Zufallszahlengenerator es ist, aber den formellen Nachweis dafür müsste ich herleiten oder im Knuth nachschlagen.

Bei der uniform_int_distribution habe ich mich geirrt; die muss anscheinend tatsächlich auch hochskalieren können. Gut, die formalen Bedingungen für den Generator, den die uniform_int_distribution verlangt, erfüllt die PermutationEngine nicht, aber in diesem speziellen Anwendungsfall sollte eine zustandslose Implementierung von uniform_int_distribution Werte liefern, die so aussehen, als sei alles in Ordnung. Meine Vermutung mit der PermutationEngine<10> ist damit hinfällig.

hustbaer

seldon schrieb:

Nein, die PermutationEngine ist nicht gleichverteilt. Die erste gezogene Zahl kommt noch mit gleicher Wahrscheinlichkeit für alle Werte daher, die zweite schon nicht mehr -- der eben gezogene Wert kann nicht wieder kommen, und die anderen Werte werden entsprechend wahrscheinlicher. Die Laplace-Bedingung ist dann auch nicht erfüllt.

Wenn du forderst dass die Zahl die bei einer Ziehung rauskommen kann unabhängig von allen Zahlen davor ist, dann erfüllt das kein einziger PRNG.

Natürlich ist diese Eigenschaft - bzw. eine gute Annäherung daran - für viele Dinge wichtig. Deswegen verwendet man ja auch für viele Dinge Generatoren die u.A. in möglichst vielen Dimensionen gleichverteilt sind.

Ich kann aus den Artikeln zum Thema Gleichverteilung auch keine solche Forderung rauslesen. Da steht die Wahrscheinlichkeit muss für alle Zahlen gleich sein. Und das ist sie bei dem hier diskutierten Generator ja auch, wenn man kein Wissen über die davor gezogenen Zahlen hat. Und wenn man es hat, siehe oben, dann erfüllt das kein einziger PRNG.

Ein Generator, der 1 bis 100 hochzählt und danach wieder bei 1 anfängt, erzeugt keine gleichverteilten Zufallszahlen, bloß weil du beim ersten Ziehen nicht weißt, wo du dich in der Folge befindest.

Ohne irgendetwas über den inneren Zustand einer PermutationEngine zu wissen, kann ich zwei Zahlen ziehen und nachweisen, dass für mindestens eine der Ziehungen die Laplace-Bedingung nicht gegolten hat, und damit ist der Generator nicht gleichverteilt.

cooky451

hustbaer schrieb:

Und das ist sie bei dem hier diskutierten Generator ja auch, wenn man kein Wissen über die davor gezogenen Zahlen hat. Und wenn man es hat, siehe oben, dann erfüllt das kein einziger PRNG.

Ja doch schon, wenn man nur gezogene Zahlen kennt und nicht den gesamten PRNG Zustand, erfüllen das alle kryptographisch sicheren PRNGs, zumindest über eine bestimmte Periode.

hustbaer

@cooky451
Genau. Selbst ein kryptographisch sicherer PRNG ist nicht unendlich aperiodisch - genau das ist ja der Punkt.

@seldon
Wo ist dann die Grenze?
Ist ein LCG mit Periode 100 gleichverteilt?
Einer mit Periode 1000? 10000? .... 10^10?
Ein 16 Bit LFSR Generator? 32 Bit? 64 Bit?

Woraus ich hinaus will, ist: alle PRNGs haben schwächen, und man kann nicht einfach beliebig irgendwo eine Grenze ziehen, und alles was auf der einen Seite ist gleichverteilt nennen und was auf der anderen Seite ist nicht gleichverteilt.

Die Forderung dass die Kenntniss vorher gezogener Zahlen keinerlei Rückschlusse über die nächste gezogene Zahl erlaubt erfüllt kein einziger PRNG.
Die Forderung dass, wenn man viele Zahlen hintereinander zieht, jede Zahl inetwa gleich oft auftritt, erfüllen sie alle.

Nexus

Meines Erachtens sind Gleichverteilung und Abhängigkeit nacheinanderfolgender Zahlen zwei verschiedene Dinge. Beides sind Qualitätsmerkmale eines PRNGs.

So ist eine Münze, die immer abwechselnd auf Kopf und Zahl liegt, sehr wohl gleichverteilt, obwohl eine offensichtliche Abhängigkeit nacheinanderfolgender Resultate besteht. Wie voraussagbar diese ist -- und zwar anhand der bisher gesehenen Zahlen, und nicht durch die Kenntnis der Implementierung -- entscheidet unter anderem, wie "gut" ein PRNG ist. Wie hustbaer sagt, kann man die nächste Zahl durch die Natur deterministischer Generatoren immer voraussagen, aber ob das von einem Blackbox-Standpunkt aus ebenfalls so gut möglich ist, ist eine andere Sache.

Ah. Ja, streng mathematisch gesehen sind keine PRNGs gleichverteilt, das ist ein Einwand. Letztendlich streiten wir uns wohl über die Qualität von Näherungen.

Das Problem mit der vorliegenden Näherung (und letztlich mit der Definition von Gleichverteilung, die lediglich das gleich häufige Vorkommen von Zahlen verlangt) ist, dass die Eigenschaft der "Gleichverteilung" bei Operationen verloren geht, in denen sie bei mathematischer Gleichverteilung erhalten bliebe. Im vorliegenden Fall zum Beispiel würden bei der Hochskalierung sämtliche Fälle ausgeschlossen, für die aus der Engine zweimal der selbe Wert gezogen werden muss. Mit gcc 4.9 kriege ich mit folgendem Code:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

template<unsigned int Range>
class PermutationEngine
{
public:
    typedef unsigned int result_type;

private:
    result_type Permutation[Range];
    std::size_t State;
    void Shuffle()
    {
        std::random_shuffle(std::begin(Permutation), std::end(Permutation));
    }

public:
    PermutationEngine()
        : State(0)
    {
        for(std::size_t i = 0; i < Range; ++i)
        {
            Permutation[i] = i; // evtl. static_cast<result_type>(i)
        }
        Shuffle();
    }

    static /*constexpr*/ result_type min()
    {
        return 0;
    }
    static /*constexpr*/ result_type max()
    {
        return Range - 1;
    }

    result_type operator() ()
    {
        result_type Result = Permutation[State];
        if(++State == Range)
        {
            State = 0;
            Shuffle();
        }
        return Result;
    }
};
template<>
class PermutationEngine<0>;

int main() {
  PermutationEngine<10> rng;
  std::uniform_int_distribution<unsigned> dist(0, 99);
  std::vector<unsigned> vec(100);

  for(std::size_t i = 0; i < 10000000; ++i) {
    ++vec[dist(rng)];
  }

  for(std::size_t i = 0; i < vec.size(); ++i) {
    std::cout << i << ":\t" << vec[i] << '\n';
  }
}

folgendes Ergebnis:

volkard

seldon schrieb:

Ein Generator, der 1 bis 100 hochzählt und danach wieder bei 1 anfängt, erzeugt keine gleichverteilten Zufallszahlen, bloß weil du beim ersten Ziehen nicht weißt, wo du dich in der Folge befindest.

Ähm, doch?
Alle 100 Zahlen kommen gleich oft vor, dachte das sei die Gleichverteilung.

Nexus

Gleichverteilung ist eine statistische Verteilung (wie Normalverteilung, Poissonverteilung, etc.) und hat zunächst einmal gar nichts mit Zufallsgeneratoren zu tun.

Da andere Kriterien wie Abhängigkeit hineinzuinterpretieren halte ich nicht für förderlich. Das führt nur dazu, dass wir uns einen neuen Begriff ausdenken müssen, wenn wir sagen wollen, dass die Werte gleich oft auftreten.

hustbaer

@seldon
Dass der Generator "schlechte" Zahlen ausspuckt (ohne jetzt "schlecht" genauer zu definieren), hab' ich doch eh schon geschrieben. Ich denke das ist klar

seldon schrieb:

Letztendlich streiten wir uns wohl über die Qualität von Näherungen.

Nö, wir streiten über die Bedeutung des Begriffs "gleichverteilt".

seldon schrieb:

Das Problem mit der vorliegenden Näherung (und letztlich mit der Definition von Gleichverteilung, die lediglich das gleich häufige Vorkommen von Zahlen verlangt) ist, dass die Eigenschaft der "Gleichverteilung" bei Operationen verloren geht, in denen sie bei mathematischer Gleichverteilung erhalten bliebe.

Auch das ist theoretisch bei allen PRNGs der Fall. Die Frage ist nur wie kompliziert die Operationen sein müssen mit denen man die Gleichverteilung zerstören kann.

Und was das "nie 2x hintereinander die selbe Zahl" Problem angeht: das Problem haben relativ viele andere Generatoren. LCGs und LFSR Generatoren spucken z.B. auch nie 2x hintereinander die selbe Zahl aus.

Entschuldigung für die lange Pause; ich bin die letzten Tage zu nichts gekommen. Ich hoffe, es zählt noch nicht als Thread-Nekromantie.

So, wie ich das mal gelernt habe, ist Gleichverteilung so definiert, dass eine Zufallsvariable gleichverteilt ist, wenn die Wahrscheinlichkeit, dass ein Element der Ereignismenge eintritt, für alle Elemente der Ereignismenge gleich ist. Da bei PRNGs (und das hatte ich zunächst schlicht nicht bedacht) immer schon vorher feststeht, was die nächste Zahl sein wird, können sie unter dieser Definition nicht gleichverteilt sein -- im Grunde handelt es sich bei ihnen schlicht nicht um Zufallsvariablen. Das meine ich, wenn ich von "Näherungen" spreche.

Wie man den Begriff der Gleichverteilung auf Pseudozufallszahlen überträgt, ist eine spannende Frage, aber allein die gleiche Häufigkeit der einzelnen Werte kann aus meiner Sicht nicht ausreichen, ohne den Charakter der stochastischen Definition völlig zu verlieren. Die Antwort, die sich mir aufdrängt, ist der χ²-Test, detailliert beschrieben z.B. in "The Art of Computer Programming, Vol. 2, Seminumerical Algorithms" in Sektion 3.3.1 (in der dritten Auflage). Kurz umrissen wird aus einer Stichprobe eine Prüfgröße

V = Σ((Y_i - np_i)² / np_i)

berechnet richtig sind, χ²-verteilt ist. Hier ist Y_i = wie oft ein bestimmter Wert gezogen wurde, p_i = vermutete Wahrscheinlichkeit, dass der Wert gezogen wird, n = Anzahl der Ziehungen, daher np_i = erwarteter Wert von Y_i. i läuft von 1 bis k, wobei k die Anzahl möglicher Werte ist.

Bei einer PermutationEngine<k> ist die Abweichung der Prüfgröße von der zugehörigen χ²-Verteilung sehr groß (V liegt immer nahe bei 0), also kann man sie meines Erachtens nicht als gleichverteilt bezeichnen. Du hast Recht, dass das auch für einen linearen Kongruenzgenerator zutrifft, wenn man ihn über seine gesamte Wertemenge betrachtet und nicht vorher auf ein kleineres Intervall herunterrechnet.