Zufallszahl mit vorgegebener bit-Wahrscheinlichkeit

rand() liefert keine richtig zufälligen Werte, hat keine schön gleichmässige Verteilung, und der ganze int Bereich wird davon meist auch nicht ausgenutzt. Also möglichst immer vermeiden.

Unter Linux gibt es /dev/urandom, und getrandom in <sys/random.h>, die bringen gute Zufallswerte. Unter Windows gäbe es RtlGenRandom in der <ntsecapi.h>.

Daniel A. schrieb:

rand() liefert keine richtig zufälligen Werte, hat keine schön gleichmässige Verteilung, und der ganze int Bereich wird davon meist auch nicht ausgenutzt.

Das kann man pauschal nicht sagen, da es von der Implementation abhängt. Echten Zufall generiert sie zwar nicht (aber es ist unklar, ob das überhaupt nötig und gewünscht ist), aber gerade die Linux-Version hat einen guten Pseudozufallsgenerator hinter rand().

Es ist in Beitrag "Re: Zufallszahl mit vorgegebener bit-Wahrscheinlichkeit" nicht erkennbar, das auf die Forderung " erzeuge aus einer Reihe von gleichverteilten Werten einen neuen Wert " eingegangen wird.

Insbesonders auf Hinblick auf die Ergänzung:

"p wird so gering sein, dass über all diese Zufallszahlen insgesamt nur ein paar Bits gesetzt sind."

Da wird man wohl eine Routine schreiben müssen, die nur einmal initial zur Generierung der Folge den seed erzwingt und hilfreich wird es wohl sein p über die gesamte Folge (und nicht nur über 32 Zufallsereignisse) zu überwachen.

Nötig wäre auch die Information über welche Mindestanzahl n von bits p ermittelt wird.

Bei sehr kleinem p (bspw <0.01) wäre es auch überlegenswert, nicht für jedes bit den Zufallsgenerator anzuwerfen, sondern lediglich den Abstand zur nächsten Zufalls-'1' "auszuwürfeln". Diese Abstände dürften auch eine Zufallsreihe mit dem Erwartungswert 1/p sein.

Rolf M. schrieb:

Daniel A. schrieb:

rand() liefert keine richtig zufälligen Werte, hat keine schön gleichmässige Verteilung, und der ganze int Bereich wird davon meist auch nicht ausgenutzt.

Das kann man pauschal nicht sagen, da es von der Implementation abhängt. Echten Zufall generiert sie zwar nicht (aber es ist unklar, ob das überhaupt nötig und gewünscht ist), aber gerade die Linux-Version hat einen guten Pseudozufallsgenerator hinter rand().

Ja, ok. Hier ist RAND_MAX gleich INT_MAX, ja, vermutlich ist es hier gar nicht so schlecht.

--

Der Code von Gerald hat noch einen Fehler drin, wenn man rand() nimmt. Statt UINT32_MAX sollte man RAND_MAX nehmen, und statt uint32_t einen int.

Daniel A. schrieb:

Ja, ok. Hier ist RAND_MAX gleich INT_MAX, ja, vermutlich ist es hier gar nicht so schlecht.

Intern wird wohl noch mit mehr Bits gearbeitet. Aus der man-Page: "Die Periode dieses Zufallszahlengenerators ist sehr groß, ungefähr 16 * ((2^31) - 1)."

Ich empfehle einen Pseudozufallsgenerator mit einem Linear Feedback Schiebe Register, kurz LFSR. Nach der Groesse der Zahl ergibt sich die Periodenlaenge. Bei geeigneter Periodenlaenge merkt der Prozess die Wiederholung nicht. Waehrend also 20 Bit eine Wiederholung bei 2^20, nach einer Million, bietet, sinds bei 2^32 4 Milliarden. Und, 32 bit sind ja nicht wirklich riesig. Die Tabellen gehen bis 2^100. Die 0/1 Verteilung ist etwa strikt 50/50, resp alle Ganz-Zahlen im Register kommen genau einmal vor, ausser die Null.

Fuer spezielle Anforderungen, zB das Verhaeltnis 0 zu 1 wuerde ich mir also etwas zusammensetzen wie Ganzzahlen auslesen, zB 7 Bit (0..127) und dann zB < 77 ergibt eie Null, groesser ergibt eine Eins.

Ein FPGA kann diese Zahlen miit 100 MHz Geschwindigkeit herausstampfen.

Purzel H. schrieb:

Ein FPGA kann diese Zahlen mit 100 MHz Geschwindigkeit herausstampfen.

Du hast dann aber erst einmal nur ein Bit und musst mehrere nicht synchronisierte Generatoren parallel laufen lassen, um weitere zu haben. So ganz einfach ist das nicht. Da muss man sehr auf das Polynom aufpassen.

Man kann natürlich die Bits im LFSR hernehmen hat dann aber in jedem Fall vorhersagbare Folgen.

Wenn wirklich zufällige Zahlen gefordert sind, geht das mit einem Rauschgenerator. Dann gibt es keine vorhersagbare Reihenfolge und auch keine gleichmäßige Häufung der Zahlen, d.h. zu jedem Zeitpunkt hat jede Zahl die gleiche Wahrscheinlichkeit für ein Wiedererscheinen, was auch zu zweimal derselben Zahl hintereinander führen kann, was bei den meisten Pseudos rausgeschlossen ist.

Will man die Häufung ausgleichen, muss man mit Tabellen arbeiten, also alle gewünschten Zahlen hinterlegen, per Rauschen eine raussuchen und deren Auftrittswahrscheinlichkeit senken. Das geht über eine zweite Zufallszahl zwischen 0 und 100% die kleiner muss, als ein REF-Wert den man ständig um x verringert, wenn die Zahlaufgetreten ist. Langfristig tauchen dann alle Zahlen mit derselben Häufigkeit auf.

Einfacher geht es, wenn man zulässt, dass alle Zahlen in einem Durchlauf einmal vorkommen sollen. Das ergibt eine Tabelle mit einem vorgeschalteten Twister, z.B. Mersenne oder Masarglia, der idealerweise ebenfalls rauschgesteuert ist.

Will man die Häufigkeit irgendwo dazwischen haben, dann legt man z.B. 16 identische Tabellen mit allen gewünschten Zahlen an, jede kommt dann 16x vor und mischt dann diese große Tabelle.

Ich habe ein System im FPGA das so hänlich funktioniert und die Tabellen schiebt und die gerade aufgetretene Zahl null um sie hinten wieder anzufügen. Wenn die eine Weile gelaufen ist, hat man totalen Mischmasch, es kommen aber auf Dauer alle Zahlen statistisch wieder dran.

Bradward B. schrieb:

Bei sehr kleinem p (bspw <0.01) wäre es auch überlegenswert, nicht für jedes bit den Zufallsgenerator anzuwerfen, sondern lediglich den Abstand zur nächsten Zufalls-'1' "auszuwürfeln". Diese Abstände dürften auch eine Zufallsreihe mit dem Erwartungswert 1/p sein.

Das ist meiner Meinung nach keine gute Methode, um "guten" Zufall zu erzeugen. Der Grund ist: Die Ziel-Bitfolge soll normalverteilt sein. Die Abstände zwischen den wenigen gesetzten Bits müssten dann Poisson-verteilt sein. Diese Abstands-Zufallszahl ist imho noch schlechter effizient aus einem Zufalls-Bitstrom herzustellen. (Bitte nagelt mich hier nicht fest. Mein Verständnis von Zufall ist zwar noch einigermaßen ok, aber die genaue Mathematik habe ich nicht mehr im Kopf.)

Ganz grundsätzlich geht es bei dieser Frage imho hauptsächlich um die Effizienz: Wie viele Original-Zufallsbits muss man pro Ergebnisbit investieren?

Hippelhaxe hat imho schon in der ersten Antwort einen guten und sicheren Algorithmus beschrieben: Hippelhaxe schrieb im Beitrag #7682517:

Du erzeugst den Zielwert bitweise.

Du nimmst für jeden Zielwert einen Block von 32 gleich- verteilten Zufallszahlen und vergleichst sie alle mit max_int*p. Wenn die jeweilige Zufallszahl kleiner als dieser Schwellenwert ist, setzt Du das korrespondierende Bit des Zielwertes auf 1, andernfalls auf 0.

Schlecht ist hier nur die Effizienz: 32 Input-Bits für ein Ergebnis-Bit.

Wenn man binär "glatte" Zahlen für p hat, z.B. 1/4 oder 3/8, dann kann man die Effizienz steigern, indem man zur Entscheidung keine 32-Bit-Zahl erzeugt, sondern z.B. nur 2 oder 3 Original-Zufallsbits verbraucht, natürlich mit einem angepassten Schwellwert.

Es kommt halt sehr drauf an, welche Anforderungen du an deinen Ergebnis-Zufall hast. Ein ganz offensichtliches Maß dafür ist die Unabhängigkeit des Ergebnis-Bits von der vorangegangenen Bitfolge. Das bekommt man ganz sicher hin, wenn man jedes Bit "frisch" aus Originalzufall herstellt und keinen Zustandsspeicher hat.

Wenn du etwas entspannter sein kannst, kann es ausreichen, eine leeren Bitpuffer anzulegen und dann per Zufall eine plausible Anzahl von 1-Bits drüberzusprenkeln und dann einfach den Puffer von vorne nach hinten auszugeben.

Ebenso denkbar ist, vorab einen ganzen Satz solcher Puffer zu erzeugen, die dann epsilon-typische Zufallsfolgen enthalten. Dann brauchst du nur wenige Bit Originalzufall um auszuwählen, von welchem Puffer du das nächste Bit holen willst. (Jeder Puffer braucht dann einen eigenen Positionszähler.)

Wenn es noch entspannter sein darf: Entscheide zufällig, welchen dieser Puffer du als nächstes komplett abspielen willst. Dann ist im Ergebnis zwar wirklich nur noch sehr wenig echter Zufall drin, dafür ist es extrem CPU-effizient. Und könnte für deine Anwendung vielleicht trotzdem noch ausreichen.