Pouvez-vous utiliser Pi comme générateur de nombres aléatoires bruts?

30

J'ai récemment vu cette question à math.SE. Cela m'a fait réfléchir. Pi pourrait-il être utilisé comme générateur de nombres aléatoires bruts? Je veux dire que les résultats sont bien connus (depuis combien de temps pi est-il calculé?), Mais Pi semble être assez aléatoire lorsqu'il est pris 1 chiffre à la fois.

Est-ce que cela a un sens?

Earlz
la source
Où ces nombres aléatoires vont-ils être utilisés?
NullUserException
2
Théoriquement, cela pourrait l'être, mais ce serait probablement moins optimal que les méthodes actuelles. Juste des instincts à ce sujet, mais il semble que le pool aléatoire soit plus grand de cette manière avec moins de frais généraux.
Rig
@NullUserException Pas sûr ... Je me demandais simplement s'ils pouvaient être utilisés DU TOUT. Je suppose que ce ne serait certainement pas pour la cryptographie ''
Earlz
3
@FrustratedWithFormsDesigner - sa partie du paquet ent. Il utilise les nombres aléatoires pour calculer l'aire d'un cercle inscrit dans un carré et à partir de cela, on peut calculer pi. En utilisant les bits de pi comme des nombres aléatoires, il y a une certaine élégance à utiliser ces données pour calculer pi.
1
@FrustratedWithFormsDesigner ent est une suite de code pour analyser le pseudo-aléatoire d'un tas d'octets. Un test en son sein est un Monte Carlo pour calculer pi et comparer le calcul aléatoire avec la valeur réelle pour voir comment il est aléatoire.

Réponses:

50

Creuser à partir de http://www.befria.nu/elias/pi/binpi.html pour obtenir la valeur binaire de pi (de sorte qu'il était plus facile de convertir en octets plutôt que d'essayer d'utiliser des chiffres décimaux), puis de l'exécuter via ent J'obtiens ce qui suit pour une analyse de la distribution aléatoire des octets:

Entropie = 7,954093 bits par octet.

Une compression optimale réduirait la taille de ce fichier de 4096 octets de 0%.

La distribution du chi carré pour 4096 échantillons est de 253,00, et dépasserait au hasard cette valeur 52,36% du temps.

La valeur arithmétique moyenne des octets de données est de 126,6736 (127,5 = aléatoire).

La valeur de Monte Carlo pour Pi est de 3.120234604 (erreur 0,68%).

Le coefficient de corrélation en série est de 0,028195 (totalement non corrélé = 0,0).

Alors oui, utiliser pi pour des données aléatoires vous donnerait des données assez aléatoires ... sachant qu'il s'agit de données aléatoires bien connues.


D'après un commentaire ci-dessus ...

Selon ce que vous faites, mais je pense que vous pouvez utiliser les décimales de la racine carrée de tout nombre premier comme générateur de nombres aléatoires. Ceux-ci devraient au moins avoir des chiffres uniformément répartis. - Paxinum

J'ai donc calculé la racine carrée de 2 en binaire pour supprimer le même ensemble de problèmes. En utilisant l'itération de Wolfram, j'ai écrit un simple script perl

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

L'exécution de cela pour les 10 premiers correspondait à A095804, donc j'étais confiant d'avoir la séquence. La valeur v n comme lorsqu'elle est écrite en binaire avec le point binaire placé après le premier chiffre donne une approximation de la racine carrée de 2.

L'utilisation de ent contre ces données binaires produit:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

la source
Exactement le type de réponse que je cherchais. Je n'ai aucune idée de comment calculer tout ce genre de choses
Earlz
Même si la distribution des nombres est assez aléatoire, n'avez-vous pas à trouver un moyen de sélectionner au hasard une partie de celle-ci?
Blumer
1
@Blumer no. L'aléatoire est mesuré sur une séquence de nombres. On dit que la séquence de chiffres pi est aléatoire. Voir en.wikipedia.org/wiki/Statistical_randomness
Simon Bergot
11
Absolument raison. Et parce que ce sont des données aléatoires bien connues, n'osez jamais les utiliser à des fins cryptographiques.
Falcon
3
+1 pour les "données aléatoires bien connues". Si vous avez besoin de données aléatoires que quelqu'un ne peut pas deviner, pi n'est pas pour vous, si vous avez juste besoin d'un tas de nombres aléatoires pour une raison quelconque, cela fonctionne très bien.
jmoreno
5

Eh bien, parmi d'autres propriétés d'un générateur de nombres aléatoires, vous voulez probablement que ce soit un nombre normal . Et plusieurs réponses à la question math.SE qui ont inspiré votre question soulignent qu'actuellement on pense que pi est normal, mais cela n'a pas été prouvé.

psr
la source
2

Un tel générateur serait un pseudo-générateur de nombres, c'est-à-dire que, étant donné la même graine, le résultat serait toujours le même. Cela étant dit, dans la plupart des frameworks, lorsque vous utilisez le générateur de nombres aléatoires standard, il y a le même problème d'être pseudo-aléatoire.

La distribution des chiffres semble être assez similaire aux générateurs de nombres aléatoires standard¹, de sorte que les chiffres de π peuvent être utilisés pour des scénarios de génération de nombres aléatoires ordinaires.

Le problème est que l'algorithme sera probablement très lent par rapport aux générateurs de nombres aléatoires ordinaires, il n'est donc pas très utile dans la pratique.


¹ Je crois que c'est vrai, mais je n'ai aucune preuve. Il serait intéressant (et non compliqué) de faire une comparaison basée sur une grande quantité de nombres.

Arseni Mourzenko
la source
5
@NullUserException: Non, certains générateurs de nombres aléatoires utilisent une source d'entropie. Cela peut se faire soit via du matériel spécialisé (l'approche adoptée par random.org ) soit en utilisant des sources d'entropie existantes (fluctuations mesurables au sein des capteurs matériels existants, certains types d'interactions utilisateur, micro-variations dans certains types de tests de performance, etc. ).
Brian
1
@NullUserException: il existe des PRNG sécurisés cryptographiquement, qui sont toujours pseudo-aléatoires. Ensuite, il y a de vrais RNG qui sont basés sur les entrées du monde réel: désintégration radioactive, bruit, etc.
Arseni Mourzenko
2
@MainMa Mais même dans ce cas, le caractère aléatoire de la désintégration radioactive, du bruit atmosphérique, dérivé des commentaires des utilisateurs, etc. est discutable. Ce n'est pas parce que nous ne reconnaissons pas un modèle qu'il n'existe pas.
NullUserException
1
@NullUserException: l'an dernier, Colbeck / Renner a publié un article qui prétend prouver: "Aucune extension de la théorie quantique ne peut avoir amélioré le pouvoir prédictif." En supposant que cela se vérifie, il peut y avoir une source d'entropie qui est vraiment imprévisible, plutôt que simplement impossible à prédire.
Brian
1
@MainMa - vous effectueriez toujours des tests mathématiques pour le caractère aléatoire. Même si la physique sous-jacente est aléatoire (au meilleur de nos connaissances), cela ne signifie pas que la mesure l'est. Les détecteurs de tous types ont beaucoup de comportements «intéressants» dans le monde réel
Martin Beckett
2

Le caractère aléatoire des chiffres de pi (ou d'ailleurs toute autre séquence) peut être testé par des soi-disant «tests de batterie». Un test de batterie populaire est le test de batterie Diehard de George Marsaglia . Il existe également la publication spéciale NIST 800-22 qui décrit un certain nombre de ces tests et les résultats de l'application de ces tests à un certain nombre de constantes physiques, y compris - lo et voici - pi pour plus d'un million de bits. Le résultat de pi est donné à l'annexe B du rapport et ressemble à ceci:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

Pi est-il un bon générateur de séquences aléatoires? Regardez les résultats ci-dessus (ou recherchez les significations de la variable de la colonne de gauche, si vous ne savez pas ce qu'ils signifient), et vérifiez si cela répond à vos besoins.

sm535
la source
1
Le read me for Diehard dit qu'il a besoin d'environ 10-12 mégaoctets de données binaires (le mieux que je puisse trouver est de 32 kilo-octets). Si vous l'exécutiez sur les données ascii, le test serait assez éloigné de ce que l'application attend.
Ma réponse était pour la question OP et la question originale sur Math.SE - aucune des deux ne mentionnant quoi que ce soit à propos des données ascii par rapport aux données binaires ou de la longueur de l'échantillon. Sans un ensemble d'échantillons suffisamment grand, comment déterminer le caractère aléatoire statistique d'une séquence?
sm535