Gleichverteilung Random

[Erhard Henkes]

#include <iostream>
#include <random>
#include <fstream>

int main()
{
    std::random_device seed;
    std::mt19937 engine(seed());
    std::uniform_int_distribution<int> six(1,6);
    int H[6] = {0,0,0,0,0,0};
    const long long unsigned int limit = 100000000;

    std::ofstream myFile1("random.txt");

    for ( int i=1; i<= limit; ++i)
        myFile1 << six(engine);
    myFile1.close();

    std::ifstream myFile2("random.txt");
    char c;
    while (myFile2.get(c))
    {
        int number = c - '0';
        for (int i=0; i<6; ++i)
        {
            if (number == i+1)
                H[i]++;
        }
     }
     myFile2.close();

     for (int i=0; i<6; ++i)
     {
         std::cout << "H[" << i+1 << "] = " << H[i]++ << std::endl << std::endl;
     }

     std::cout << std::endl;
}

`H[1] = 16661072

H[2] = 16665331

H[3] = 16670582

H[4] = 16667616

H[5] = 16664761

H[6] = 16670638`

Ich hatte hier eine deutlich bessere Gleichverteilung erwartet.

[Bengo]

Der Zufall ist im allgemeinen nicht gleichverteilt.
Quatsch, hab die Doku zu uniform_int_distribution falsch interpretiert.

[TGGC]

Hast du denn mal berechnet, wie hoch die Wahrscheinlichkeit ist, dass die Zahlen so stark von 1000000/6 abweichen?

[Columbo]

Warum schreibste das alles in eine Datei?

#include <iostream>
#include <random>

int main()
{
	std::mt19937_64 engine(std::random_device{}());
	std::uniform_int_distribution<int> six(0,5);
	unsigned long count[6] {};
	for (unsigned long i = 0; i < 100'000'000; ++i)
		++count[six(engine)];
	for (int i = 0; i < 6; ++i)
		std::cout << i+1 << ": " << count[i] << '\n';
}

1: 16660742
2: 16665734
3: 16670581
4: 16662449
5: 16672299
6: 16668195

Zufall halt. Sieht mir aber sehr gleichverteilt aus.

[Columbo]

~Disclaimer: Was folgt kann furchtbar falsch sein und soll erst von SeppJ o.ä. bestätigt werden.~

TGGC schrieb:

Hast du denn mal berechnet, wie hoch die Wahrscheinlichkeit ist, dass die Zahlen so stark von 1000000/6 abweichen?

Wir reden hier quasi von der Verteilung von Würfelzahlen. Da N groß ist, dürfen wir mittels einer Normalverteilung die entsprechende Binominalverteilung $B(10^8, \frac{1}{6})$ approximieren:
$N(\frac{10^8}{6}, \frac{10^8\cdot 5}{36}) \approx N(16666667, 13888889)$

Nehmen wir bspw. $16672299$. Die Entfernung zum Erwartungswert beträgt $\frac{16672299-16666667}{3727} \approx 1.51$ Standardabweichungen. Die Wahrscheinlichkeit, dass ein Wert mehr als eine Standardabweichung vom Erwartungswert entfernt ist, ist über 30%. Und ~13% sind mehr als 1.5 Standardabweichungen entfernt. Ist also alles im Rahmen normaler Wahrscheinlichkeiten.

[Bengo]

Ist der Sinn der hier verwendeten Zufallsfunktion nicht, dass die Standartabweichung so klein wie möglich ist. Und das Ergebnis möglichst "gleichverteilt" ist?

[Erhard Henkes]

Ich erinnere mich dunkel, dass Volkard, Marcus und ich einen gleichverteilten Zufallszahlengenerator gebastelt haben. Muss hier irgendwo vergraben sein (Suchfunktion findet ihn nicht), sobald ich ihn gefunden habe, zeige ich ihn. Da waren die Zahlenhäufigkeiten im Milliardenbereich absolut gleich.

[SeppJ]

Erhard Henkes schrieb:

Ich erinnere mich dunkel, dass Volkard, Marcus und ich einen gleichverteilten Zufallszahlengenerator gebastelt haben. Muss hier irgendwo vergraben sein (Suchfunktion findet ihn nicht), sobald ich ihn gefunden habe, zeige ich ihn. Da waren die Zahlenhäufigkeiten im Milliardenbereich absolut gleich.

Dann waren die Zufallszahlen aber nicht gleichverteilt in dem Sinne, wie man das Wort normalerweise verwendet, da sie irgendwie korreliert wären. Siehe Arcoths Rechnung.

[hustbaer]

Wenn du ne Reihe willst wo alle Zahlen exakt gleich oft vorkommen dann nimm halt random_shuffle .

Ist dann aber wie SeppJ schon impliziert hat kein so guter Zufall mehr wie wenn du die "Fehler" in der Gleichverteilung akzeptierst.

[out]

Erhard Henkes schrieb:

Ich erinnere mich dunkel, dass Volkard, Marcus und ich einen gleichverteilten Zufallszahlengenerator gebastelt haben. Muss hier irgendwo vergraben sein (Suchfunktion findet ihn nicht), sobald ich ihn gefunden habe, zeige ich ihn. Da waren die Zahlenhäufigkeiten im Milliardenbereich absolut gleich.

Meinst du den Thread? https://www.c-plusplus.net/forum/47483-full

[Columbo]

@Erhard Mit deinem Code bekomme ich

1: 16665217
2: 16664601
3: 16669229
4: 16671513
5: 16667476
6: 16661964

Das ist nicht besser.

[Finnegan]

hustbaer schrieb:

Wenn du ne Reihe willst wo alle Zahlen exakt gleich oft vorkommen dann nimm halt random_shuffle .

Ach ne, das ist zu einfach! Ich schlage vor

for ( int i=1; i<= limit; ++i)

durch

for (;;)

zu ersetzen. Wenn er damit durch ist sind auch alle Zahlen exakt gleich oft vorgekommen
... ist aussedem schneller, weil man sich das inkrementieren und das Prüfen der Schleifeninvariante spart

[SeppJ]

Ist leider nicht 100% RandomNumberDistribution kompatibel (aber 99%):

#include <random>
#include <vector>
#include <limits>
#include <algorithm>

template< class IntType = int > class super_random_uniform_int_distribution
{
public:

  class param_type
  {
    IntType a, b;
    std::size_t range;
    std::vector< IntType > pool;
   public:
    typedef super_random_uniform_int_distribution<IntType> distribution_type;

    param_type(IntType a = 0, IntType b = std::numeric_limits<IntType>::max() ):
      a(a), b(b), range(b-a), pool(range+1) 
    { std::iota(pool.begin(), pool.end(), a); }

    friend distribution_type;
  };

  typedef IntType result_type;

  super_random_uniform_int_distribution( IntType a = 0,
                                            IntType b = std::numeric_limits<IntType>::max() ) : params(a, b) { }
  super_random_uniform_int_distribution( const param_type& params ): params(params) { }

  void reset() { params.range = params.b - params.a; }

  template< class Generator >
  result_type operator()( Generator& g )
  {
    std::uniform_int_distribution<std::size_t> d(0, params.range);
    std::size_t rn = d(g);
    IntType i = params.pool[rn];
    std::swap(params.pool[rn], params.pool[params.range]);
    if (params.range == 0) reset(); else --params.range;
    return i;
  }

  template< class Generator >
  result_type operator()( Generator& g, const param_type& params )
  {
    std::uniform_int_distribution<std::size_t> d(0, params.range);
    std::size_t rn = d(g);
    return params.pool[rn];
  }

  result_type a() const { return params.a; }
  result_type b() const { return params.b; }

  param_type param() const { return params; }
  void param( const param_type& params ) { this->params = params; }
  result_type min() const { return a(); }	
  result_type max() const { return b(); }
private:
  param_type params;
};

#include <iostream>
int main()
{
  std::random_device rd;
  std::mt19937 gen(rd());
  super_random_uniform_int_distribution<> six(1, 6);
  int H[6] = {0,0,0,0,0,0};
  const long long unsigned int limit = 100000001;
  for ( long long unsigned int i=0; i<= limit; ++i )
    ++H[six(gen)-1];
  for (int i=0; i<6; ++i)
    {
      std::cout << "H[" << i+1 << "] = " << H[i]++ << "\n\n";
    }  
}

(Operatoren ==, !=, << und >> überlasse ich als Fleißaufgabe dem geneigten Leser)

H[1] = 16666667

H[2] = 16666667

H[3] = 16666667

H[4] = 16666667

H[5] = 16666667

H[6] = 16666667

Eindeutig perfekter Zufall

[volkard]

auch nicht schlecht

unsigned int myRand()//geringe Abweichungen bei COUNT GROUP BY myRand%egal und lecker schnell
{
   static x=0;
   return x++;
}

[volkard]

Übringens hängt dem mt der Ruf an, ein wenig *zu gleichverteilt* zu sein, was so die Ergebnisse von diehard und Konsorten angeht.

[hustbaer]

@SeppJ
Falls du es schaffst die Distribution einer Online-Roulette Bude anzudrehen lass es mich bitte wissen

[SeppJ]

hustbaer schrieb:

@SeppJ
Falls du es schaffst die Distribution einer Online-Roulette Bude anzudrehen lass mich es mich bitte wissen

Hmm... Vielleicht sollte ich die Klasse einfach super_random_uniform_int_distribution nennen und hier so stehen lassen oder auf github veröffentlichen. Irgendein fauler Programmierer wird sicherlich darüber stolpern und sie einfach so übernehmen

[hustbaer]

Ja, mach mal!

[volkard]

SeppJ schrieb:

hustbaer schrieb:

@SeppJ
Falls du es schaffst die Distribution einer Online-Roulette Bude anzudrehen lass mich es mich bitte wissen

Hmm... Vielleicht sollte ich die Klasse einfach super_random_uniform_int_distribution nennen und hier so stehen lassen oder auf github veröffentlichen. Irgendein fauler Programmierer wird sicherlich darüber stolpern und sie einfach so übernehmen

Nee, schauen wir vom Mersenne Twister ab, der auf allen Architekuren, wo ich ihn gemessen hatte die veröffentlichten Zahlen um Faktor 4 und mehr unterschritten hatte, ein Jahrzehnt(!) lang. Inzwischen hat er aufgeholt. Er war von Anfang an ungepüft ge-hype-d.

Nennen wir ihn zum Beispiel GHRTumbler und stützen uns (angeblich) auf die GHR mit lauter Hyperlinks auf die "generalized Riemann hypothesis". Statt den GHRTumbler zu erklären wird die GHR erklärt. Minimales FaselBlasel dazu für den GHRTumbler. Als Veröffentlicher sei mal spaßig und tauche als Portugiese auf.

Wenn Du es übertreiben willst, such Dir als Doktorvater einen kürzlich verstorbenen möglichst bekannten Mathematiker aus. Das wird keiner prüfen. Türlich keinen Portugiesen, sondern einen von wo man die Uni kennt und (MIT) oder (Stanford Uni) dranschreibt.

lass mich es mich bitte wissen

[Columbo]

Wir sollten Jürgen Wolf bestechen, damit er "PRNGs von A bis Z" schreibt und darin speziell für Roulette-Tische konzipierte Zufallsgeneratoren preist, deren Code von SeppJ stark mittels Templates entstellt und auf mehrere hundert LOCs gestreckt wurde. Auf den Einband kommt "Das umfassende PRNG-Handbuch zum Lernen und Nachschlagen! Einsteiger erhalten eine gründliche und kompetente Einführung in moderne Pseudo Zufallszahlen-Generatoren. Viele praktische Beispiele und präzise Erläuterungen garantieren einen schnellen Lernerfolg. [..]"
Und Wolfs Standardspruch "Mein Traum ist es, im Westen Kanadas zu leben. Und Bücher auf der Veranda schreiben."

Das ganze wird dann von einem bezahlten Rezensenten in den Himmel gelobt.