Random integers met opzettelijke bias

[Kun]

Ik gebruik op dit moment PCG om random 32-bit integers te genereren. Ik heb vastgesteld dat elke van de 32 bit posities altijd 50/50 verdeeld is tussen 0 en 1. Dat is natuurlijk wat je normaal gesproken juist wilt.

Wat ik nu graag wil is dat die verhouding instelbaar is, dus bijvoorbeeld 30% 0-bits en 70% 1-bits per positie.

Ik heb geen flauw idee waar ik moet beginnen om dit voor elkaar te krijgen. Iemand een idee hoe ik dit het beste kan aanpakken?

[Firefly III]

-

[ Voor 100% gewijzigd door Firefly III op 21-10-2019 09:39 . Reden: Leeg ivm privacy ]

[McKaamos]

Je wil juist geen 50/50 scheiding, volgens mij.
Daarmee beperk je de getallen tot een minimum van 2¹⁶. (16 x 0 en 16x 1, in die volgorde)
Het idee van een random integer is dat het volledig random is en dus ook willekeurige verdeling heeft.

Verder wat JCE zegt.
Pak gewoon een random generator die bewezen goed is en ga dan selecties maken, als je een kleuring van het resultaat wil hebben.

Of je zoekt een prebuilt random generator waarbij je de minimale en maximale waarde zelf kan opgeven in de vorm van een Int.
2¹⁶ betekent dat je int minimaal 65535 (even uit mn hoofd) is en je maximum ergens in de 16miljoen.

[ Voor 22% gewijzigd door McKaamos op 20-11-2016 18:48 ]

[Kun]

Ik heb meerdere generators getest (o.a. PCG, XorShift+ en Mersenne Twister), maar die hebben allemaal gemiddeld per bit een verdeling van 50%. Volgens mij is dat prima, want je wilt volgens mij juist niet dat er verschil zit tussen de verschillende bits anders zou je namelijk vaker grote of kleine getallen genereren.

Daarom wil ik dus ook geen generator waarbij ik een minimale of maximale waarde kan opgeven, omdat daarmee een oneerlijke verdeling onstaat tussen de 32 bits.

Daarnaast wil ik ook niet een true of false waarde genereren, maar een random integer list waar in totaal bijvoorbeeld 70% van de bits 1 is.

[Sendy]

Gewoon XOR met een andere bitstring die 30% 0 bevat en 70% 1. (De string 0001111111 is genoeg, eventeel herhaald)

Oh ja. Niet dus. Dank allemaal.

[ Voor 15% gewijzigd door Sendy op 21-11-2016 20:02 ]

[Firefly III]

-

[ Voor 100% gewijzigd door Firefly III op 21-10-2019 09:39 . Reden: Leeg ivm privacy ]

[Rukapul]

Kun schreef op zondag 20 november 2016 @ 18:24:
Ik gebruik op dit moment PCG om random 32-bit integers te genereren.

Waarom gebruik je een RNG dat nog niet eens in een peer reviewed journal is gepubliceerd en van een professor zonder track record?

Sendy schreef op zondag 20 november 2016 @ 19:23:
Gewoon XOR met een andere bitstring die 30% 0 bevat en 70% 1. (De string 0001111111 is genoeg, eventeel herhaald)

Nee. Een vaste bitstring XOR-en met een willekeurige bitstring levert een willekeurige bitstring op.

Of anders bezien: neem positie i, de kans is met 50%/50% 1 of 0 op die positie, maar die statistiek verandert niet of je elke keer dat bit XOR-ed.

---

Een naieve oplossing kan zijn om je PRNG een getal te laten leveren in een bepaald domein, bv [0,9]. Indien het tot de onderste 30% (bv [0,2]) behoort dan kies je een 0, anders een 1. Een fatsoenlijke omgeving levert je een RNG die dat kan zonder noemenswaardige bias. Wil je het zelf construeren n.a.v. een random input bitstring dan staat er een wereld aan literatur tot je beschikking.

[ Voor 29% gewijzigd door Rukapul op 20-11-2016 20:01 ]

[Kun]

Rukapul schreef op zondag 20 november 2016 @ 19:45:
Waarom gebruik je een RNG dat nog niet eens in een peer reviewed journal is gepubliceerd en van een professor zonder track record?

Ik heb het zo opgezet dat het eenvoudig is om te wisselen van generator. De reden dat ik deze voor nu prefereer is, omdat ik deze zelf het getest op mijn eisen en omdat de performance erg goed is.

Rukapul schreef op zondag 20 november 2016 @ 19:45:
Nee. Een vaste bitstring XOR-en met een willekeurige bitstring levert een willekeurige bitstring op.

Of anders bezien: neem positie i, de kans is met 50%/50% 1 of 0 op die positie, maar die statistiek verandert niet of je elke keer dat bit XOR-ed.

Dit gaat inderdaad niet werken, in totaal wel, maar per bit-positie niet.

Rukapul schreef op zondag 20 november 2016 @ 19:45:
Een naieve oplossing kan zijn om je PRNG een getal te laten leveren in een bepaald domein, bv [0,9]. Indien het tot de onderste 30% (bv [0,2]) behoort dan kies je een 0, anders een 1. Een fatsoenlijke omgeving levert je een RNG die dat kan zonder noemenswaardige bias. Wil je het zelf construeren n.a.v. een random input bitstring dan staat er een wereld aan literatur tot je beschikking.

Bedoel je dat ik voor het samenstellen van elke 32-bit integer eerst 32 random getallen genereer en op basis van die getallen een 1 of een 0 (op basis van een range) toevoeg aan mijn nieuwe random nummer? Dit gaat wel werken, maar maakt het wel minstens 32 keer zo traag. Het werkt wel, maar is wel vrij omslachtig.

[pedorus]

JCE schreef op zondag 20 november 2016 @ 18:44:
Wat je zult moeten doen is zelf een gekleurde selectie maken uit de resultaten van de random generator. Maak een functie die 10 random bitjes accepteert. Als er 7 true zijn, geef je true terug, anders false?

Dit lijkt me helaas geen juiste methode om met 70% kans true te krijgen.. (kans hierop is 1-pbinom(6,10,0.5)=0.171875)

Sendy schreef op zondag 20 november 2016 @ 19:23:
Gewoon XOR met een andere bitstring die 30% 0 bevat en 70% 1. (De string 0001111111 is genoeg, eventeel herhaald)

En dit doet al helemaal niets..

Rukapul schreef op zondag 20 november 2016 @ 19:45:
Waarom gebruik je een RNG dat nog niet eens in een peer reviewed journal is gepubliceerd en van een professor zonder track record?

Lijkt er zelfs op dat het paper niet geaccepteerd is. Ik vermoed dat bijvoorbeeld de performance niet klopt en iets als XorShift sneller is. Zit me ook af te vragen waarom XorShift 64 'Many Issues' zou hebben terwijl XorShift* wel 'Excellent' is (maar ook wel een bekend issue heeft). In zijn algemeenheid is het per definitie mogelijk om 'issues' te ontdekken aan pseudo-rngs, maar de vraag is hoe erg deze nu echt zijn in een bepaalde praktische situatie.

Kun schreef op zondag 20 november 2016 @ 20:31:
Bedoel je dat ik voor het samenstellen van elke 32-bit integer eerst 32 random getallen genereer en op basis van die getallen een 1 of een 0 (op basis van een range) toevoeg aan mijn nieuwe random nummer? Dit gaat wel werken, maar maakt het wel minstens 32 keer zo traag. Het werkt wel, maar is wel vrij omslachtig.

Zou hopen dat je geen 32-bit rng meer gebruikt, dus dan is het zelfs 64 keer zo traag.. Het probleem zit hem een beetje in de nauwkeurigheid van die 70%. Als bijvoorbeeld 75% ok is, dan kun je 2 bits precies mappen op 1 bit. Alternatief kun je voor exact 70% ook 4 bits gebruiken, en bij A-F hex opnieuw 4 bits pakken, dan heb je maar ~6.3 bits per resulterende bit nodig. Als die 70% instelbaar is op zo'n beetje alles, en met maximale precisie, dan zit je aan die vertraging vast ja.

[DroogKloot]

De juiste oplossing hiervoor is rejection sampling: samples van je [biased; P(false)=0.3, P(true)=0.7] doel-distributie genereer je door samples van je [uniforme; P(false)=0.5, P(true)=0.5] bron-distributie conditioneel te accepteren met (in dit geval) kans 0.7 voor 1-bits en 0.3 voor 0-bits. Zoiets dus:

Python:

def reject_sample_bits(nbits = 32, prob = 0.7, urng = random.random):
    bits = [0] * nbits

    for i in xrange(nbits):
        bits[i] = (urng() <= prob)

    return bits

NB: de kans dat een bit i 1 wordt, is 0.7 (bij werkelijk onafhankelijke samples); de kans dat 70% van alle bits (~22 van de 32) op 1 komen te staan is binomiaal verdeeld.

En ja, goede statistiek is nu eenmaal traag.

[ Voor 3% gewijzigd door DroogKloot op 21-11-2016 06:31 ]