schlechte zufallsfahlen ?

hallo,
ich generiere in C++ mit rand() zufallszahlen zwischen 1-100.

Um mal zu testen wie gut die Zufallszahlen sind, zähle ich bei gewürfelten jeder zahl zwischen 1 und 50 einen counter hoch.

Dh bei 10000 zufallszahlen müsste der counter bei ca 5000 wenn die zufallszahlen gut sind oder ? ...

leider errecihe ich aber nur 4378, also kommen die zahlen 1-50 häufiger vor als die zahlen 51-100.

gibts da andere möglichkeiten , bessere Zufallszahlen zu würfen ?

Danke
chris

CStoll

Erstens glaube ich nicht, daß diese Abweichung schon signifikant ist. Wie sieht das Ergebnis denn aus, wenn du einen anderen Seed-Wert verwendest (oder eine größere Stichprobe)?

Zweitens hat Marc++us einen sehr interessanten Artikel zum Thema Zufallszahlen geschrieben (schau mal ins Magazin zu "Zufälle gibt's"), der auch auf die Probleme der Verteilung eingeht - lesen, verstehen, umsetzen

Hallo

Ich hoffe, dass es hier keine Trittbrettfahrer gibt.

chrische

Artchi

In der boost sind noch spezielle Zufallszahlen-Libraries drin. Vielleicht helfen die.

hi,
danke für die Info, hab mir den Artikel mal durchgelesen, soweit verstanden und umgesetzt.

meine Berechnung der Zufallszahlen sieht jetzt so aus:

int ignore = (RAND_MAX / 10000) * 10000; 

				z = rand(); 
				while ( z > ignore )
				{
					z=rand();         
				}
				//
				zahl = (z%10000)+1;
				if (zahl <=5000) 
                                          counter++;

bei 8148576 Zufallszahlen sind 3566648 kleiner als 5000!

Also immer noch ~43% unter 5000.

@ chrische
Warum Trittbrettfahrer ?

Danke
Chris

CStoll

chri5 schrieb:

bei 8148576 Zufallszahlen sind 3566648 kleiner als 5000!

Also immer noch ~43% unter 5000.

Also das ist merkwürdig (ich hab' jetzt keine Lust auszurechnen, wie hoch die Signifikanz deines Tests ist) - könntest du die Verteilung noch ein wenig feiner aufdröseln? (und ändern sich die Werte möglicherweise, wenn du das Programm mehrfach durchlaufen lässt - mit unterschiedlichen Ausgangswerten für srand()?)

@ chrische
Warum Trittbrettfahrer ?

Bei dem Namen fragst du noch ;)?

Tachyon

Also 10000 Stichproben sind bei einer Monte-Carlo-Simulation, insbesondere, wenn deutlich mehr mit releativ geringem Zeitaufwand möglich sind, schon wenig.
Außerdem würde ich eher ein Histogramm als Mittel zu Analyse nehmen. Weiterhin sind die Standardabweichung und das arithmetische Mittel interessant.

chri5 schrieb:

hallo,
ich generiere in C++ mit rand() zufallszahlen zwischen 1-100.

Um mal zu testen wie gut die Zufallszahlen sind, zähle ich bei gewürfelten jeder zahl zwischen 1 und 50 einen counter hoch.

Dh bei 10000 zufallszahlen müsste der counter bei ca 5000 wenn die zufallszahlen gut sind oder ? ...

leider errecihe ich aber nur 4378, also kommen die zahlen 1-50 häufiger vor als die zahlen 51-100.

gibts da andere möglichkeiten , bessere Zufallszahlen zu würfen ?

Danke
chris

Irgendwas hast du falsch gemacht.

#include <stdlib.h>
int main()
{
    int counter = 0;

    for (int i = 10000; i; i--)
    {
         if ((rand()%100)+1 < 51)
            counter++;
    }
           // counter == 4975 !
    return 0;
}

tesuji

hi,
mit dem folgenden Programm habe ich rand() mit einem von mir geschriebenen Zufallszahlengenerator (Lehmersche lineare Kongruenzmethode) getestet. Verwendet wurde gcc. Ergebnisse siehe unten.

unsigned long lehmer(unsigned long s) // Lineare Kongruenzmethode nach Lehmer
{   static unsigned long a = 1, b = 4194301, c = 2147483647, z = b;
    z = (a + b * z) % c ;
    return z % s;
}
void test_lehmer()
{    long unsigned n = 100000, mp = RAND_MAX, iz1, od1=0, iz2, od2=0;
     double s1=0, ss1=0, zz1, mi1, va1, s2=0, ss2=0, zz2, mi2, va2;
     for (int i = 0; i < n; i++)
     { iz1 = lehmer(mp); iz2 = rand();
       if ( iz1 % 2 ) od1 ++; if ( iz2 % 2 ) od2 ++;
       zz1 =((double)iz1 / ((double)(mp)+ 1 ) );
       zz2 =((double)iz2 / ((double)(mp)+(double)(1)) );
       s1 += zz1; ss1 +=zz1*zz1; s2 += zz2; ss2 +=zz2*zz2;
     }
     cout << "Ergebnisse fuer Randomgenerator Lehmer (Periode: " << mp << ")" << endl;
     mi1 = s1 / n; va1 = ((ss1 - n * mi1*mi1)/n);
     cout << "Anzahl n: " << n << ", davon ungerade: " << od1 << ",   Summe: " << s1 << "  E(Summe): " << n / 2 << endl;
     cout << "Mittelwert: " << mi1 << ",   Varianz: " << va1 << ",   E(Varianz): " << 1.0/12 << endl;

     cout << "\nErgebnisse fuer Randomgenerator rand() (max. Periode: " << mp << ")" << endl;
     mi2 = s2 / n; va2 = ((ss2 - n * mi2*mi2)/n);
     cout << "Anzahl n: " << n << ", davon ungerade: " << od2 << ",   Summe: " << s2 << "  E(Summe): " << n / 2 << endl;
     cout << "Mittelwert: " << mi2 << ",   Varianz: " << va2 << ",   E(Varianz): " << 1.0/12 << endl;
     wait_return();

/* 
Ergebnisse für 10000 Zufallszahlen
----------------------------------
Ergebnisse fuer Randomgenerator Lehmer (Periode: 32767)
Anzahl n: 10000, davon ungerade: 5031,   Summe: 5028.66  E(Summe): 5000
Mittelwert: 0.502866,   Varianz: 0.084465,   E(Varianz): 0.0833333

Ergebnisse fuer Randomgenerator rand() (max. Periode: 32767)
Anzahl n: 10000, davon ungerade: 5035,   Summe: 5037.71  E(Summe): 5000
Mittelwert: 0.503771,   Varianz: 0.0834414,   E(Varianz): 0.0833333

Ergebnisse für 100000 Zufallszahlen
-----------------------------------
Ergebnisse fuer Randomgenerator Lehmer (Periode: 32767)
Anzahl n: 100000, davon ungerade: 50097,   Summe: 50046.9  E(Summe): 50000
Mittelwert: 0.500469,   Varianz: 0.083549,   E(Varianz): 0.0833333

Ergebnisse fuer Randomgenerator rand() (max. Periode: 32767)
Anzahl n: 100000, davon ungerade: 50145,   Summe: 50146.1  E(Summe): 50000
Mittelwert: 0.501461,   Varianz: 0.0832408,   E(Varianz): 0.0833333

Ergebnisse für 10000000 Zufallszahlen
-------------------------------------
Ergebnisse fuer Randomgenerator Lehmer (Periode: 32767)
Anzahl n: 10000000, davon ungerade: 4987790,   Summe: 5.00193e+006  E(Summe): 5000000
Mittelwert: 0.500193,   Varianz: 0.0834284,   E(Varianz): 0.0833333

Ergebnisse fuer Randomgenerator rand() (max. Periode: 32767)
Anzahl n: 10000000, davon ungerade: 5000153,   Summe: 4.99948e+006  E(Summe): 5000000
Mittelwert: 0.499948,   Varianz: 0.0833409,   E(Varianz): 0.0833333
*/
}

Mittelwerte und Varianzen der beiden Generatoren stimmen für 100000 und 10000000 relativ gut überein. Bei rand() sind von 10000000 Zufallszahlen 4999480 kleiner als 5000000, also 49,9948 Prozent. Auch Mittelwert und Varianz entsprechen mit 0.499948 und 0.083333 praktisch den Erwartungswerten von 1/2 und 1/12.

Wenn du nur 43 % erreichst, scheint irgendwas bei deiner Berechnung nicht zu stimmen. Welchen Compiler, Prozessor benutzt du?
Anzumerken ist noch, das die Anzahl der in einem Experiment verwendeten Zufallszahlen wesentlich kleiner als die Periode sein soll. Bei rand() ist die Periode gleich RAND_MAX, also 32767. lehmer hat eine max. Periode von 2147483647 (der Grund, warum ich den mal schrieb). Bei den im letzten Beispiel gewürfelten 10 000 000 Zufallszahlen gibt es also bereits 10 000 000 / 32767 = 305 Wiederholungen der gewürfelten Zufalszahlenfolge. Das ist für physikalische Experimente und auch für Dinge wie gestreute Speicherung recht ungünstig. Man sollte da Generatoren mit wesentlich größeren Perioden verwenden (Bei lehmer wären es 10000000 / 2147483647 = 0,0046 Wiederholungen gewesen. Zum Vergleich mit rand() wurde lehmer jedoch auch auf die Periode RAND_MAX begrenzt.)

viele Grüße von tesu (auf Nachtwache:)

tesuji

Hallo chri5
ich hab mir mal dein Programm angeschaut. Da stimmt ja wirklich nichts, siehe unten!

chri5 schrieb:

hi,
danke für die Info, hab mir den Artikel mal durchgelesen, soweit verstanden und umgesetzt.

meine Berechnung der Zufallszahlen sieht jetzt so aus:
int ignore = (RAND_MAX / 10000) * 10000; 

				z = rand(); 
				while ( z > ignore )
				{
					z=rand();         
				}
				//
				zahl = (z%10000)+1;
				if (zahl <=5000) 
                                          counter++;
bei 8148576 Zufallszahlen sind 3566648 kleiner als 5000!

Also immer noch ~43% unter 5000.

@ chrische
Warum Trittbrettfahrer ?

Danke
Chris

Wenn ich dein Programm bei mir laufen lasse, erhalte ich folgendes:
1. ignore hat den Wert 30000
2. Das z vor der Schleife hat den Wert 32650
3. In der Schleife wird z gleich 5272 gewürfelt, die Schleife also genau 1mal durchlaufen. Du würfelst also keine 8148576 Zufallszahlen.
4. zahl ist dann 5273
5. counter enthält den zufälligen Wert 1094795585 weil er nicht initalisiert ist (falls du doch init. hast, dann Entschuldigung).

So gehts also nicht.

vg tesu

ceplusplus

Nimm doch den http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.h

MfG

hi ceplusplus,
vielen Dank für diesen genialen Generator. Der schlägt rand() natürlich um Längen. Man muss ihn allerdings auch richtig anwenden, sprich programmieren können
Grüsse von Ney

@tesuji

das mein programm nicht so oft durchläuft ist mir schon klar, die while Schleife dient zu einem anderen Zweck!
CStoll hat mich auf einen Artikel im Magazin hingewiesen, vielleicht solltest die den auch mal durchlesen dann weist warum ich da ne while hab.
Kurz gesagt, am Beispiel:
zufallszahlengenerator 8 bit , also 0-255;
begrenze ich meine zufallszahlen mit modulo 200, kommen die zahlen 0-55 einmal öfter vor als die restliuchen deswegen wir bei zahlen > 201 nochmal gewürfelt.

Das ganze ist nur ein Ausschnitt aus meinem Programm, natürlich wird der counter mit 0 initialisiert und natürlich is da noch irgendwo ne for-schleife die 8148576 durchlaufen wird.

Danke das dich so viel mit meinem Programm befasst hast.

chris