Is pi een goede generator voor willekeurige getallen?

Een deel van wat ik doe, is het bestuderen van typisch gedrag van grote combinatorische structuren door te kijken naar pseudorandom-instanties. Maar veel commercieel verkrijgbare pseudowillekeurige nummergeneratoren hebben defecten gekend, waardoor ik me afvraag of ik alleen de cijfers (of bits) van $ \ pi $ zou moeten gebruiken.

Een collega van mij zegt dat hij "ergens gelezen" heeft dat de cijfers van $ \ pi $ geen goede generator voor willekeurige getallen zijn. Misschien denkt hij aan het artikel "Een onderzoek naar de willekeurigheid van de cijfers van $ \ pi $" door Shu-Ju Tu en Ephraim Fischbach. Weet iemand dit artikel? Sommige van de pers die het kreeg (zie bijvoorbeeld http://news.uns.purdue.edu /html4ever/2005/050426.Fischbach.pi.html ) klonk het alsof $ \ pi $ niet zo'n goede bron van willekeur was, maar de samenvatting voor het artikel zelf (zie http://adsabs.harvard.edu/abs/2005IJMPC..16..281T ) suggereert het tegenovergestelde.

Weet iemand van problemen met het gebruik van $ \ pi $ op deze manier? Als u de cijfers van $ \ pi $ gebruikt, moet u er natuurlijk voor zorgen dat u cijfers die u al elders in uw experiment heeft gebruikt, niet opnieuw gebruikt.

Mijn gevoel is dat je de cijfers van $ \ pi $ moet gebruiken voor Monte Carlo-simulaties. Als u een commerciële RNG gebruikt en u tot valse conclusies komt, heeft u tijd verspild en collega's misleid. Als je $ \ pi $ gebruikt en het leidt je tot het publiceren van valse conclusies, heb je nog steeds tijd verspild en collega's misleid, maar je hebt ook een patroon gevonden in de cijfers van $ \ pi $!

42
Ik betwijfel het. Ik ben persoonlijk veel gelukkiger in het geloven van een gepubliceerd bewijs (dat ik geen fout kan vinden) dan de uitvoer van een soort RNG die met de hand is gebouwd in de echte wereld.
toegevoegd de auteur DavidEBest, de bron
toegevoegd de auteur Deepak Shenoy, de bron
Zijn er eigenlijk voorbeelden waarin commerciële RNG's hebben geleid tot valse conclusies in een gepubliceerd artikel?
toegevoegd de auteur Assaf Lavie, de bron
Er zijn gevallen waarin pseudowillekeurige nummergenerators kunnen leiden tot onjuiste simulatieresultaten (zie bijvoorbeeld 'Gevoeligheid van ballistische afzetting voor Pseudorandom-nummergeneratoren' door D'Souza, Bar-Yam en Kardar (Physical Review E 57 (1998), 5044- 5052), mae.ucdavis.edu/dsouza/Pubs/bdrng.final_pre.pdf ). Dit zijn niet echt goede PRNG's, zeker geen cryptografische, maar veel simulaties gebruiken de slechte PRNG die geïmplementeerd wordt in hun favoriete programmeertaal, dus dit kan een echt probleem zijn.
toegevoegd de auteur brasofilo, de bron

11 antwoord

Strikt genomen zijn er enkele bekende patronen in de cijfers van $ \ pi $. Er zijn enkele bekende resultaten over hoe goed $ \ pi $ kan worden benaderd door rationals, wat impliceert (bijvoorbeeld) dat we a priori weten dat de volgende $ n $ als-nog-niet-gecorrigeerde cijfers van $ \ pi $ kan niet allemaal nul zijn (voor een expliciete waarde van $ n $ dat ik op dit moment te lui ben om te berekenen). In de praktijk zijn deze "patronen" echter zo zwak dat ze geen Monte Carlo-experimenten zullen beïnvloeden.

De belangrijkste beperking van het gebruik van de cijfers van $ \ pi $ kan de rekensnelheid zijn. Afhankelijk van hoeveel willekeurige cijfers je nodig hebt, kan het berekenen van nieuwe cijfers van $ \ pi $ een computationeel knelpunt worden. Hoe verder u komt, hoe moeilijker het wordt om meer cijfers van $ \ pi $ te berekenen.

Als u zich zorgen maakt over de kwaliteit van willekeurige getallen die u krijgt, kunt u cryptografische willekeurige-nummergeneratoren gebruiken. Het vinden van een patroon in de willekeurige nummergenerator Blum-Blum-Shub zou bijvoorbeeld waarschijnlijk een nieuw algoritme opleveren voor het berekenen van grote gehele getallen! Generatoren van cryptografische willekeurige getallen zullen langzamer draaien dan de "commerciële" willekeurige getallengeneratoren waar je het over hebt, maar je kunt er zeker enkele vinden die sneller cijfers zullen genereren dan algoritmen voor het berekenen van $ \ pi $ will.

43
toegevoegd
Ik heb onlangs de literatuur gecontroleerd en het lijkt erop dat ik een beetje verkeerd schrijf over een "expliciete waarde van $ n $". Salikhov bewees dat de irrationaliteitsmaat van $ \ pi $ minder is dan $ 8 $, wat impliceert dat er bijvoorbeeld $ n_0 $ bestaat voor alle $ n> n_0 $, de $ n $ th tot en met de $ 8n $ th bits van $ \ pi $ kan niet allemaal nul zijn, maar voor zover ik heb kunnen zien, is er geen effectieve bovengrens voor de grootte van $ n_0 $.
toegevoegd de auteur Joel Brown, de bron

In technische zin, nee. Een goede pseudowillekeurige nummergenerator zou er een zijn die u kunt aansluiten op elk willekeurig algoritme en verwacht hetzelfde gedrag te zien dat u zou verwachten van een echte willekeurige nummergenerator. Een manier om hier een technische definitie van te maken, is te zeggen dat de pseudowillekeurige nummergenerator niet kan worden onderscheiden van echt willekeurige (met waarschijnlijkheid weg van 1/2 gelimiteerde) door elke polynomiale tijdtest.

Maar de cijfers van π kunnen duidelijk van willekeurig worden onderscheiden door een polynoom-tijdtest, namelijk een test die de cijfers van π berekent en vergelijkt met uw veronderstelde willekeurige volgorde.

Om dezelfde reden kan geen volledig deterministische sequentie een goede willekeurige reeks zijn. Om in deze definitie te passen, moet je in plaats daarvan een pseudowillekeurige nummergenerator gebruiken die een aantal n werkelijk willekeurige bits als een invoerzaad nodig heeft en daaruit een langere reeks (polynoom in n) van pseudorandombits genereert die niet van willekeurig door te onderscheiden zijn door een polynoomtijdalgoritme.

19
toegevoegd
Ja, al deze entropie moet ergens vandaan komen! Omgekeerd was het een groot probleem met ENIGMA-decodering.
toegevoegd de auteur Edward Nunn, de bron

Ook relevant is de formule Bailey-Borwein-Plouffe

$$ \ pi = \ sum_ {i = 0} ^ {\ infty} \ frac1 {16 ^ i} \ left (\ frac {4} {8i + 1} - \ frac {2} {8i + 4} - \ frac {1} {8i + 5} - \ frac {1} {8i + 6} \ right) $$

die een zekere voorspelbaarheid aangeeft in de basis-16 cijfers van $ \ pi $.

18
toegevoegd
maar toch +1 omdat ik denk dat deze formule echt cool is.
toegevoegd de auteur DavidEBest, de bron
zie de opmerking van Steve.
toegevoegd de auteur DavidEBest, de bron
Ik ben het ermee eens dat het een coole formule is (en nuttig om op te starten), maar hoe geeft dit 'voorspelbaarheid' aan, afgezien van het feit dat de computationele complexiteit van het berekenen van een enkel cijfer of een reeks cijfers die er gebruik van maakt vrij laag is?
toegevoegd de auteur Edward Nunn, de bron
@Victor: Is dat niet wat "voorspelbaarheid" betekent?
toegevoegd de auteur JanC, de bron
Ik zou willen dat mensen geen naakte links plaatsen. Ik volg ze zelden.
toegevoegd de auteur JanC, de bron

Ik denk dat het afhangt van je aanvraag.

Ik zou zeggen nee als je de willekeurige getallen gebruikt om cryptografische sleutels te genereren, dan open je jezelf onmiddellijk voor aanvallen, omdat de aanvaller waarschijnlijk je willekeurige nummergenerator kan nabootsen, en dus voeg je een zwakke link toe in de keten.

7
toegevoegd
Daar ben ik het mee eens. Als je een Monte Carlo-experiment wilt doen, kan $ \ pi $ werken, hoewel het waarschijnlijk langzamer is dan, laten we zeggen, de Mersenne Twister. Als je crypto wilt doen, is dat een heel slecht idee.
toegevoegd de auteur Mateusz Piotrowski, de bron

Het is bekend dat $ \ pi $ niet zo goed verdelen . Ik weet niet zeker wat dit zegt (als er iets is) over de `willekeurigheid 'van de cijfers, maar het kan het gebruik van de gulden snede of Euler-Mascheroni-constante over $ \ pi $ suggereren.

6
toegevoegd
mmm Ik vraag me af of er een verband is tussen gemak 'van spigot-algoritme en goedheid van equidistributie?
toegevoegd de auteur DavidEBest, de bron
... of $ \ ln 2: $ er is een eenvoudig spigot-algoritme voor
toegevoegd de auteur Edward Nunn, de bron
Zijn er rigoureuze kwantitatieve resultaten die zeggen dat $ \ pi $ equidistributes "slowly" is? of alleen cijfers?
toegevoegd de auteur John Pardon, de bron

Houd er rekening mee dat de Tu- en Fischbach-analyse werd aangevochten - ik weet niet of deze zorgen geldig zijn. Zie hieronder

Weerlegging van claims zoals "Pi is minder willekeurig dan we dachten". George Marsaglia Professor Emeritus Florida State University

http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf

4
toegevoegd
  1. Given all digits of a sequence S till a certain length say n ie di ( i = 1 to n) ; if the probability of any next block of digits B in next m digits ( m -> infinity ) can be ascertained as < 1/(b^w) where b is the base and w is the string length of the block , through an algorithm which is guaranteed to halt then S is NOT a random sequence.

  2. Just being a normal number is not "sufficient" say the sequence 1234..101102103..10001001 is a normal sequence yet not random.

  3. Based on above since using the spigot formula for Pi I can predict its digits, it is not random.

  4. Direction of analysis is also important. Suppose there is a civilization where constant Pi has not been discovered yet ( let alone its formula), here a only a reverse analysis would be possible and the probability of one chancing upon the spigot formula while analysing the digits of Pi cannot be ruled out though its remote. Other wise the equidistribution of digits would lead such a civilisation to take Pi sequence as random

4
toegevoegd

Het voor de hand liggende probleem hierbij is dat een goede pseudowillekeurige nummergenerator elke keer dat je hem uitvoert een andere reeks genereert, terwijl de cijfers van pi nooit zijn waargenomen.

3
toegevoegd
Nog ...
toegevoegd de auteur Herms, de bron
Dus wanneer u uw simulatie de volgende keer uitvoert, hoeft u alleen maar verder te gaan waar u was gebleven.
toegevoegd de auteur Kate Gregory, de bron
Zonder een willekeurige seeding is het onmogelijk om de vraag te beantwoorden of de cijfers van $ \ pi $ willekeurig lijken. Voor een constante seed lijken de cijfers van $ \ pi $ constant .
toegevoegd de auteur Jonathan Ross, de bron

Cryptografische PRNG's zijn de gouden standaard, want als je een praktische manier hebt om de geringste niet-willekeurigheid in de uitvoer te detecteren, wordt dit beschouwd als een breuk met de generator en een significant onderzoeksresultaat (in cryptanalyse) als de PRNG als goed werd beschouwd ( stel dat het op een of andere verstandige manier is gebaseerd op AES, de geavanceerde versleutelingsstandaard). Het is eenvoudig om ze deterministisch te maken: neem voor elke sleutel K de codering E (0), E (1), E (2), ... waarbij E de coderingsfunctie is.

Recente x86-computers hebben een hardware-instructie voor AES-codering, dus het is erg snel. Het zou me niet verbazen als AES met behulp van de hardware-instructies sneller is dan Mersenne Twister geïmplementeerd in software.

De eerste editie van "Numerical Recipes" had enige discussie over het gebruik van DES (voorganger van AES) als een RNG, hoewel ze het uit latere edities haalden.

3
toegevoegd

Waarom construeer je geen willekeurige getallen met niet-opeenvolgende cijfers van pi? Bijvoorbeeld cijfers die 10 cijfers uit elkaar liggen, op voortschrijdende basis.

En je kunt een enorm woordenboek van de cijfers van pi kopen of krijgen dat zou moeten volstaan, samen met een slimme codering van hoe je je cijfers pakt.

3
toegevoegd
Hoe zouden uw suggesties de willekeurigheidseigenschappen of bruikbaarheid van de cijferreeks verbeteren?
toegevoegd de auteur ricree, de bron

Feitelijk is niet aangetoond dat pi een normaal getal is, en dat is zeker de minimumvoorwaarde voor gebruik als "willekeurige getallen".

2
toegevoegd
Dirichlet zegt alleen dat de cijfers 1, 3, 7 en 9 oneindig vaak voorkomen. Om normaliteit te krijgen zou je moeten nadenken over prime gaps. Normaliteit of abnormaliteit volgt waarschijnlijk uit de veronderstelling van Hardy-Littlewood k-tuple ( mathworld.wolfram.com/k -TupleConjecture.html ).
toegevoegd de auteur Robert Höglund, de bron
IS ELK specifiek aantal bewezen normaal?
toegevoegd de auteur jt., de bron
Als u probeert een minder voorspelbaar normaal nummer te construeren, zijn getallen die alleen een subset van de cijfers gebruiken nuttig? Stelt de stelling van Dirichlet dat het getal waarvan de uitzetting bestaat uit de laatste cijfers van opeenvolgende priemgetallen> 5 een getal geeft met een normaal voorkomen van de cijfers 1,3,7,9? Dit is een variatie op de opmerking van Davidac.
toegevoegd de auteur Zackkenyon, de bron
@ Gerry: ik stelde voor dat Paul Siegel Wikipedia raadpleegt voor het antwoord op zijn vraag of een specifiek nummer is bewezen normaal te zijn. Het was Gerald Edgar, niet ik, die suggereerde dat normaliteit een noodzakelijke (niet voldoende) voorwaarde is voor een 'willekeurige volgorde'. Zie voor mijn antwoord op de vraag van Jim mijn antwoord op de vraag van Jim.
toegevoegd de auteur Joel Brown, de bron
@Paul: Ja. Zie Wikipedia.
toegevoegd de auteur Joel Brown, de bron
@Timothy, je suggereert niet om .123456789101112131415 ... als een bron van willekeurige cijfers te gebruiken, toch?
toegevoegd de auteur andrew, de bron