Le hasard n'est pas du tout aléatoire ?

Question

J'ai fait ça pour tester le caractère aléatoire de Randint :

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

J'ai essayé environ 10 fois de plus et le meilleur résultat que j'ai obtenu était 121 itérations avant un répétiteur. Est-ce le meilleur résultat que l'on puisse obtenir avec la bibliothèque standard ?

Answer 1

Le paradoxe de l'anniversaire, ou pourquoi les PRNG produisent des doublons plus souvent qu'on ne le pense.

Il y a plusieurs problèmes en jeu dans le problème de l'OP. Le premier est le paradoxe de l'anniversaire comme indiqué plus haut, et la seconde est la nature de ce que vous générez, qui ne garantit pas en soi qu'un nombre donné ne se répétera pas.

Le paradoxe de l'anniversaire s'applique lorsqu'une valeur donnée peut se produire plus d'une fois au cours de la période du générateur - et donc que des doublons peuvent se produire dans un échantillon de valeurs. L'effet du paradoxe de l'anniversaire est que la probabilité réelle d'obtenir de tels doublons est assez importante et que la période moyenne entre eux est plus petite que ce que l'on aurait pu penser. Cette dissonance entre les probabilités perçues et les probabilités réelles fait du paradoxe de l'anniversaire un bon exemple de biais cognitif où une estimation naïve et intuitive est susceptible d'être très erronée.

Une brève introduction aux générateurs de nombres pseudo-aléatoires (PRNG)

La première partie de votre problème est que vous prenez la valeur exposée d'un générateur de nombres aléatoires et la convertissez en un nombre beaucoup plus petit, de sorte que l'espace des valeurs possibles est réduit. Bien que certains générateurs de nombres pseudo-aléatoires ne répètent pas de valeurs pendant leur période, cette transformation change le domaine en un domaine beaucoup plus petit. Le domaine plus petit invalide la condition de "non-répétition" et vous pouvez donc vous attendre à une probabilité significative de répétitions.

Certains algorithmes, tels que le PRNG linéaire congruent ( A'=AX|M ) faire garantissent l'unicité pour toute la période. Dans un LCG, la valeur générée contient l'état complet de l'accumulateur et aucun état supplémentaire n'est conservé. Le générateur est déterministe et ne peut pas répéter un nombre au cours de la période - toute valeur d'accumulateur donnée ne peut impliquer qu'une seule valeur successive possible. Par conséquent, chaque valeur ne peut apparaître qu'une seule fois au cours de la période du générateur. Cependant, la période d'un tel PRNG est relativement petite - environ 2^30 pour les implémentations typiques de l'algorithme LCG - et ne peut pas être plus grande que le nombre de valeurs distinctes.

Tous les algorithmes PRNG ne partagent pas cette caractéristique ; certains peuvent répéter une valeur donnée à l'intérieur de la période. Dans le problème de l'OP, le Twister de Mersenne (utilisé dans l'algorithme de Python au hasard ) a une période très longue - beaucoup plus grande que 2^32. Contrairement à un PRNG linéaire congruentiel, le résultat n'est pas purement fonction de la valeur de sortie précédente car l'accumulateur contient un état supplémentaire. Avec une sortie entière de 32 bits et une période de ~2^19937, il est impossible de fournir une telle garantie.

Le tordeur de Mersenne est un algorithme populaire pour les PRNG car il possède de bonnes propriétés statistiques et géométriques et une période très longue - des caractéristiques souhaitables pour un PRNG utilisé sur des modèles de simulation.

• Bon propriétés statistiques signifie que les nombres générés par l'algorithme sont distribués de manière homogène, aucun nombre n'ayant une probabilité d'apparaître significativement plus élevée que les autres. De mauvaises propriétés statistiques pourraient produire une distorsion indésirable des résultats.

• Bon propriétés géométriques signifient que les ensembles de N nombres ne se trouvent pas sur un hyperplan dans un espace à N dimensions. De mauvaises propriétés géométriques peuvent générer des corrélations parasites dans un modèle de simulation et fausser les résultats.

• Une longue période signifie que vous pouvez générer un grand nombre de numéros avant que la séquence ne revienne au début. Si un modèle nécessite un grand nombre d'itérations ou doit être exécuté à partir de plusieurs graines, les quelque 2^30 nombres discrets disponibles dans une implémentation LCG typique peuvent ne pas être suffisants. L'algorithme MT19337 a une période très longue - 2^19337-1, ou environ 10^5821. Par comparaison, le nombre total d'atomes dans l'univers est estimé à environ 10^80.

Le nombre entier de 32 bits produit par un MT19337 PRNG ne peut pas représenter suffisamment de valeurs discrètes pour éviter les répétitions pendant une période aussi longue. Dans ce cas, les valeurs dupliquées sont susceptibles de se produire et sont inévitables avec un échantillon suffisamment grand.

Le paradoxe de l'anniversaire en bref

Ce problème est défini à l'origine comme la probabilité que deux personnes dans la pièce partagent le même anniversaire. Le point clé est que deux quelconques les personnes dans la pièce pourraient partager un anniversaire. Les gens ont tendance à interpréter naïvement le problème comme étant la probabilité que quelqu'un dans la pièce partage un anniversaire avec un individu spécifique, ce qui est la source de l'idée que le problème de l'anniversaire n'est pas une question de probabilité. biais cognitif qui amène souvent les gens à sous-estimer la probabilité. Il s'agit d'une hypothèse erronée - il n'est pas nécessaire que la concordance se fasse avec un individu spécifique et deux individus quelconques peuvent correspondre.

La probabilité d'une correspondance entre deux personnes est beaucoup plus élevée que la probabilité d'une correspondance avec une personne spécifique, car il n'est pas nécessaire que la correspondance porte sur une date précise. En effet, il suffit de trouver deux personnes qui partagent la même date d'anniversaire. D'après ce graphique (que l'on peut trouver sur la page Wikipédia consacrée au sujet), on peut voir qu'il suffit de 23 personnes dans la pièce pour qu'il y ait 50 % de chances de trouver deux personnes qui correspondent de cette manière.

De la Entrée Wikipedia sur le sujet nous pouvons obtenir un Bon résumé. Dans le problème de l'OP, nous avons 4 500 "anniversaires" possibles, au lieu de 365. Pour un nombre donné de valeurs aléatoires générées (équivalant à des "personnes"), nous voulons connaître la probabilité de tout deux valeurs identiques apparaissant dans la séquence.

Calculer l'effet probable du paradoxe de l'anniversaire sur le problème de l'OP.

Pour une séquence de 100 nombres, on a paires (voir Comprendre le problème ) qui pourraient potentiellement correspondre (c'est-à-dire que le premier pourrait correspondre avec le deuxième, le troisième etc., le deuxième pourrait correspondre avec le troisième, le quatrième etc. et ainsi de suite), donc le nombre de combinaisons qui pourraient potentiellement correspondre est bien plus que 100.

De Calcul de la probabilité nous obtenons une expression de . Le bout de code Python suivant effectue une évaluation naïve de la probabilité d'apparition d'une paire correspondante.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

Cela produit un résultat d'apparence raisonnable de p=0.669 pour une correspondance se produisant dans un intervalle de 100 nombres échantillonnés à partir d'une population de 4500 valeurs possibles. (Peut-être que quelqu'un pourrait vérifier cela et poster un commentaire si c'est faux). A partir de cela, nous pouvons voir que les longueurs des séries entre les numéros correspondants observées par le PO semblent être tout à fait raisonnables.

Note de bas de page : utilisation du brassage pour obtenir une séquence unique de nombres pseudo-aléatoires.

Voir cette réponse ci-dessous de S. Mark pour un moyen d'obtenir un ensemble unique et garanti de nombres aléatoires. La technique à laquelle l'affiche fait référence prend un tableau de nombres (que vous fournissez, afin de les rendre uniques) et les mélange dans un ordre aléatoire. En tirant les nombres en séquence à partir du tableau mélangé, vous obtenez une séquence de nombres pseudo-aléatoires dont la non-répétition est garantie.

Note de bas de page : PRNGs cryptographiquement sécurisés

L'algorithme MT n'est pas sécurité cryptographique car il est relativement facile de déduire l'état interne du générateur en observant une séquence de chiffres. D'autres algorithmes, tels que Blum Blum Shub sont utilisés pour les applications cryptographiques mais peuvent être inadaptés à la simulation ou aux applications générales de nombres aléatoires. Les PRNG cryptographiquement sûrs peuvent être coûteux (nécessitant éventuellement des calculs de bignum) ou ne pas avoir de bonnes propriétés géométriques. Dans le cas de ce type d'algorithme, la principale exigence est qu'il soit infaisable sur le plan informatique de déduire l'état interne du générateur en observant une séquence de valeurs.

Answer 2

Avant de blâmer Python, vous devriez vraiment revoir la théorie des probabilités et des statistiques. Commencez par lire le paradoxe de l'anniversaire

D'ailleurs, le random en Python utilise le module Torsion de Mersenne Le PRNG, qui est considéré comme très bon, a une période énorme et a été testé de manière approfondie. Soyez donc assuré que vous êtes entre de bonnes mains.

Answer 3

Comme une réponse à la réponse de Nimbuz :

http://xkcd.com/221/

Answer 4

Si vous ne voulez pas un tableau répétitif, générez un tableau séquentiel et utilisez random.shuffle

Answer 5