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