Pourquoi la génération de 8 bits aléatoires est-elle uniforme sur (0, 255)?

35

Je génère 8 bits aléatoires (un 0 ou un 1) et les concatène ensemble pour former un nombre de 8 bits. Une simple simulation Python donne une distribution uniforme sur le jeu discret [0, 255].

J'essaie de justifier pourquoi cela a du sens dans ma tête. Si je compare cela au fait de jeter 8 pièces, la valeur attendue ne serait-elle pas autour de 4 têtes / 4 queues? Pour moi, il est donc logique que mes résultats reflètent un pic au milieu de la plage. En d'autres termes, pourquoi une séquence de 8 zéros ou de 8 uns semble-t-elle être tout aussi probable qu'une séquence de 4 et 4, ou de 5 et 3, etc.? Qu'est-ce que j'oublie ici?

vitreux
la source
17
La valeur attendue de la distribution des bits dans une plage aléatoire uniforme de la plage [0,255] se situe également autour de 4 1/4 0.
user253751
2
Le fait d’attribuer un poids égal à chaque nombre compris entre 0 et 255 ne signifie pas que le résultat de la fonction "différence entre le nombre de 1 et de 0" apparaîtra également une fois et une seule fois. Je pourrais donner un poids égal à chaque personne de mon organisation. Cela ne veut pas dire que leur âge aurait le même poids. Certains âges pourraient être beaucoup plus communs que d'autres. Mais une personne n'est pas plus commune que toute autre personne.
Brad Thomas
2
Pensez-y de cette façon ... Votre premier bit aléatoire déterminera la valeur du bit 7, un 1 vaut 128 et un 0 vaut 0. Sur 256 numéros, vous avez 50% de chances que le nombre soit 0-127 si le le bit est 0 et 128-255 si le bit est 1. Supposons que c'est 0, alors le bit suivant détermine si le résultat sera 0-63 ou 64-127. Les 8 bits doivent former l'un des 256 résultats probables. Vous pensez ajouter des totaux comme vous le feriez avec des dés. Les probabilités d'obtenir 4 1 et 4 0 sont plus élevées que d'obtenir 8 1, mais elles peuvent être arrangées de différentes manières pour vous donner un résultat différent.
Jason Goemaat
2
Supposons que vous lancez un dé à 256 faces portant les chiffres de 0 à 255. Vous attendez une distribution uniforme. Supposons maintenant que vous ré-étiquetiez le dé pour qu’un côté dise 0, 8 côtés disent 1, 28 côtés disent 2, et ainsi de suite; chaque côté est maintenant étiqueté avec le nombre de bits actifs dans le nombre qui était auparavant de ce côté. Vous relancez le dé; pourquoi vous attendriez-vous à obtenir une distribution uniforme des nombres de 0 à 8?
Eric Lippert
Si la distribution fonctionnait ainsi, je ne pourrais gagner beaucoup d'argent en misant à la roulette qu'après que 7 rouges soient apparus à la suite. 7 et 1 est plus de 8 fois plus probable que 8 et 0! (en ignorant les 0, mais ce biais dépasse de loin le 0 et le 00)
Cruncher le

Réponses:

61

TL; DR: Le contraste entre les pièces de monnaie et les pièces de monnaie est que, dans le cas des pièces de monnaie, vous ignorez l’ ordre des résultats. HHHHTTTT est traité comme le même que TTTTHHHH (les deux ont 4 têtes et 4 queues). Mais peu à peu, l’ordre vous importe (parce que vous devez donner des "poids" aux positions des bits pour obtenir 256 résultats), donc 11110000 est différent de 00001111.


Explication plus longue: ces concepts peuvent être unifiés plus précisément si nous définissons un peu plus formel le problème. Considérez une expérience comme une séquence de huit essais avec des résultats dichotomiques et une probabilité de "succès" 0,5, et un "échec" 0,5, les essais étant indépendants. En général, j'appellerai cela succès, essais totaux et échecs et la probabilité de succès est .n n - k pknn-kp

  • Dans l'exemple de pièce, le résultat " têtes, queues" ignore l'ordre des essais (4 têtes correspond à 4 têtes quel que soit l'ordre d'apparition), ce qui donne à penser que 4 têtes sont plus susceptibles que 0 ou 8 têtes. Quatre têtes sont plus courantes car il existe de nombreuses façons de créer quatre têtes (TTHHTHTHH, ou HHTTHHTT, etc.) par rapport à un autre nombre (8 têtes n'ont qu'une séquence). Le théorème binomial donne le nombre de façons de réaliser ces différentes configurations.n - kkn-k

  • En revanche, l'ordre est important en bits, car chaque lieu est associé à un "poids" ou à une "valeur de lieu". Une propriété du coefficient binomial est que , c'est-à-dire que si nous comptons toutes les différentes séquences ordonnées, nous obtenons . Ceci relie directement l’idée du nombre de façons différentes de faire têtes dans essais binomiaux au nombre de séquences d’octets différentes.2n=Σk=0n(nk)28=256kn

  • De plus, nous pouvons montrer que les 256 résultats sont également probables par la propriété d’indépendance. Les essais précédents n’ont pas d’influence sur l’essai suivant. La probabilité d’un ordre particulier est donc généralement (car la probabilité conjointe d’événements indépendants est le produit de leurs probabilités). Parce que les essais sont équitables, , cette expression est réduite à . Comme tous les ordres ont la même probabilité, nous avons une distribution uniforme sur ces résultats (qui, par codage binaire, peut être représentée sous forme d’entiers dans ). P ( succès ) = P ( échec ) = p = 0,5 P ( ordre quelconque ) = 0,5 8 = 1pk(1-p)n-kP(Succès)=P(échouer)=p=0.5 [0,255]P(toute commande)=0.58=1256[0,255]

  • Enfin, nous pouvons ramener ce cercle complet au tirage au sort et à la distribution binomiale. Nous savons que l'occurrence de 0 têtes n'a pas la même probabilité que 4 têtes, ce qui s'explique par le fait qu'il existe différentes manières d'ordonner les occurrences de 4 têtes et que le nombre de ces ordres est donné par le théorème binomial. Donc, doit être pondéré d’une manière ou d’une autre, en particulier il doit être pondéré par le coefficient binomial. Cela nous donne donc le PMF de la distribution binomiale, . Il peut être surprenant que cette expression soit un PMF, en particulier parce qu’il n’est pas immédiatement évident que sa somme soit égale à 1. Pour vérifier, nous devons vérifier queP ( k  succès ) = ( nP(4 têtes)Σ n k = 0 ( nP(k successes)=(nk)pk(1p)nk1=1n=(p+1-p)n= n k = 0 ( nΣk=0n(nk)pk(1-p)n-k=1Cependant, il ne s’agit que d’un problème de coefficients binomiaux: .1=1n=(p+1p)n=k=0n(nk)pk(1p)nk

Sycorax dit Réintégrer Monica
la source
Cela a du sens ... mais alors ne devrions-nous pas nous attendre à ce que les 15, 30, 60, 120 et 240 aient un poids plus élevé dans la distribution que 0 ou 255?
vitreux le
1
Je pense que je le comprends maintenant. Je vais accepter cette réponse parce que je pense que la clé ici est l'ordre, sur lequel vous avez attiré l'attention. Merci
vitreux
Encore une note - pour utiliser mon exemple de pièce, il s’agit de lancer 8 pièces en même temps, au lieu de 8 essais de lancer une pièce. C'est là que réside ma confusion.
vitreux le
2
La notion de "valeur de position" tirée de "l'arithmétique élémentaire" est particulièrement applicable ici; pour utiliser une analogie décimale, on considère 10001000et 10000001des nombres très différents.
JM n'est pas un statisticien le
17

pourquoi une séquence de 8 zéros ou de 8 uns semble-t-elle être aussi probable qu'une séquence de 4 et 4, ou de 5 et 3, etc.

Le paradoxe apparent peut être résumé en deux propositions qui peuvent paraître contradictoires:

  1. La séquence (huit zéros) est également probable que la séquence (quatre zéros, quatre uns). (En général, toutes les séquences ont la même probabilité, quel que soit le nombre de zéros / unités qu'elles ont.)s 2 : 01010101 2 8s1:00000000s2:0101010128

  2. L'événement " : la séquence avait quatre zéros " est plus probable (en effet, fois plus probable) que l'événement " : la séquence avait huit zéros ". 70 e 2e170e2

Ces propositions sont toutes deux vraies. Parce que l'événement comprend de nombreuses séquences.e1

Leonbloy
la source
8

Toutes les séquences ont la même probabilité = 1/256. Il est faux de penser que les séquences qui se rapprochent d'un nombre égal de 0 et de 1 sont plus probables au vu de l'interprétation de la question. Il devrait être clair que nous arrivons à 1/256 parce que nous supposons l' indépendance d'un procès à l'autre . C'est pourquoi nous multiplions les probabilités et le résultat d'un essai n'a aucune influence sur le suivant.2 82828

Michael R. Chernick
la source
2
Ce serait une bonne réponse si elle était courte ... si la question n'incluait pas le mot "pourquoi". En l’occurrence, vous répétez simplement l’un des éléments de la question, sans aucune explication.
Tin Man
1
En fait ... Cette réponse est fausse, voir la réponse de leonbloy pour savoir pourquoi.
Tin Man
3
@Walt ce n'est pas incorrect. La subtilité du langage. Une séquence donnée n’est pas plus probable car elle présente moins de déséquilibre entre 0 et 1. Il y a simplement plus de telles séquences .
Hobbs
4
Est-ce que quelqu'un est d'accord avec moi? Si un 0 a une probabilité de 1/2 et un 1 a une probabilité de 1/2 et qu'un terme de la séquence est indépendant du suivant, la probabilité qu'une séquence donnée de longueur 8 ait une probabilité de . et tout comme n'importe quelle autre séquence de 8.1/28=1/256
Michael R. Chernick
4
@ Michael, je suis tout à fait d'accord et je suis heureux de voir enfin un appel explicite au cœur même du problème: l' indépendance. Je serais heureux d’invoquer votre réponse si vous pouviez y inclure ce commentaire.
whuber
7

EXEMPLE avec 3 bits (souvent, un exemple est plus illustratif)

Je vais écrire les nombres naturels 0 à 7 comme:

  • Un nombre en base 10
  • Un nombre en base 2 (c'est-à-dire une séquence de bits)
  • Une série de lancers de pièces impliquée par la représentation de la base 2 (1 désigne un retournement de têtes et 0 désigne un retournement de queues).

Base 10Base 2 (avec 3 bits)Série de bas de caisse impliciteLes chefsLes queues0000TTT031001TTH122010THT123011THH214100HTT125101HTH216110HHT217111HHH30

Choisir un nombre naturel compris entre 0 et 7 avec une probabilité égale revient à choisir l'une des séries de lancers de pièces à droite avec une probabilité égale.

Par conséquent, si vous choisissez un nombre dans la distribution uniforme sur les nombres entiers de 0 à 7, vous avez un chances de choisir 3 têtes,318 chances de choisir 2 têtes,338 chances de choisir 1 tête et138 chances de choisir 0 tête.18

Matthew Gunn
la source
3

La réponse de Sycorax est correcte, mais il semble que vous ne sachiez pas pourquoi. Lorsque vous retournez 8 pièces ou générez 8 bits aléatoires en tenant compte de l'ordre, votre résultat sera l'une des 256 possibilités également probables. Dans votre cas, chacun de ces 256 résultats possibles est mappé de manière unique sur un entier, vous obtenez ainsi une distribution uniforme comme résultat.

Si vous ne prenez pas en compte l'ordre, par exemple en considérant le nombre de têtes ou de queues que vous avez obtenu, il n'y a que 9 résultats possibles (0 têtes / 8 queues - 8 têtes / 0 queues), et ils ne sont plus aussi probables . La raison en est que sur les 256 résultats possibles, il y a 1 combinaison de retournements qui vous donne 8 têtes / 0 queues (HHHHHHHHH) et 8 combinaisons qui donnent 7 têtes / 1 queues (une queue dans chacune des 8 positions l’ordre), mais 8C4 = 70 façons d’avoir 4 têtes et 4 queues. Dans le cas de la pièce retournée, chacune de ces 70 combinaisons est mappée à 4 têtes / 4 queues, mais dans le problème du nombre binaire, chacune de ces 70 résultats mappe à un entier unique.

Acier noir
la source
2

Le problème, reformulé, est le suivant: pourquoi le nombre de combinaisons de 8 chiffres binaires aléatoires est-il pris de 0 à 8 chiffres sélectionnés (par exemple, les 1) à un moment différent du nombre de permutations de 8 chiffres binaires aléatoires? Dans le présent contexte, le choix aléatoire de 0 et de 1 signifie que chaque chiffre est indépendant de tout autre, de sorte que les chiffres ne sont pas corrélés et que ; .p(0)=p(1)=12

La réponse est: il y a deux encodages différents; 1) codage sans perte de permutations et 2) codage avec perte de combinaisons.

Ad 1) pour coder sans perte les nombres de telle sorte que chaque séquence est unique , nous pouvons voir que le numéro comme un binaire entier , où X i sont les gauche à droite i t h chiffres dans le séquence binaire de 0 et 1 aléatoires. Cela rend chaque permutation unique, car chaque chiffre aléatoire est ensuite codé en position. Et le nombre total de permutations est alors 2 8 = 256Σje=182je-1XjeXjejeth28=256. Ensuite, par coïncidence, vous pouvez traduire ces chiffres binaires en nombres de base 10 compris entre 0 et 255 sans perte d'unicité. Vous pouvez également réécrire ce nombre en utilisant tout autre codage sans perte (par exemple, données compressées sans perte, Hex, Octal). La question elle-même, cependant, est binaire. Chaque permutation est alors également probable car il n’ya alors qu’une façon de créer chaque séquence de codage unique, et nous avons supposé que l’apparition d’un 1 ou d’un 0 était également probable n'importe où dans cette chaîne, de sorte que chaque permutation était également probable.

Σje=1820XjeC(8,Σje=18Xje)Σje=18XjeC(8,4)

Remarque: à l'heure actuelle, la réponse ci-dessus est la seule à contenir une comparaison de calcul explicite des deux codages, et la seule qui mentionne même le concept de codage. Cela a pris un certain temps pour bien faire les choses, c'est pourquoi cette réponse a toujours été votée négativement. S'il y a des plaintes en suspens, laissez un commentaire.

Mise à jour: Depuis la dernière mise à jour, je suis ravi de constater que le concept d'encodage a commencé à faire son chemin dans les autres réponses. Pour montrer cela explicitement pour le problème actuel, j’attache le nombre de permutations codées avec perte dans chaque combinaison.entrez la description de l'image ici

C(8,n)-1n069256-9=247

Carl
la source
2
000000000100000001
16
Franchement, tout est correct, mais cela ne règle pas la question . Vous avez fait du bon travail en montrant comment huit bits ordonnés peuvent représenter des nombres dans l’intervalle, mais vous n’avez pas expliqué pourquoi la sélection aléatoire de ces bits donnait une distribution uniforme (quelque chose qui est, certes, si simple qu’il faut clairement l'expliquer. subtilité).
dmckee
9
Ne serait-il pas plus simple de dire que 8 bits aléatoires (indépendamment) sont uniformément répartis sur [00000000, 11111111] pour la même raison que 3 chiffres aléatoires sont uniformément répartis sur [000, 999]? Le discours sur les raisons pour lesquelles les ordinateurs utilisent des bases binaires et des bases fractionnaires est totalement inutile et sans rapport. Je veux dire, le fait que binaire utilise uniquement les symboles 0 et 1 est simplement une propriété inhérente de la base 2 ... inutile de l'expliquer. Si vous souhaitez conserver ce type d'explication, il serait probablement plus utile d'expliquer le fonctionnement des bases en général, mais ce serait toujours à côté de la question.
Blackhawk
3
Je suis heureux de voir à quel point cette réponse s'est améliorée. Cependant, j'ai du mal à comprendre ce que les représentations en base 10 ont à voir avec cette question (les bases 3 ou 17 ne fonctionneraient-elles pas aussi bien?) Et je ne vois pas ce qui pourrait être spécial à propos de 8 bits mais qui ne fonctionne pas aussi. généraliser à un nombre fini de bits. Cela suggère que la plupart des considérations de cette réponse sont tangentielles ou non pertinentes.
whuber
3
Et je tiens à vous remercier pour cette caractérisation heureuse de la confusion exprimée dans la question: codage "avec perte" et "sans perte". C'est mémorable, légèrement différent des autres perspectives, perspicace et pourrait éventuellement éclaircir cette confusion rapidement.
whuber
1

J'aimerais développer un peu l'idée de la dépendance à l'ordre par rapport à l'indépendance.

Dans le problème du calcul du nombre attendu de têtes en retournant 8 pièces, nous additionnons les valeurs de 8 distributions identiques, chacune étant la distribution de Bernoulli [; B(1, 0.5) ;](en d'autres termes, une probabilité de 50% de 0, une probabilité de 50% de 1). La distribution de la somme est la distribution binomiale [; B(8, 0.5) ;], qui a la forme de bosse familière avec la plupart des probabilités centrées autour de 4.

Dans le problème du calcul de la valeur attendue d'un octet constitué de 8 bits aléatoires, chaque bit a une valeur différente qu'il contribue à l'octet. Nous additionnons donc les valeurs de 8 distributions différentes . Le premier est [; B(1, 0.5) ;], le deuxième est [; 2 B(1, 0.5) ;], le troisième est [; 4 B(1, 0.5) ;], ainsi de suite jusqu'au huitième qui est [; 128 B(1, 0.5) ;]. La distribution de cette somme est naturellement très différente de la première.

Si vous vouliez prouver que cette dernière distribution est uniforme, je pense que vous pouvez le faire de manière inductive - la distribution du bit le plus bas est uniforme avec une plage de 1 par hypothèse, vous voudrez donc montrer que si la distribution des [; n ;]bits le plus bas est uniforme avec une plage de [; 2^n - 1} ;]alors l’ajout du premier [; n+1 ;]bit rend la distribution des [; n + 1 ;]bits les plus bas uniforme avec une plage de [; 2^{n+1} - 1 ;], réalisant une preuve pour tous les positifs[; n ;]. Mais la manière intuitive est probablement le contraire. Si vous commencez par le bit haut et que vous choisissez les valeurs une par une jusqu'au bit le plus bas, chaque bit divise exactement l’espace des résultats possibles en deux, et chaque moitié est choisie avec une probabilité égale. En bas, chaque valeur individuelle doit avoir la même probabilité pour être choisie.

Hobbs
la source
Ce n'est pas un uniforme continu. Le bit est 0 ou 1 et rien entre les deux.
Michael R. Chernick
@ MichaelChernick bien sûr, nous ne traitons ici que des distributions discrètes.
Hobbs
L'OP a déclaré que les bits ne sont que 1 ou 0 et qu'il n'y a rien entre les deux.
Michael R. Chernick
1
@ MichaelChernick correct.
Hobbs
1

Si vous effectuez une recherche binaire en comparant chaque bit, vous avez besoin du même nombre d’étapes pour chaque nombre de 8 bits, de 0000 0000 à 1111 1111, qui ont tous deux une longueur de 8 bits. À chaque étape de la recherche binaire, les deux côtés ont 50% de chances de se produire. En fin de compte, chaque nombre ayant la même profondeur et les mêmes probabilités, sans véritable choix, chaque nombre doit avoir le même poids. Ainsi, la distribution doit être uniforme, même lorsque chaque mors est déterminé par des virements.

Cependant, le digitsum des nombres n’est pas uniforme et aurait une distribution égale à celle de lancer 8 pièces.

Si tout va bien utile
la source
1

Il n'y a qu'une séquence avec huit zéros. Il y a soixante-dix séquences avec quatre zéros et quatre autres.

Par conséquent, alors que 0 a une probabilité de 0,39%, et 15 a également une probabilité de 0,39% et 23 [00010111] a une probabilité de 0,39%, etc., si vous additionnez les soixante-dix des probabilités de 0,39%. vous obtenez 27,3%, ce qui correspond à la probabilité d'avoir quatre unités. La probabilité de chaque résultat individuel de quatre et quatre ne doit pas nécessairement être supérieure à 0,39% pour que cela fonctionne.

Au hasard832
la source
Cela ne change pas le fait que toutes les 256 séquences sont également probables.
Michael R. Chernick
@MichaelChernick Je n'ai pas dit ça, j'ai dit explicitement qu'ils ont tous une probabilité de 0,39%, je m'adresse aux hypothèses de OP.
Random832
Vous avez raison. C'est une autre façon de dire ce que j'ai dit dans ma réponse. Certaines des autres réponses sont fausses.
Michael R. Chernick
1

Considérez les dés

Pensez à lancer deux dés, un exemple courant de distribution non uniforme. Par souci de mathématiques, imaginez les dés sont numérotés de 0 à 5 au lieu de 1 à 6. traditionnelle La raison pour laquelle la distribution est pas uniforme que vous regardez la somme des jets de dés, où de multiples combinaisons peuvent donner la même total comme {5, 0}, {0, 5}, {4, 1}, etc., générant tous 5.

616060

Comme le soulignent @Sycorax et @Blacksteel, cette différence se résume vraiment à la question de l'ordre.

Blackhawk
la source
0

Chaque bit que vous choisissez est indépendant l'un de l'autre. Si vous considérez pour le premier bit il y a un

  • 50% de probabilité que ce soit 1

et

  • 50% de probabilité qu'il s'agisse de 0.

(12)81256

Ahemone
la source
Toutes ces affirmations sont vraies, mais cela n'indique pas pourquoi les lancers de pièces, qui sont également justes et indépendants, n'ont que 9 résultats distincts lorsqu'un résultat est défini comme le nombre de têtes et de queues.
Sycorax dit: Réintégrer Monica le
Ce n'est que le résultat de placer les résultats dans un système ordonné après les avoir choisis. La même distribution serait obtenue même si les bits aléatoires étaient placés dans des positions aléatoires sur l'octet. Vous obtiendrez également la même distribution sur les lancers de pièces, selon la manière dont vous formulez la question pour déterminer la possibilité d'obtenir une combinaison particulière de têtes et de queues, telle que HHTHTTTH. Vous aurez 1 chance sur 256 d'obtenir cette séquence exacte de lancers de pièces pour les 8 lancers de pièces exécutés à chaque fois.
Ahemone
Toutes ces informations sont à inclure dans la réponse elle-même. Mon commentaire ne conteste pas ce que vous avez dit, à savoir l'omission d'une adresse directe de la source de confusion d'OP: la relation entre bits et jetons.
Sycorax dit: Réintégrer Monica le
Je devrais également dire que, pour obtenir la valeur attendue de 4 du PO, ils essaient de trouver la probabilité de n nombreux 1 ou de n nombreux 0 dans un octet donné. Cette formulation de la question donnerait la distribution binomiale qu’ils attendaient dans leur esprit plutôt que la distribution uniforme de trouver la probabilité d’obtenir une certaine valeur à partir de ces bits aléatoires.
Ahemone