Zufallszahl mit vorgegebener bit-Wahrscheinlichkeit

[A. S. (rava)]

Google hat mir nichts erzählt. Vielleicht hatte ich die falschen 
Begriffe?

Wie erzeuge ich aus einer Reihe von gleichverteilten random uint32_t 
Werten einen neuen random uint32_t Wert, in dessen bit-pattern Einsen 
mit einer Wahrscheinlichkeit p und Nullen mit einer Wahrscheinlichkeit 
1-p vorkommen?

Am Ende werde ich wohl ein paar Millionen dieser Zufallszahlen brauchen 
und p wird so gering sein, dass über all diese Zufallszahlen insgesamt 
nur ein paar Bits gesetzt sind.

p liegt also als float vor und Geschwindigkeit wäre ein Thema.
Hat schon mal jemand was über dieses Problem gelesen?

[Hippelhaxe (hippelhaxe)]

A. S. schrieb:

> Wie erzeuge ich aus einer Reihe von gleichverteilten
> random uint32_t Werten einen neuen random uint32_t Wert,
> in dessen bit-pattern Einsen mit einer Wahrscheinlichkeit p
> und Nullen mit einer Wahrscheinlichkeit 1-p vorkommen?

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.


> Hat schon mal jemand was über dieses Problem gelesen?

Nein -- aber Deine präzise Fragestellung suggerierte mir
im zweiten Durchdenken die Antwort...

HTH

[Gerald K. (geku)]

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

uint32_t generate_random_uint32_with_probability(double p) {
    uint32_t result = 0;
    uint32_t mask = 1;

    // Schwellenwert berechnen
    uint32_t threshold = (uint32_t)(p * (double)UINT32_MAX);

    for (int i = 0; i < 32; ++i) {
        uint32_t rand_value = rand();
        
        // Setze das Bit basierend auf der Wahrscheinlichkeit p
        if (rand_value <= threshold) {
            result |= mask;
        }

        mask <<= 1;
    }

    return result;
}

int main() {
    // Seed für den Zufallszahlengenerator setzen
    srand((unsigned int)time(NULL));

    double p = 0.7;  // Wahrscheinlichkeit für Einsen

    // Generiere den Zufallswert
    uint32_t random_value = generate_random_uint32_with_probability(p);

    printf("Generierter uint32_t Wert: %u\n", random_value);

    return 0;
}

[Daniel A. (daniel-a)]

`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>`.

[Rolf M. (rmagnus)]

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().

[Bradward B. (Firma: Starfleet) (ltjg_boimler)]

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.

[Daniel A. (daniel-a)]

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.

[Rolf M. (rmagnus)]

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)."

[Purzel H. (hacky)]

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.

[J. S. (engineer)]

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.

[Tilo R. (joey5337)]

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:
> 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.