Comprendre le «hasard»

829

Je n'arrive pas à comprendre ce qui est plus aléatoire?

rand()

OU :

rand() * rand()

Je trouve que c'est un vrai casse-tête, pourriez-vous m'aider?


ÉDITER:

Intuitivement, je sais que la réponse mathématique sera qu'ils sont également aléatoires, mais je ne peux m'empêcher de penser que si vous "exécutez l'algorithme des nombres aléatoires" deux fois lorsque vous multipliez les deux ensemble, vous créerez quelque chose de plus aléatoire que de le faire une fois.

Trufa
la source
162
Qu'entendez-vous par «plus aléatoire»?
dan04
55
Comme d'autres l'ont indiqué, ces deux quantités n'ont pas la même distribution. Voir mathworld.wolfram.com/UniformProductDistribution.html pour la distribution que vous obtenez réellement. Comparez cela à un nombre aléatoire uniforme unique, où toutes les valeurs de l'intervalle sont également probables, de sorte que la fonction de densité de probabilité est une ligne droite horizontale.
bnaul
44
Je recommande fortement de lire Random Stupidity sur le Daily WTF . Lisez en particulier ce commentaire , où ils analysent la sortie de ce nouveau nombre aléatoire. Le message à retenir est que les opérations arbitraires sur des nombres aléatoires n'entraînent pas nécessairement une sortie aléatoire .
detly
51
Aussi: Intuitivement, je sais que la réponse mathématique sera qu'ils sont également aléatoires - si vous pouviez faire des calculs uniquement par intuition, nous n'aurions pas besoin de tous ces symboles sanglants: P
détly
92
Ne
ramenez

Réponses:

1481

Juste une clarification

Bien que les réponses précédentes soient exactes chaque fois que vous essayez de repérer le caractère aléatoire d'une variable pseudo-aléatoire ou sa multiplication, vous devez savoir que si Random () est généralement uniformément distribué, Random () * Random () ne l'est pas.

Exemple

Il s'agit d'un échantillon de distribution aléatoire uniforme simulé par une variable pseudo-aléatoire:

Histogramme aléatoire ()

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

Bien que ce soit la distribution que vous obtenez après avoir multiplié deux variables aléatoires:

Histogramme de aléatoire () * aléatoire ()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Les deux sont donc «aléatoires», mais leur distribution est très différente.

Un autre exemple

Alors que 2 * Random () est uniformément distribué:

Histogramme de 2 * aléatoire ()

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random () + Random () ne l'est pas!

Histogramme de Random () + Random ()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Le théorème de la limite centrale

Le théorème de la limite centrale indique que la somme de Random () tend vers une distribution normale mesure que les termes augmentent.

Avec seulement quatre termes, vous obtenez:

Histogramme aléatoire () + aléatoire () + aléatoire () + aléatoire ()

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

Et ici, vous pouvez voir la route d'une distribution uniforme à une distribution normale en additionnant 1, 2, 4, 6, 10 et 20 variables aléatoires uniformément réparties:

Histogramme de différents nombres de variables aléatoires ajouté

Éditer

Quelques crédits

Merci à Thomas Ahle d' avoir souligné dans les commentaires que les distributions de probabilité montrées dans les deux dernières images sont connues sous le nom de distribution Irwin-Hall

Merci à Heike pour sa merveilleuse fonction déchirée []

Dr. belisarius
la source
41
+1. Étant donné que le PO voulait probablement une distribution uniforme, cela devrait être la réponse acceptée. Et si vous le faisiez rand()+rand(), vous vous retrouveriez avec une distribution de type "2d6" avec un centre de graisse.
Thilo
8
C'est très intéressant, mais ça me tue à l'intérieur à quel point c'est anti-intuitif. Je donnerai un aperçu plus approfondi après avoir lu un peu plus sur la distribution. Merci beaucoup!
Trufa
46
@Trufa: Peut-être que cela aidera une partie de l'intuition, au moins pour les sommes. Imaginez prendre la "moyenne" d'un dé lancé. Imaginez maintenant prendre la moyenne de deux dés. Maintenant cent. Qu'arrive-t-il à la chance d'obtenir un ou six pour la moyenne lorsque vous ajoutez plus de dés?
johncip
3
@matt b Les graphiques sont à une ligne dans Mathematica. Le code est le texte en gras qui précède chaque graphique. Mathematica est un langage génial pour faire des tracés!
Dr belisarius
4
@thenonhacker: oui, les histogrammes démontrent un biais, mais ils ne démontrent pas le caractère non aléatoire. Les nombres aléatoires biaisés ne sont pas moins aléatoires. Quant à la bonne réponse à la question initiale de l'utilisateur, "n'essayez pas d'être intelligent, vous ne ferez qu'aggraver les choses", et cette réponse fait bien comprendre ce point.
Kennet Belenky
151

Je suppose que les deux méthodes sont aussi aléatoires, même si ma gutfeel dirait que rand() * rand() c'est moins aléatoire car cela donnerait plus de zéros. Dès que l'on rand()est 0, le total devient0

Janco
la source
18
Ma réponse à toutes les réponses en utilisant cette bande est la suivante: j'aime l'humour, mais ça doit être CW!
Andreas Rejbrand
4
@Andomar: Non, ce n'est pas le cas. Pas du tout. Savez-vous ce qu'est CW?
Andreas Rejbrand
17
@Andreas Rejbrand: CW est une arme qui tue des questions intéressantes en refusant la réputation à ceux qui y répondent. On dirait que c'est devenu nerfed meta.stackexchange.com/questions/392/… (c'est peut-être pourquoi cette question intéressante apparaît!)
Andomar
11
@Andomar - Oui, CW tue des questions intéressantes, mais (d'après la FAQ ) "La réputation est une mesure approximative de la confiance de la communauté." Si vous incluez une image amusante et protégée par des droits d'auteur dans votre réponse, cela me fera penser que votre réponse est cool, et je penserai probablement que vous êtes cool aussi, mais cela ne vous rend pas plus digne de confiance - donc, idéalement, aucun représentant devrait être attribué. Que cela signifie CW, ou que cela signifie que l'on ne devrait pas voter la réponse est un autre problème.
Richard JP Le Guen
13
le troll "générateur aléatoire" dans le dessin animé pourrait être juste un savant récitant π, et atteignant juste le point de Feynman . btw, les π chiffres sont-ils aléatoires? :)
mykhal
82

Ni l'un ni l'autre n'est «plus aléatoire».

rand()génère un ensemble prévisible de nombres basé sur une graine pseudo-aléatoire (généralement basée sur l'heure actuelle, qui change toujours). La multiplication de deux nombres consécutifs dans la séquence génère une séquence de nombres différente, mais tout aussi prévisible.

Pour savoir si cela réduira les collisions, la réponse est non. Cela augmentera en fait les collisions en raison de l'effet de la multiplication de deux nombres où0 < n < 1 . Le résultat sera une fraction plus petite, provoquant un biais dans le résultat vers l'extrémité inférieure du spectre.

Quelques explications supplémentaires. Dans ce qui suit, «imprévisible» et «aléatoire» se réfèrent à la capacité de quelqu'un à deviner quel sera le prochain numéro sur la base des numéros précédents, c'est-à-dire. un oracle.

Étant donné la graine xqui génère la liste de valeurs suivante:

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand()générera la liste ci-dessus et rand() * rand()générera:

0.18, 0.08, 0.08, 0.21, ...

Les deux méthodes produiront toujours la même liste de nombres pour la même graine, et sont donc également prévisibles par un oracle. Mais si vous regardez les résultats de la multiplication des deux appels, vous verrez qu'ils sont tous inférieurs 0.3malgré une distribution décente dans la séquence d'origine. Les nombres sont biaisés en raison de l'effet de la multiplication de deux fractions. Le nombre résultant est toujours plus petit, donc beaucoup plus susceptible d'être une collision bien qu'il soit tout aussi imprévisible.

Matthew Scharley
la source
9
+1 Notez que d'autre part rand()+rand()+rand()...devient de moins en moins "aléatoire" (si par hasard vous entendez uniformément distribué).
Thilo
4
@Thilo Non, ce n'est pas ...? Si une variable aléatoire est uniformément distribuée dans la plage (0,1), et que vous échantillonnez la variable n fois, et prenez la somme, elle sera simplement répartie uniformément dans la plage (0, n).
user359996
5
@Trufa se contente de faire confiance rand()au fait d'être aléatoire, et n'essayez pas de `` renforcer '' son caractère aléatoire. Ne placez pas la graine plusieurs fois. Toute graine individuelle est parfaitement fine, tant qu'elle est semi-aléatoire elle-même. Beaucoup d'implémentations que j'ai vues utilisent l'époque UNIX comme graine, qui change à chaque seconde et est unique à chaque fois qu'elle change.
Matthew Scharley
61
@ user359996 rand () + rand () n'est pas uniformément distribué. Ajoutez deux dés, vous avez plus de chances d'obtenir 7 que 2.
Liam
4
@thenonhacker Voir ma définition de l'aléatoire dans mon post. Le fait que les valeurs tendent vers une extrémité du spectre n'augmente pas la prévisibilité des valeurs exactes produites, ce à quoi je faisais référence lorsque j'ai utilisé le mot aléatoire. J'ai ensuite abordé la question du parti pris séparément.
Matthew Scharley
80

Une simplification excessive pour illustrer un point.

Supposez que votre fonction aléatoire ne produit que 0ou 1.

random()est l'un des (0,1), mais random()*random()est l'un des(0,0,0,1)

Vous pouvez clairement voir que les chances d'obtenir un 0dans le deuxième cas ne sont en aucun cas égales à celles d'obtenir un 1.


Quand j'ai posté cette réponse pour la première fois, je voulais la garder aussi courte que possible afin qu'une personne qui la lise puisse comprendre d'un coup d'œil la différence entre random()et random()*random(), mais je ne peux pas m'empêcher de répondre à la question originale ad litteram:

Quel est le plus aléatoire?

Etant donné que random(), random()*random(), random()+random(), (random()+1)/2ou toute autre combinaison qui ne conduit pas à un résultat fixe ont la même source d'entropie (ou le même état initial dans le cas des générateurs pseudo - aléatoires), la réponse est qu'ils sont tout aussi aléatoire (la différence est dans leur distribution). Un exemple parfait que nous pouvons regarder est le jeu de Craps. Le nombre que vous obtiendrez serait random(1,6)+random(1,6)et nous savons tous qu'obtenir 7 a les meilleures chances, mais cela ne signifie pas que le résultat du lancer de deux dés est plus ou moins aléatoire que le résultat du premier.

Alin Purcaru
la source
+1 pour condenser quelque chose de diaboliquement délicat en "également aléatoire sur différentes distributions". Très élégant.
Jens Roland
3
Donc, techniquement, (random () * 0 + 9) est également aléatoire, car il renvoie aléatoirement une valeur de l'ensemble à 1 élément: [9]. Le dessin animé de Dilbert avait raison.
Jens Roland
2
@Jens Rolan "toute autre combinaison qui ne conduit pas à un résultat fixe";). 999999 <i> probablement </i> n'est pas généré aléatoirement et la chance qu'il a été généré aléatoirement peut être calculée.
Alin Purcaru
69

Voici une réponse simple. Considérez le monopole. Vous lancez deux dés à six faces (ou 2d6 pour ceux d'entre vous qui préfèrent la notation de jeu) et prenez leur somme. Le résultat le plus courant est 7 car il y a 6 façons possibles de rouler un 7 (1,6 2,5 3,4 4,3 5,2 et 6,1). Alors qu'un 2 ne peut être lancé que sur 1,1. Il est facile de voir que le roulement 2d6 est différent du roulement 1d12, même si la plage est la même (en ignorant que vous pouvez obtenir un 1 sur un 1d12, le point reste le même). Multiplier vos résultats au lieu de les ajouter va les biaiser de la même manière, la plupart de vos résultats se situant au milieu de la plage. Si vous essayez de réduire les valeurs aberrantes, c'est une bonne méthode, mais cela n'aidera pas à faire une distribution uniforme.

(Et bizarrement, cela augmentera également les rouleaux bas. En supposant que votre caractère aléatoire commence à 0, vous verrez un pic à 0 car il transformera tout autre rouleau en 0. Considérez deux nombres aléatoires entre 0 et 1 (inclus ) et multiplier. Si l'un des résultats est un 0, le tout devient un 0, peu importe l'autre résultat. La seule façon d'en tirer un 1 est que les deux lancers soient un 1. En pratique, cela n'aurait probablement pas d'importance mais cela donne un graphique bizarre.)

valadil
la source
4
"Multiplier vos résultats au lieu de les ajouter va les biaiser de la même manière, la plupart de vos résultats se situant au milieu de la fourchette." - vérifiez cette affirmation par rapport au deuxième graphique de la réponse de belisarius.
Daniel Earwicker
52

Le xkcd obligatoire ...
retour 4;  // choisi par jet de dés équitable, garanti aléatoire.

crowne
la source
7
danmn cela finit toujours par apparaître quand le mot "random apparaît" :) Je l'attendais !!
Trufa
9
J'aime l'humour, mais ça doit être CW.
Andreas Rejbrand
2
@Andreas Rejbrand - pourquoi cette réponse "humour" devrait-elle être CW?
warren
16
S'il ne s'agit pas de CW, la réputation sera mise à l'épreuve de l'affiche de la réponse à chaque fois qu'elle sera majorée (160 rep jusqu'à présent). Maintenant, la réputation est comme les notes à l'école - ce devrait être un certificat de compétence technique (dans ce cas, la programmation). Par conséquent, on ne devrait pas pouvoir gagner en réputation en publiant quelque chose qui est facilement surévalué mais qui n'a pas besoin d'une telle compétence. De plus, le score de réputation détermine également les privilèges de l'utilisateur. Par exemple, avec un score de 10 000, l'utilisateur a accès aux outils de modération de StackOverflow.
Andreas Rejbrand
35

Il pourrait être utile de penser à cela en chiffres plus discrets. Envisagez de générer des nombres aléatoires entre 1 et 36, vous décidez donc que la manière la plus simple est de lancer deux dés équitables à 6 faces. Vous obtenez ceci:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

Nous avons donc 36 chiffres, mais ils ne sont pas tous équitablement représentés, et certains ne se produisent pas du tout. Les nombres proches de la diagonale centrale (du coin inférieur gauche au coin supérieur droit) apparaîtront avec la fréquence la plus élevée.

Les mêmes principes qui décrivent la distribution injuste entre les dés s'appliquent également aux nombres à virgule flottante compris entre 0,0 et 1,0.

Juliette
la source
3
+1 pour montrer plus concrètement, le changement de distribution lors de la multiplication des nombres aléatoires. La matrice a aidé plus que les mots ou même un graphique de distribution.
Marjan Venema
26

Certaines choses sur le "hasard" sont contre-intuitives.

En supposant une distribution plate de rand(), les éléments suivants vous permettront d'obtenir des distributions non plates:

  • biais élevé: sqrt(rand(range^2))
  • biais biaisé au milieu: (rand(range) + rand(range))/2
  • faible: biais: range - sqrt(rand(range^2))

Il existe de nombreuses autres façons de créer des courbes de biais spécifiques. J'ai fait un test rapide rand() * rand()et cela vous donne une distribution très non linéaire.

staticien
la source
24

La plupart des implémentations rand () ont une certaine période. C'est-à-dire après un nombre énorme d'appels, la séquence se répète. La séquence des sorties derand() * rand() répétitions dans la moitié du temps, elle est donc "moins aléatoire" dans ce sens.

De plus, sans construction soigneuse, effectuer une arithmétique sur des valeurs aléatoires a tendance à entraîner moins de caractère aléatoire. Une affiche ci-dessus cite " rand()+ rand()+ rand()..." (k fois, disons) qui tendra en fait à k fois la valeur moyenne de la plage de valeurs de rand()retour. (C'est une marche aléatoire avec des étapes symétriques par rapport à cette moyenne.)

Supposons pour plus de concret que votre fonction rand () retourne un nombre réel aléatoire uniformément distribué dans la plage [0,1). (Oui, cet exemple permet une précision infinie. Cela ne changera pas le résultat.) Vous n'avez pas choisi une langue particulière et différentes langues peuvent faire des choses différentes, mais l'analyse suivante est valable avec des modifications pour toute implémentation non perverse de rand ( ). Le produit rand() * rand()est également dans la gamme [0,1) mais n'est plus uniformément distribué. En fait, le produit est aussi susceptible d'être dans l'intervalle [0,1 / 4) que dans l'intervalle [1 / 4,1). Une multiplication plus importante faussera encore davantage le résultat vers zéro. Cela rend le résultat plus prévisible. En traits larges, plus prévisible == moins aléatoire.

À peu près n'importe quelle séquence d'opérations sur une entrée uniformément aléatoire sera aléatoire de manière non uniforme, conduisant à une prévisibilité accrue. Avec soin, on peut surmonter cette propriété, mais il aurait alors été plus facile de générer un nombre aléatoire uniformément réparti dans la plage que vous vouliez réellement plutôt que de perdre du temps avec l'arithmétique.

Eric Towers
la source
J'avais aussi pensé que cela passerait par la période du générateur aléatoire deux fois plus vite.
Jared Updike
3
La longueur de la séquence ne sera réduite de moitié que si elle est régulière. Si c'est étrange, vous obtenez r1 * r2, r3 * r4, ..., rn * r1, r2 * r3, r4 * r5, et la longueur totale est la même.
Jander
23

«aléatoire» vs «plus aléatoire», c'est un peu comme demander quel zéro est le plus zéro.

Dans ce cas, randc'est un PRNG, donc pas totalement aléatoire. (en fait, tout à fait prévisible si la graine est connue). Le multiplier par une autre valeur ne le rend ni plus ni moins aléatoire.

Un vrai RNG de type crypto sera en fait aléatoire. Et l'exécution de valeurs via n'importe quel type de fonction ne peut pas lui ajouter plus d'entropie, et peut très probablement supprimer l'entropie, ce qui ne la rend plus aléatoire.

abelenky
la source
3
Notez que ce n'est pas au carré car chaque appel avec retourne une valeur différente. Tout le reste est cependant exact.
Matthew Scharley
2
@thenonhacker: Selon votre propre description, la séquence "1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10 , 1,2,3,4,5,6,7,8,9,10 ... "est aléatoire. Il est réparti uniformément, tous les chiffres ayant une chance équitable. Il n'y a pas de pic ou de biais. Considérez-vous vraiment cette séquence aléatoire ??? Vous devez changer votre définition. Aléatoire ne concerne pas la sortie, aléatoire concerne le processus utilisé pour créer la sortie.
abelenky
2
@CurtainDog: La compression de texte maintient le même niveau d'entropie tout en réduisant le nombre de bits requis pour exprimer la même quantité d'entropie.
Kennet Belenky
4
@thenonhacker, @abelenky: Même les distributions sont faciles. Ce qui importe dans un générateur de nombres aléatoires, c'est le nombre de bits dans l'état du générateur de nombres aléatoires. Un générateur de nombres aléatoires à état zéro (par exemple 4, 4, 4, 4, 4, ...) est totalement prévisible. Un tampon ponctuel a autant d'état que le nombre de valeurs qu'il produit, ce qui le rend impossible à prévoir. Une convolution de deux PNRG produira un PNRG avec autant de bits d'entropie qu'ils contiennent tous les deux, moins leur covariance.
Kennet Belenky
1
@Kennet - Merci, vous m'avez énormément éclairci. @abelenky - cool, je vous comprends maintenant.
CurtainDog
20

Le concept que vous recherchez est "l'entropie", le "degré" de désordre d'une chaîne de bits. L'idée est plus facile à comprendre en termes de concept "d'entropie maximale".

Une définition approximative d'une chaîne de bits avec une entropie maximale est qu'elle ne peut pas être exprimée exactement en termes d'une chaîne de bits plus courte (c'est-à-dire en utilisant un algorithme pour étendre la plus petite chaîne à la chaîne d'origine).

La pertinence de l'entropie maximale pour le caractère aléatoire vient du fait que si vous choisissez un nombre "au hasard", vous choisirez presque certainement un nombre dont la chaîne de bits est proche d'avoir une entropie maximale, c'est-à-dire qu'il ne peut pas être compressé. C'est notre meilleure compréhension de ce qui caractérise un nombre "aléatoire".

Donc, si vous voulez faire un nombre aléatoire de deux échantillons aléatoires qui est "deux fois" aussi aléatoire, vous concaténerez les deux chaînes de bits ensemble. Pratiquement, vous ne feriez que remplir les échantillons dans les moitiés haute et basse d'un mot de double longueur.

Sur une note plus pratique, si vous vous retrouvez avec un rand merdique (), cela peut parfois aider à xor quelques échantillons ensemble --- bien que, si c'est vraiment cassé, même cette procédure n'aidera pas.

PachydermPuncher
la source
2
Je n'avais jamais pensé à des générations de nombres aléatoires via xor, mais je suppose que vous pouvez prendre le concept assez loin ( en.wikipedia.org/wiki/Mersenne_twister )! Merci d'avoir répondu.
Gabriel Mitchell
1
J'ai vraiment du mal à trouver cette réponse ... L'entropie maximale n'est-elle pas vaincue par les réponses données dans stackoverflow.com/questions/3956478/understanding-randomness/… et stackoverflow.com/questions/3956478/understanding-randomness/… . Dans ces cas, le nombre choisi ne peut pas être compressé, mais vous aurez du mal à les appeler au hasard.
CurtainDog
1
+1 Magnifique, la réponse acceptée est ma préférée. En ce qui concerne les ordinateurs, pensez toujours en bits - beaucoup moins déroutant et plus pertinent que d'essayer de penser en termes de réels. (J'ai écrit ma réponse, puis j'ai remarqué celle-ci, donc la mienne n'est rien de plus qu'une expansion de celle-ci - peut-être avec une entropie ajoutée).
Daniel Earwicker
1
Le nombre aléatoire 4ou binaire de @CurtainDog xkcd 0100peut être compressé à zéro bit. Le programme de décompression renverrait simplement «4». Ce n'est pas moins aléatoire que ça. Le problème avec dilbert est que nous ne savons pas si nous pouvons le compresser à zéro bit (décompresser en renvoyant toujours «neuf»). Il pourrait renvoyer huit aussi, puis nous pourrions compresser à 1 bit. Décompression par: 0-> neuf, 1-> huit. Nous aurions 1 bit aléatoire.
Ishtar
14

La réponse acceptée est assez belle, mais il existe une autre façon de répondre à votre question. La réponse de PachydermPuncher prend déjà cette approche alternative, et je vais juste l'étendre un peu.

La façon la plus simple de penser à la théorie de l'information est en termes de la plus petite unité d'information, un seul bit.

Dans la bibliothèque standard C, rand()renvoie un entier compris entre 0 et RAND_MAX, une limite qui peut être définie différemment selon la plate-forme. Supposons RAND_MAXqu'il se trouve que soit défini comme 2^n - 1nest un entier (cela se trouve être le cas dans l'implémentation de Microsoft, où nest 15). Ensuite, nous dirions qu'une bonne implémentation retournerait des nbits d'information.

Imaginez que vous rand()construisiez des nombres aléatoires en retournant une pièce pour trouver la valeur d'un bit, puis en répétant jusqu'à ce qu'elle ait un lot de 15 bits. Ensuite, les bits sont indépendants (la valeur d'un bit quelconque n'influence pas la probabilité que d'autres bits du même lot aient une certaine valeur). Ainsi, chaque bit considéré indépendamment est comme un nombre aléatoire compris entre 0 et 1 inclus, et est "uniformément réparti" sur cette plage (susceptible d'être égal à 0 comme 1).

L'indépendance des bits garantit que les nombres représentés par des lots de bits seront également répartis uniformément sur leur plage. Ceci est intuitivement évident: s'il y a 15 bits, la plage autorisée est de zéro à 2^15 - 1= 32767. Chaque nombre dans cette plage est un modèle unique de bits, tel que:

010110101110010

et si les bits sont indépendants, aucun motif n'est plus susceptible de se produire que tout autre motif. Donc, tous les nombres possibles dans la plage sont également probables. Et donc l'inverse est vrai: si rand()produit des entiers uniformément répartis, alors ces nombres sont faits de bits indépendants.

Considérez-la donc rand()comme une chaîne de production pour la fabrication de bits, qui se trouve juste à les servir par lots de taille arbitraire. Si vous n'aimez pas la taille, décomposez les lots en morceaux individuels, puis remettez-les dans les quantités que vous souhaitez (bien que si vous avez besoin d'une plage particulière qui n'est pas une puissance de 2, vous devez réduire vos nombres , et de loin la façon la plus simple de le faire est de convertir en virgule flottante).

Pour revenir à votre suggestion d'origine, supposons que vous souhaitiez passer de 15 lots à 30 lots, demandez rand()le premier nombre, décalez-le de 15 positions, puis ajoutez-en un autre rand(). C'est une façon de combiner deux appels vers rand()sans perturber une distribution uniforme. Cela fonctionne simplement parce qu'il n'y a pas de chevauchement entre les emplacements où vous placez les bits d'information.

Ceci est très différent de "l'étirement" de la plage rand()en multipliant par une constante. Par exemple, si vous vouliez doubler la portée, rand()vous pourriez multiplier par deux - mais maintenant vous n'obtiendrez que des nombres pairs et jamais des nombres impairs! Ce n'est pas exactement une distribution fluide et cela pourrait être un problème sérieux selon l'application, par exemple un jeu de type roulette permettant soi-disant des paris pairs / impairs. (En pensant en termes de bits, vous éviteriez cette erreur intuitivement, car vous vous rendriez compte que la multiplication par deux équivaut à déplacer les bits vers la gauche (plus grande signification) d'un endroit et à combler l'écart avec zéro. Donc, évidemment, la quantité d'informations est la même - elle a juste bougé un peu.)

De telles lacunes dans les plages de nombres ne peuvent pas être corrigées dans les applications de nombres à virgule flottante, car les plages de virgules flottantes ont intrinsèquement des lacunes qui ne peuvent tout simplement pas être représentées du tout: un nombre infini de nombres réels manquants existe dans l'écart entre chacun des deux flottants représentables numéros de points! Nous devons donc simplement apprendre à vivre avec des lacunes de toute façon.

Comme d'autres l'ont prévenu, l'intuition est risquée dans ce domaine, en particulier parce que les mathématiciens ne peuvent pas résister à l'attrait des nombres réels, qui confondent horriblement les choses pleines d'infinis noueux et de paradoxes apparents.

Mais au moins si vous pensez qu'il s'agit de bits, votre intuition pourrait vous pousser un peu plus loin. Les bits sont vraiment faciles - même les ordinateurs peuvent les comprendre.

Daniel Earwicker
la source
3
+1: En fait, il y a plus de nombres manquants entre deux flottants double précision IEEE qu'il n'y a de nombres dans l'ensemble des entiers (mathématiques).
Donal Fellows
13

Comme d'autres l'ont dit, la réponse courte et simple est: non, ce n'est pas plus aléatoire, mais cela change la distribution.

Supposons que vous jouiez à un jeu de dés. Vous avez des dés complètement équitables et aléatoires. Est-ce que les jets de dé seraient "plus aléatoires" si avant chaque jet de dé, vous mettez d'abord deux dés dans un bol, le secouez, choisissez un des dés au hasard, puis lancez-le? De toute évidence, cela ne ferait aucune différence. Si les deux dés donnent des nombres aléatoires, le choix aléatoire d'un des deux dés ne fera aucune différence. Dans les deux cas, vous obtiendrez un nombre aléatoire compris entre 1 et 6 avec une répartition uniforme sur un nombre suffisant de rouleaux.

Je suppose que dans la vraie vie, une telle procédure pourrait être utile si vous soupçonniez que les dés n'étaient PAS justes. Si, par exemple, les dés sont légèrement déséquilibrés, l'un a tendance à donner 1 plus souvent que 1/6 du temps, et un autre a tendance à donner 6 inhabituellement souvent, alors choisir aléatoirement entre les deux aurait tendance à obscurcir le biais. (Bien que dans ce cas, 1 et 6 soient toujours supérieurs à 2, 3, 4 et 5. Eh bien, je suppose que cela dépend de la nature du déséquilibre.)

Il existe de nombreuses définitions du caractère aléatoire. Une définition d'une série aléatoire est qu'il s'agit d'une série de nombres produits par un processus aléatoire. Selon cette définition, si je lance un dé juste 5 fois et que j'obtiens les nombres 2, 4, 3, 2, 5, c'est une série aléatoire. Si je lance ensuite ce même dé juste 5 fois de plus et que j'obtiens 1, 1, 1, 1, 1, alors c'est aussi une série aléatoire.

Plusieurs affiches ont souligné que les fonctions aléatoires sur un ordinateur ne sont pas vraiment aléatoires mais plutôt pseudo-aléatoires et que si vous connaissez l'algorithme et la graine, elles sont complètement prévisibles. C'est vrai, mais la plupart du temps complètement hors de propos. Si je mélange un jeu de cartes et que je les retourne une à la fois, cela devrait être une série aléatoire. Si quelqu'un jette un œil aux cartes, le résultat sera complètement prévisible, mais selon la plupart des définitions de l'aléatoire, cela ne le rendra pas moins aléatoire. Si la série passe des tests statistiques d'aléatoire, le fait que j'aie jeté un œil aux cartes ne changera pas ce fait. En pratique, si nous misons de grosses sommes d'argent sur votre capacité à deviner la prochaine carte, le fait que vous ayez jeté un œil aux cartes est très pertinent. Si nous utilisons la série pour simuler les choix de menu des visiteurs de notre site Web afin de tester les performances du système, le fait que vous ayez jeté un œil ne fera aucune différence. (Tant que vous ne modifiez pas le programme pour profiter de ces connaissances.)

ÉDITER

Je ne pense pas que je pourrais ma réponse au problème de Monty Hall dans un commentaire, donc je vais mettre à jour ma réponse.

Pour ceux qui n'ont pas lu le lien Bélisaire, l'essentiel est le suivant: un participant à un jeu télévisé a le choix entre 3 portes. Derrière l'un est un prix précieux, derrière les autres quelque chose de sans valeur. Il choisit la porte # 1. Avant de révéler s'il s'agit d'un gagnant ou d'un perdant, l'hôte ouvre la porte n ° 3 pour révéler qu'il est un perdant. Il donne ensuite au candidat la possibilité de passer à la porte n ° 2. Le candidat doit-il faire cela ou non?

La réponse, qui choque l'intuition de beaucoup de gens, est qu'il devrait changer. La probabilité que son choix d'origine soit le gagnant est de 1/3, que l'autre porte est le gagnant est de 2/3. Mon intuition initiale, ainsi que celle de beaucoup d'autres personnes, est qu'il n'y aurait aucun gain à changer, que les cotes viennent d'être modifiées à 50:50.

Après tout, supposons que quelqu'un ait allumé le téléviseur juste après que l'hôte ait ouvert la porte perdante. Cette personne verrait deux portes fermées restantes. En supposant qu'il connaît la nature du jeu, il dirait qu'il y a une 1/2 chance que chaque porte cache le prix. Comment les chances pour le spectateur peuvent-elles être de 1/2: 1/2 alors que les chances pour le concurrent sont de 1/3: 2/3?

J'ai vraiment dû y penser pour mettre en forme mon intuition. Pour comprendre cela, comprenez que lorsque nous parlons de probabilités dans un problème comme celui-ci, nous entendons la probabilité que vous attribuez en fonction des informations disponibles. Pour un membre de l'équipage qui a placé le prix derrière, disons, la porte # 1, la probabilité que le prix soit derrière la porte # 1 est de 100% et la probabilité qu'il soit derrière l'une des deux autres portes est nulle.

Les cotes du membre d'équipage sont différentes de celles du concurrent parce qu'il sait quelque chose que le concurrent ne sait pas, à savoir la porte derrière laquelle il a mis le prix. De même, les chances du candidat sont différentes de celles du spectateur car il sait quelque chose que le spectateur ne sait pas, à savoir quelle porte il a initialement choisie. Ce n'est pas sans importance, car le choix de l'hôte de la porte à ouvrir n'est pas aléatoire. Il n'ouvrira pas la porte choisie par le candidat et il n'ouvrira pas la porte qui cache le prix. S'il s'agit de la même porte, cela lui laisse deux choix. S'il s'agit de portes différentes, cela n'en laisse qu'une.

Alors, comment pouvons-nous arriver à 1/3 et 2/3? Lorsque le concurrent a initialement choisi une porte, il avait 1/3 de chance de choisir le gagnant. Je pense que cela est évident. Cela signifie qu'il y avait 2/3 de chances que l'une des autres portes soit gagnante. Si l'hôte lui donne la possibilité de changer sans donner d'informations supplémentaires, il n'y aurait aucun gain. Encore une fois, cela devrait être évident. Mais une façon de voir les choses est de dire qu'il y a 2/3 de chances qu'il gagne en changeant. Mais il a 2 alternatives. Ainsi, chacun n'a que 2/3 divisé par 2 = 1/3 de chance d'être le gagnant, ce qui n'est pas mieux que son choix d'origine. Bien sûr, nous connaissions déjà le résultat final, cela le calcule simplement d'une manière différente.

Mais maintenant, l'hôte révèle que l'un de ces deux choix n'est pas le gagnant. Donc, sur les 2/3 de chances qu'une porte qu'il n'a pas choisie soit gagnante, il sait maintenant que 1 des 2 alternatives ne l'est pas. L'autre pourrait l'être ou non. Il n'a donc plus 2/3 divisé par 2. Il a zéro pour la porte ouverte et 2/3 pour la porte fermée.

Geai
la source
Très bonnes analogies! Je suppose que c'est une très bonne explication en anglais simple, et contrairement à beaucoup d'autres, vous avez en fait répondu à ma question :)
Trufa
@Trufa @Jay La confusion entre la pré-connaissance possible des événements et le caractère aléatoire est TRÈS courante. Permettez-moi de partager avec vous cette histoire intéressante sur une femme qui a résolu un problème et jeté une honte sur certains des meilleurs mathématiciens de l'académie. Ils ont dit beaucoup de choses à regretter plus tard (comme "Vous avez fait une erreur, mais regardez le côté positif. Si tous ces docteurs avaient tort, le pays aurait de très sérieux ennuis."). Voici donc l'histoire, liée à vos considérations ... profitez-en! marilynvossavant.com/articles/gameshow.html
Dr belisarius
@belisarius yep. Je dis blackjack21 :) je plaisante, je te fais remarquer!
Trufa du
@belisarius BTW n'a jamais eu celui-là, je vais l'essayer maintenant!
Trufa
@Trufa Et voici un article montrant la réaction académique à la déclaration de Marilyn query.nytimes.com/gst/… (TRÈS TRÈS amusant)
Dr. belisarius
11

Considérez que vous avez un simple problème de retournement de pièces où même est considéré comme une tête et impair est considéré comme une queue. L'implémentation logique est:

rand() mod 2

Sur une distribution suffisamment grande, le nombre de nombres pairs doit être égal au nombre de nombres impairs.

Considérons maintenant un léger ajustement:

rand() * rand() mod 2

Si l'un des résultats est pair, alors le résultat entier doit être pair. Considérez les 4 résultats possibles (pair * pair = pair, pair * impair = pair, impair * pair = pair, impair * impair = impair). Maintenant, sur une distribution suffisamment importante, la réponse devrait même être de 75% du temps.

Je parierais des têtes si j'étais toi.

Ce commentaire est vraiment plus une explication de la raison pour laquelle vous ne devriez pas implémenter une fonction aléatoire personnalisée basée sur votre méthode qu'une discussion sur les propriétés mathématiques de l'aléatoire.

user479885
la source
1
Il faut se méfier! rand()%2peut ne pas être très aléatoire; cela dépend vraiment du caractère aléatoire du bit bas, et certains PRNG ne sont pas très bons de cette façon. (Bien sûr, dans certaines langues, vous obtenez un résultat à virgule flottante de rand()sorte que vous ne pouvez pas du tout le faire de cette façon…)
Donal Fellows
10

En cas de doute sur ce qui arrivera aux combinaisons de vos nombres aléatoires, vous pouvez utiliser les leçons que vous avez apprises en théorie statistique.

Dans la situation d'OP, il veut savoir quel est le résultat de X * X = X ^ 2 où X est une variable aléatoire distribuée le long de Uniform [0,1]. Nous utiliserons la technique CDF car il s'agit simplement d'un mappage un à un.

Puisque X ~ Uniform [0,1] c'est cdf est: f X (x) = 1 On veut la transformation Y <- X ^ 2 donc y = x ^ 2 Trouver l'inverse x (y): sqrt (y) = x cela nous donne x en fonction de y. Ensuite, trouvez la dérivée dx / dy: d / dy (sqrt (y)) = 1 / (2 sqrt (y))

La distribution de Y est donnée par: f Y (y) = f X (x (y)) | dx / dy | = 1 / (2 sqrt (y))

Nous n'avons pas encore fini, nous devons obtenir le domaine de Y. puisque 0 <= x <1, 0 <= x ^ 2 <1 donc Y est dans la plage [0, 1). Si vous voulez vérifier si le pdf de Y est bien un pdf, intégrez-le sur le domaine: intégrez 1 / (2 sqrt (y)) de 0 à 1 et en effet, il apparaît comme 1. Aussi, notez la forme du ladite fonction ressemble à ce qui a été publié par des bélis.

En ce qui concerne des choses comme X 1 + X 2 + ... + X n , (où X i ~ Uniforme [0,1]), nous pouvons simplement faire appel au théorème de la limite centrale qui fonctionne pour toute distribution dont les moments existent. C'est pourquoi le test Z existe réellement.

D'autres techniques pour déterminer le pdf résultant incluent la transformation jacobienne (qui est la version généralisée de la technique cdf) et la technique MGF.

EDIT: À titre de clarification, notez que je parle de la distribution de la transformation résultante et non de son caractère aléatoire . C'est en fait pour une discussion séparée. De plus, ce que j'ai réellement dérivé était pour (rand ()) ^ 2. Pour rand () * rand (), c'est beaucoup plus compliqué, ce qui, de toute façon, n'entraînera aucune distribution uniforme.

Wil
la source
9

Ce n'est pas exactement évident, mais rand()est généralement plus aléatoire que rand()*rand(). Ce qui est important, c'est que ce n'est pas vraiment très important pour la plupart des utilisations.

Mais tout d'abord, ils produisent des distributions différentes. Ce n'est pas un problème si c'est ce que vous voulez, mais c'est important. Si vous avez besoin d'une distribution particulière, ignorez toute la question «qui est plus aléatoire». Alors pourquoi est-ce rand()plus aléatoire?

Pourquoi rand()est plus aléatoire (en supposant qu'il produit des nombres aléatoires à virgule flottante avec la plage [0..1], ce qui est très courant), c'est que lorsque vous multipliez deux nombres FP avec beaucoup d'informations dans la mantisse, vous obtenez une certaine perte d'informations au bout du compte; il n'y a tout simplement pas assez de bits dans un flotteur double précision IEEE pour contenir toutes les informations qui se trouvaient dans deux flotteurs double précision IEEE sélectionnés de manière uniforme et aléatoire parmi [0..1], et ces bits supplémentaires d'informations sont perdus. Bien sûr, cela n'a pas beaucoup d'importance puisque vous n'utiliseriez (probablement) pas ces informations, mais la perte est réelle. Peu importe également quelle distribution vous produisez (c'est-à-dire quelle opération vous utilisez pour faire la combinaison). Chacun de ces nombres aléatoires a (au mieux) 52 bits d'informations aléatoires - cela '

La plupart des utilisations de nombres aléatoires n'utilisent même pas autant d'aléatoire que ce qui est réellement disponible dans la source aléatoire. Obtenez un bon PRNG et ne vous en faites pas trop. (Le niveau de «qualité» dépend de ce que vous en faites; vous devez être prudent lors de la simulation ou de la cryptographie Monte Carlo, mais sinon vous pouvez probablement utiliser le PRNG standard car c'est généralement beaucoup plus rapide.)

Associés Donal
la source
1
Cette réponse doit vraiment être lue en conjonction avec la magnifique de Bélisaire; ils couvrent différents aspects du problème.
Donal Fellows
7

Les aléas flottants sont basés, en général, sur un algorithme qui produit un entier entre zéro et une certaine plage. En tant que tel, en utilisant rand () * rand (), vous dites essentiellement int_rand () * int_rand () / rand_max ^ 2 - ce qui signifie que vous excluez tout nombre premier / rand_max ^ 2.

Cela modifie considérablement la distribution aléatoire.

rand () est uniformément distribué sur la plupart des systèmes et difficile à prévoir s'il est correctement ensemencé. Utilisez-le à moins que vous n'ayez une raison particulière de faire des calculs dessus (c'est-à-dire façonner la distribution en une courbe nécessaire).

Fordi
la source
@belisarius: Ce n'est le cas que si 1 est un résultat possible du processus aléatoire.
Joris Meys
J'ai dû lire longuement les réponses avant de trouver celle-ci. Vous énoncez un problème clair: l'espace de résultat (nombre de valeurs possibles) de rand()*rand()est plus petit que l'espace de résultat de rand()- car il exclut les nombres premiers. Obtient mon vote ...
Floris
7

La multiplication des nombres se retrouverait dans une gamme de solutions plus petite en fonction de l'architecture de votre ordinateur.

Si l'écran de votre ordinateur affiche 16 chiffres, rand()cela signifie que 0,12234567890123 multiplié par seconde rand(), 0,12234567890123, ce qui donnerait 0,0152415, vous trouverez certainement moins de solutions si vous répétez l'expérience 10 ^ 14 fois.

Huub
la source
3

La plupart de ces distributions se produisent parce que vous devez limiter ou normaliser le nombre aléatoire.

Nous le normalisons pour qu'il soit tout positif, qu'il s'inscrive dans une plage, et même pour s'adapter aux contraintes de la taille de la mémoire pour le type de variable affecté.

En d'autres termes, parce que nous devons limiter l'appel aléatoire entre 0 et X (X étant la taille limite de notre variable), nous aurons un groupe de nombres "aléatoires" entre 0 et X.

Maintenant, lorsque vous ajoutez le nombre aléatoire à un autre nombre aléatoire, la somme sera quelque part entre 0 et 2X ... cela biaise les valeurs loin des points de bord (la probabilité d'ajouter deux petits nombres ensemble et deux grands nombres ensemble est très petite lorsque vous avez deux nombres aléatoires sur une large plage).

Pensez au cas où vous aviez un nombre proche de zéro et que vous l'ajoutez avec un autre nombre aléatoire, il deviendra certainement plus grand et éloigné de 0 (ce sera vrai pour les grands nombres et il est peu probable qu'il y ait deux grands nombres (nombres proches de X) retournés deux fois par la fonction Random.

Maintenant, si vous deviez configurer la méthode aléatoire avec des nombres négatifs et des nombres positifs (s'étendant également sur l'axe zéro), ce ne serait plus le cas.

Disons par exemple que RandomReal({-x, x}, 50000, .01)vous obtiendrez une distribution uniforme des nombres du côté négatif et positif et que si vous additionniez les nombres aléatoires, ils conserveraient leur "caractère aléatoire".

Maintenant, je ne sais pas ce qui se passerait avec l' Random() * Random()intervalle négatif à positif ... ce serait un graphique intéressant à voir ... mais je dois revenir à l'écriture de code maintenant. :-P

user479538
la source
2
  1. Il n'y a rien de plus aléatoire. C'est aléatoire ou non. Aléatoire signifie "difficile à prévoir". Cela ne signifie pas non déterministe. Random () et random () * random () sont également aléatoires si random () est aléatoire. La distribution n'est pas pertinente en ce qui concerne le caractère aléatoire. Si une distribution non uniforme se produit, cela signifie simplement que certaines valeurs sont plus probables que d'autres; ils sont encore imprévisibles.

  2. Étant donné que le pseudo-aléatoire est impliqué, les nombres sont très déterministes. Cependant, le pseudo-aléatoire est souvent suffisant dans les modèles de probabilité et les simulations. Il est bien connu que rendre compliqué un générateur de nombres pseudo-aléatoires ne fait que le rendre difficile à analyser. Il est peu probable qu'il améliore le caractère aléatoire; il fait souvent échouer les tests statistiques.

  3. Les propriétés souhaitées des nombres aléatoires sont importantes: répétabilité et reproductibilité, statistique aléatoire, (généralement) uniformément répartie, et une grande période sont quelques-unes.

  4. Concernant les transformations sur les nombres aléatoires: Comme l'a dit quelqu'un, la somme de deux ou plus uniformément distribués donne une distribution normale. C'est le théorème de la limite centrale additive . Il s'applique quelle que soit la distribution source tant que toutes les distributions sont indépendantes et identiques. le multiplicatifle théorème de la limite centrale dit que le produit de deux ou plusieurs variables aléatoires indépendantes et réparties de façon identique est lognormal. Le graphique créé par quelqu'un d'autre semble exponentiel, mais il est vraiment log-normal. Donc random () * random () est distribué lognormalement (bien qu'il ne soit pas indépendant puisque les nombres sont tirés du même flux). Cela peut être souhaitable dans certaines applications. Cependant, il est généralement préférable de générer un nombre aléatoire et de le transformer en un nombre lognormalement distribué. Random () * random () peut être difficile à analyser.

Pour plus d'informations, consultez mon livre sur www.performorama.org. Le livre est en construction, mais le matériel pertinent est là. Notez que les numéros de chapitre et de section peuvent changer avec le temps. Chapitre 8 (théorie des probabilités) - sections 8.3.1 et 8.3.3, chapitre 10 (nombres aléatoires).

À M
la source
1

Nous pouvons comparer deux tableaux de nombres concernant le caractère aléatoire en utilisant la complexité de Kolmogorov Si la séquence de nombres ne peut pas être compressée, alors c'est le plus aléatoire que nous pouvons atteindre à cette longueur ... Je sais que ce type de mesure est plus théorique option...

HamoriZ
la source
1

En fait, quand vous pensez à ce sujet rand() * rand()est moins aléatoire que rand(). Voici pourquoi.

Essentiellement, il existe le même nombre de nombres impairs que les nombres pairs. Et dire que 0,04325 est impair, et comme 0,388 est pair, et 0,4 est pair, et 0,15 est impair,

Cela signifie qu'il rand()a une chance égale d'être un nombre décimal pair ou impair .

D'un autre côté, rand() * rand()ses chances sont-elles empilées un peu différemment. Disons:

double a = rand();
double b = rand();
double c = a * b;

aet les bdeux ont une probabilité de 50% d'être pair ou impair. Sachant que

  • pair * pair = pair
  • pair * impair = pair
  • impair * impair = impair
  • impair * pair = pair

signifie qu'il y a 75% de chance qui cest pair, alors que seulement 25% de chance c'est impair, ce qui rend la valeur de rand() * rand()plus prévisible que rand(), donc moins aléatoire.

John S.
la source
rand()donne généralement un nombre compris entre 0 et 1. Est-ce que parler de savoir si c'est pair ou impair a un sens?
Teepeemm
1
En fait, 0.2*0.2=0.04ce qui suggère un défaut fondamental avec cette approche: multiplier les 53 bits de deux doubles donnera environ 100 bits dans le résultat. Mais la dernière moitié de ces bits sera supprimée. Donc, lorsque vous prenez deux doubles avec un 1 comme bit le moins significatif, vous ne pouvez rien dire sur le bit le moins significatif de leur produit.
Teepeemm
Ou, pour le dire autrement, vous avez supposé que la définition de "pair" et "impair" qui a du sens pour la distribution de rand()est la même que les définitions de "pair" et "impair" qui ont du sens pour la distribution de rand()*rand(). Si ce n'est pas le cas, cet argument échoue. C'est vrai pour les entiers, mais ce ne sont pas des entiers.
David Schwartz
0

Utilisez un registre à décalage à rétroaction linéaire (LFSR) qui implémente un polynôme primitif.

Le résultat sera une séquence de 2 ^ n nombres pseudo-aléatoires, c'est-à-dire aucun répéter dans la séquence où n est le nombre de bits dans le LFSR .... résultant en une distribution uniforme.

http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Utilisez une graine "aléatoire" basée sur les microsecs de l'horloge de votre ordinateur ou peut-être un sous-ensemble du résultat md5 sur certaines données en constante évolution dans votre système de fichiers.

Par exemple, un LFSR 32 bits générera 2 ^ 32 nombres uniques en séquence (pas 2 pareils) en commençant par une graine donnée. La séquence sera toujours dans le même ordre, mais le point de départ sera différent (évidemment) pour des graines différentes. Donc, si une séquence pouvant se répéter entre les semis n'est pas un problème, cela pourrait être un bon choix.

J'ai utilisé des LFSR 128 bits pour générer des tests aléatoires dans des simulateurs matériels en utilisant une valeur de départ qui correspond aux résultats md5 sur des données système en constante évolution.

johnny
la source
0

En supposant que rand()renvoie un nombre entre [0, 1)il est évident que rand() * rand()sera biaisé vers 0. En effet, la multiplication xpar un nombre entre [0, 1)entraînera un nombre inférieur à x. Voici la distribution de 10000 nombres aléatoires supplémentaires :

Si rand()renvoie un entier entre [x, y]alors vous avez la distribution suivante. Notez le nombre de valeurs paires et impaires:

Salman A
la source
-1

OK, je vais donc essayer d'ajouter de la valeur pour compléter les autres réponses en disant que vous créez et utilisez un générateur de nombres aléatoires.

Les générateurs de nombres aléatoires sont des dispositifs (dans un sens très général) qui ont de multiples caractéristiques qui peuvent être modifiées pour s'adapter à un objectif. Certains (de moi) sont:

  • Entropie: comme dans Shannon Entropie
  • Distribution: distribution statistique (poisson, normal, etc.)
  • Type: quelle est la source des nombres (algorithme, événement naturel, combinaison de, etc.) et algorithme appliqué.
  • Efficacité: rapidité ou complexité d'exécution.
  • Patterns: périodicité, séquences, runs, etc.
  • et probablement plus ...

Dans la plupart des réponses ici, la distribution est le principal point d'intérêt, mais en mélangeant et en associant des fonctions et des paramètres, vous créez de nouvelles façons de générer des nombres aléatoires qui auront des caractéristiques différentes pour certaines dont l'évaluation peut ne pas être évidente à première vue.

Loki
la source
-1

Il est facile de montrer que la somme des deux nombres aléatoires n'est pas nécessairement aléatoire. Imaginez que vous ayez un dé et un jet à 6 faces. Chaque numéro a 1/6 de chance d'apparaître. Supposons maintenant que vous disposiez de 2 dés et que vous avez résumé le résultat. La répartition de ces sommes n'est pas 1/12. Pourquoi? Parce que certains chiffres apparaissent plus que d'autres. Il en existe plusieurs partitions . Par exemple, le nombre 2 est la somme de 1 + 1 seulement mais 7 peut être formé par 3 + 4 ou 4 + 3 ou 5 + 2 etc ... donc il a une plus grande chance d'apparaître.

Par conséquent, l'application d'une transformation, dans ce cas, l'ajout d'une fonction aléatoire ne la rend pas plus aléatoire, ni ne préserve nécessairement le caractère aléatoire. Dans le cas des dés ci-dessus, la distribution est biaisée à 7 et donc moins aléatoire.

sashang
la source
-1

Comme d'autres l'ont déjà souligné, cette question est difficile à répondre car chacun de nous a sa propre image de l'aléatoire dans sa tête.

C'est pourquoi, je vous recommande fortement de prendre un peu de temps et de parcourir ce site pour avoir une meilleure idée de l'aléatoire:

Pour revenir à la vraie question. Il n'y a pas plus ou moins de hasard dans ce terme:

les deux n'apparaissent qu'au hasard !

Dans les deux cas - juste rand () ou rand () * rand () - la situation est la même: après quelques milliards de nombres, la séquence se répétera (!) . Il semble aléatoire pour l'observateur, car il ne connaît pas toute la séquence, mais l'ordinateur n'a pas de véritable source aléatoire - il ne peut donc pas non plus produire de hasard.

Ex: La météo est-elle aléatoire? Nous n'avons pas suffisamment de capteurs ou de connaissances pour déterminer si la météo est aléatoire ou non.

Fabian Bigler
la source
-2

La réponse serait que cela dépend, espérons que le rand () * rand () serait plus aléatoire que rand (), mais comme:

  • les deux réponses dépendent de la taille en bits de votre valeur
  • que dans la plupart des cas, vous générez en fonction d'un algorithme pseudo-aléatoire (qui est principalement un générateur de nombres qui dépend de l'horloge de votre ordinateur, et pas beaucoup au hasard).
  • rendre votre code plus lisible (et ne pas invoquer un dieu vaudou aléatoire de hasard avec ce genre de mantra).

Eh bien, si vous vérifiez l'un de ces éléments ci-dessus, je vous suggère de choisir le simple "rand ()". Parce que votre code serait plus lisible (ne vous demandez pas pourquoi vous avez écrit ceci, pendant ... enfin ... plus de 2 secondes), facile à maintenir (si vous voulez remplacer votre fonction rand par un super_rand).

Si vous voulez un meilleur aléatoire, je vous recommande de le diffuser à partir de n'importe quelle source qui fournit suffisamment de bruit ( radio statique ), puis un simple rand()devrait suffire.

dvhh
la source