Au hasard est à peine au hasard du tout?

Question

Je l'ai fait 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 plus et le meilleur résultat que je suis arrivé était de 121 itérations avant un répéteur. Est-ce le meilleur type de résultat que vous pouvez obtenir de la bibliothèque standard?

Answer 1

Le paradoxe d'anniversaire, ou pourquoi PRNGs produisent plus souvent des doublons que vous pourriez penser.

Il y a deux questions en jeu dans le problème de l'OP. L'un est d'anniversaire comme mentionné ci-dessus et la seconde est la nature de ce que vous générez, qui ne garantit pas en soi qu'un nombre donné ne sera pas répété.

L'anniversaire Paradox applique lorsque la valeur donnée peut se produire plus d'une fois au cours de la période du générateur - et donc des doublons peut se produire dans un échantillon de valeurs. L'effet de l'anniversaire paradoxe est que la probabilité réelle d'obtenir ces copies est tout à fait significative et la durée moyenne entre eux est plus petite que l'on pourrait par ailleurs avoir pensé. Cette dissonance entre les probabilités perçues et réelles rend l'anniversaire Paradox un bon exemple d'un , où une estimation intuitive naïve est susceptible d'être sauvagement mal.

Une amorce rapide sur les générateurs pseudo nombres aléatoires (PRNGs)

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 conversion à un nombre beaucoup plus petit, donc l'espace de valeurs possibles est réduit. Bien que certains générateurs de nombres pseudo-aléatoires ne répètent pas les valeurs au cours de leur période cette transformation modifie le domaine un beaucoup plus petit. Le petit domaine annule la condition « sans répétition » de sorte que vous pouvez vous attendre à une forte probabilité de répétitions.

Certains algorithmes, tels que les linéaire PRNG (de A'=AX|M) faire unicité de garantie pour toute la période. Dans un LCG la valeur générée contient tout l'état de l'accumulateur et aucun état supplémentaire est maintenu. Le générateur est déterministe et ne peut pas répéter un certain nombre dans la période - toute valeur de l'accumulateur donné peut impliquer seulement une possible valeur successive. Par conséquent, chaque valeur ne peut se produire une fois dans la période du générateur. Cependant, la période d'un tel PRNG est relativement faible - environ 2 ^ 30 pour les implémentations typiques de l'algorithme LCG -. Et ne peut peut-être plus grand que le nombre de valeurs distinctes

Tous les algorithmes PRNG partagent cette caractéristique; certains peuvent répéter une valeur donnée dans le délai. Dans le problème de l'OP, Mersenne Twister algorithme (utilisé dans Python Module aléatoire ) a une très longue période - bien supérieure à 2 ^ 32. Contrairement à un Linear Congruential PRNG, le résultat est purement une fonction de la valeur de sortie précédente que l'accumulateur contient état supplémentaire. Avec la sortie de nombre entier de 32 bits et une période de ~ 2 ^ 19937, il ne peut peut-être fournir une une telle garantie.

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

• Bon propriétés statistiques signifient que les chiffres générés par l'algorithme sont répartis uniformément sans nombre ayant une probabilité significativement plus élevée d'apparaître que d'autres. propriétés statistiques pauvres pourraient produire skew indésirables dans les résultats.

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

• Une longue période signifie que vous pouvez générer beaucoup de chiffres avant que la séquence s'enroule autour du début. Si un modèle a besoin d'un grand nombre d'itérations ou doit être exécuté à partir de plusieurs graines puis les 2 ^ 30 ou si un nombre discret disponibles à partir d'une mise en œuvre de LCG typique peut ne pas être suffisant. L'algorithme de MT19337 a une très longue période - 2 ^ 19337-1, soit 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 PRNG MT19337 ne peut pas représenter éventuellement suffisamment de valeurs discrètes pour éviter de répéter pendant une telle période. Dans ce cas, les valeurs en double sont susceptibles de se produire et inévitable avec un échantillon suffisamment grand.

Date de naissance Paradox en un mot

Ce problème est à l'origine défini comme la probabilité de deux personnes dans la salle partageant le même anniversaire. Le point clé est que deux personnes dans la salle pourrait partager un anniversaire. Les gens ont tendance à mal interpréter le problème naïvement la probabilité d'une personne dans la salle de partager un anniversaire avec une personne en particulier, qui est la source de l'élément biais cognitif qui provoque souvent des gens à sous-estimer la probabilité. Ceci est l'hypothèse erronée - il n'y a pas d'obligation pour le match d'être à un individu spécifique et deux individus pourrait correspondre.

La probabilité d'un match qui se produit entre deux individus est beaucoup plus élevé que la probabilité d'un match à une personne en particulier que le match ne doit pas être à une date précise. Au contraire, il suffit de trouver deux personnes qui partagent le même anniversaire. A partir de ce graphique (qui se trouve sur la page Wikipedia sur le sujet), nous pouvons voir que nous avons seulement besoin de 23 personnes dans la salle pour qu'il y ait une chance de 50% de trouver deux qui correspondent à cette façon.

De la entrée de Wikipedia sur le sujet nous pouvons obtenir un  paires (voir Comprendre le problème ) qui pourraient correspondre (le premier pourrait correspondre à la deuxième, troisième, etc., la seconde pourrait correspondre à la troisième, quatrième, etc., etc.), de sorte que le nombre de combinaisons qui pourraient match est plutôt plus que 100

Calcul de la probabilité nous obtenons une expression de . L'extrait de code suivant fait python-dessous d'une évaluation naïve de la probabilité d'une paire correspondante se produise.

# === 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 raisonnable à la recherche de p = 0,669 pour un match se produisant à moins de 100 nombres échantillonnés à partir d'une population de 4500 valeurs possibles. (Peut-être que quelqu'un pourrait vérifier et publier un commentaire si c'est faux). De cela, nous pouvons voir que les longueurs de pistes entre les numéros correspondants observés par l'OP semblent être tout à fait raisonnable.

Note: en utilisant pour obtenir une brassage 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 garantie de nombres aléatoires. La technique de l'affiche fait référence à prend un tableau de nombres (que vous fournissez, afin que vous puissiez les rendre uniques) et les mélange dans un ordre aléatoire. Tirant les numéros dans l'ordre du tableau brassé vous donnera une séquence de nombres pseudo-aléatoires qui sont garantis de ne pas répéter.

Note: sécurisé pour les PRNGs

L'algorithme de MT n'est pas cryptographiquement sécurisé car il est relativement facile d'en déduire l'état interne du générateur en observant une séquence de nombres. D'autres algorithmes tels que Blum Blum Shub sont utilisés pour des applications de chiffrement, mais peuvent ne pas convenir à la simulation ou générale applications de nombres aléatoires. (Peut-être nécessitant des calculs BigNum) peuvent être coûteux Cryptographically PRNGs sécurisés ou peuvent ne pas avoir de bonnes propriétés géométriques. Dans le cas de ce type d'algorithme, l'exigence principale est qu'il doit être mathématiquement impossible d'en 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 rafraîchir une théorie des probabilités et statistiques. Commencez par lire sur le d'anniversaire

Par ailleurs, le module random en Python utilise le Mersenne Twister PRNG, qui est considéré comme très bon, a une période énorme et a été testé. Alors rassurez-vous que vous êtes dans de bonnes mains.

Answer 3

Si vous ne voulez pas un repetative, générer tableau séquentiel et utilisez aléatoire. lecture aléatoire

Answer 4

En réponse à la réponse de Nimbuz:

http://xkcd.com/221/

Answer 5

True aléatoire inclut certainement la répétition des valeurs avant l'ensemble des valeurs possibles est épuisé. Il ne serait pas au hasard autrement, comme vous seriez en mesure de prédire combien de temps une valeur ne se reproduirait pas.

Si jamais vous rouliez dés, vous avez sûrement 3 Sixes en ligne assez souvent ...

Answer 6

mise en œuvre aléatoire de Python est en fait tout à fait l'état de l'art:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

Answer 7

Ce n'est pas un répéteur. Un répéteur est lorsque vous répétez la même séquence . Pas seulement un numéro.

Answer 8

Vous générer des nombres aléatoires 4500 d'une 500 <= x <= 5000 gamme. Vous vérifiez ensuite de voir pour chaque numéro si elle a été produite avant. d'anniversaire rel="nofollow nous indique quelle est la probabilité pour deux de ces chiffres pour correspondre donné n essaie d'un d de gamme.

Vous pouvez également inverser la formule pour calculer le nombre de chiffres que vous devez générer jusqu'à ce que la chance de générer un duplicata est plus 50%. Dans ce cas, vous avez une chance de >50% de trouver un numéro en double après itérations 79.

Answer 9

Vous avez défini un espace aléatoire de 4501 valeurs (500-5000), et vous itérer 4500 fois. Vous êtes essentiellement assuré d'obtenir une collision dans le test que vous avez écrit.

Pour penser une autre façon:

• Lorsque le tableau de résultats est vide P (dupe) = 0
• une valeur en Array P (dupe) = 1/4500
• 2 valeurs dans la matrice P (dupe) = 2/4500
• etc.

Donc au moment où vous arrivez à 45/4500, cet insert a une chance de 1% d'être un double, et cette probabilité ne cesse d'augmenter à chaque insertion ultérieure.

Pour créer un test qui teste vraiment les capacités de la fonction aléatoire, augmenter l'univers des valeurs aléatoires possibles (par exemple: 500-500000) Vous pouvez, ou ne peut pas obtenir une dupe. Mais vous obtiendrez des itérations beaucoup plus en moyenne.

Answer 10

Pour quelqu'un d'autre à ce problème, j'utilisé uuid.uuid4 () et il fonctionne comme un charme.

Answer 11

Il y a le paradoxe d'anniversaire. En tenant compte de vous rendre compte que ce que vous dites est que trouver « 764, 3875, 4290, 4378, 764 » ou quelque chose comme ça n'est pas très aléatoire car un nombre dans cette séquence se répète. La vraie façon de le faire est de comparer les séquences les unes aux autres. J'ai écrit un script python pour le faire.

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)