Warum werden auf (0, 255) 8 zufällige Bits gleichmäßig erzeugt?

35

Ich generiere 8 zufällige Bits (entweder eine 0 oder eine 1) und verkette sie zu einer 8-Bit-Zahl. Eine einfache Python-Simulation ergibt eine gleichmäßige Verteilung auf der diskreten Menge [0, 255].

Ich versuche zu rechtfertigen, warum das in meinem Kopf Sinn macht. Wenn ich das mit dem Umwerfen von 8 Münzen vergleiche, würde der erwartete Wert nicht bei 4 Kopf / 4 Zahl liegen? Für mich ist es also sinnvoll, dass meine Ergebnisse eine Spitze in der Mitte des Bereichs widerspiegeln. Mit anderen Worten, warum scheint eine Folge von 8 Nullen oder 8 Einsen genauso wahrscheinlich zu sein wie eine Folge von 4 und 4 oder 5 und 3 usw.? Was vermisse ich hier?

glasig
quelle
17
Der erwartete Wert der Verteilung der Bits in einem gleichmäßigen zufälligen Bereich [0,255] liegt ebenfalls irgendwo bei 4 1/4 0.
user253751
2
Nur weil Sie jeder Zahl von 0 bis 255 die gleiche Gewichtung geben, bedeutet dies nicht, dass das Funktionsergebnis "Differenz zwischen der Zählung von 1 und 0" auch einmal und nur einmal auftritt. Ich könnte jeder Person in meiner Organisation das gleiche Gewicht geben. Bedeutet nicht, dass ihr Alter gleich gewichtet wäre. Einige Altersgruppen sind möglicherweise viel häufiger als andere. Aber eine Person ist nicht häufiger als jede andere Person.
Brad Thomas
2
Stellen Sie es sich so vor ... Ihr erstes Zufallsbit bestimmt den Wert von Bit 7, eine 1 ist 128 und eine 0 ist 0. Von 256 Zahlen haben Sie eine 50% ige Chance, dass die Zahl 0-127 ist, wenn die Bit ist 0 und 128-255, wenn das Bit 1 ist. Sagen wir, es ist 0, dann bestimmt das nächste Bit, ob das Ergebnis 0-63 oder 64-127 ist. Alle 8 Bits sind erforderlich, um eines von 256 gleich wahrscheinlichen Ergebnissen zu bilden. Sie denken darüber nach, Summen hinzuzufügen, wie Sie es mit Würfeln tun würden. Die Wahrscheinlichkeit, 4 1s und 4 0s zu erhalten, ist höher als die Wahrscheinlichkeit, 8 1s zu erhalten, aber es gibt mehr Möglichkeiten, wie sie angeordnet werden können, um ein anderes Ergebnis zu erzielen.
Jason Goemaat
2
Angenommen, Sie würfeln mit einem fairen 256-seitigen Würfel, der mit den Zahlen 0 bis 255 gekennzeichnet ist. Sie würden eine gleichmäßige Verteilung erwarten. Angenommen, Sie beschriften den Würfel neu, sodass auf einer Seite 0, 8 Seiten 1, 28 Seiten 2 und so weiter stehen. Jede Seite ist jetzt mit der Anzahl der Ein-Bits in der Anzahl beschriftet, die sich früher auf dieser Seite befand. Sie würfeln noch einmal; warum würden Sie eine gleichmäßige Verteilung der Zahlen von 0 bis 8 erwarten?
Eric Lippert
Wenn die Verteilung so funktionieren würde, könnte ich eine Menge Geld verdienen, wenn ich auf Roulette setze, nachdem 7 Rottöne hintereinander aufgetaucht sind. 7 und 1 sind 8-mal wahrscheinlicher als 8 und 0! (Ohne Berücksichtigung der Nullen, aber dieser Versatz überwiegt bei weitem den Versatz von 0 und 00)
Cruncher

Antworten:

61

TL; DR: Der scharfe Kontrast zwischen den Bits und Münzen besteht darin, dass Sie bei den Münzen die Reihenfolge der Ergebnisse ignorieren . HHHHTTTT wird wie TTTTHHHH behandelt (beide haben 4 Köpfe und 4 Schwänze). Aber in Bits ist Ihnen die Reihenfolge wichtig (weil Sie den Bitpositionen "Gewichte" geben müssen, um 256 Ergebnisse zu erhalten), daher unterscheidet sich 11110000 von 00001111.


Längere Erklärung: Diese Konzepte lassen sich präziser vereinheitlichen, wenn wir das Problem etwas formeller formulieren. Betrachten Sie ein Experiment als eine Folge von acht Versuchen mit dichotomen Ergebnissen und einer Wahrscheinlichkeit von "Erfolg" 0,5 und "Misserfolg" 0,5, und die Versuche sind unabhängig. Im Allgemeinen nenne ich das Erfolge, n Gesamtversuche und n - k Misserfolge und die Erfolgswahrscheinlichkeit ist p .knnkp

  • Im Münzbeispiel ignoriert das Ergebnis " Köpfe, n - k Schwänze" die Reihenfolge der Versuche (4 Köpfe sind 4 Köpfe, unabhängig von der Reihenfolge des Auftretens), und dies führt zu Ihrer Beobachtung, dass 4 Köpfe wahrscheinlicher sind als 0 oder 8 Köpfe. Vier Köpfe sind üblicher, weil es viele Möglichkeiten gibt, vier Köpfe (THTHTHTHH oder THTHTHHTT usw.) herzustellen, als es eine andere Zahl gibt (8 Köpfe haben nur eine Sequenz). Der Binomialsatz gibt die Anzahl der Möglichkeiten an, diese verschiedenen Konfigurationen vorzunehmen.knk

  • Im Gegensatz dazu ist die Reihenfolge für Bits wichtig, da jeder Stelle ein "Gewicht" oder ein "Stellenwert" zugeordnet ist. Eine Eigenschaft des Binomialkoeffizienten ist, dass , das heißt, wenn wir alle verschiedenen geordneten Folgen hochzählen, erhalten wir28=256. Dies verbindet direkt die Idee, wie viele verschiedene Arten es gibt,kKöpfe innBinomialversuchen zu erzeugen, mit der Anzahl verschiedener Bytesequenzen.2n=k=0n(nk)28=256kn

  • Darüber hinaus können wir zeigen, dass die 256 Ergebnisse durch die Eigenschaft der Unabhängigkeit gleichermaßen wahrscheinlich sind. Frühere Versuche haben keinen Einfluss auf den nächsten Versuch, daher beträgt die Wahrscheinlichkeit einer bestimmten Reihenfolge im Allgemeinen (da die gemeinsame Wahrscheinlichkeit unabhängiger Ereignisse das Produkt ihrer Wahrscheinlichkeiten ist). Da die Versuche fair sind, P ( Erfolg ) = P ( Misserfolg ) = p = 0,5 , reduziert sich dieser Ausdruck auf P ( beliebige Reihenfolge ) = 0,5 = 8pk(1-p)n-kP(Erfolg)=P(Scheitern)=p=0,5 . Da alle Ordnungen die gleiche Wahrscheinlichkeit haben, haben wir eine gleichmäßige Verteilung über diese Ergebnisse (die durch binäre Codierung als ganze Zahlen in[0,255] dargestellt werden können).P(jede Bestellung)=0,58=1256[0,255]

  • Schließlich können wir diesen Kreis wieder auf den Münzwurf und die Binomialverteilung zurückführen. Wir wissen, dass das Auftreten von 0 Köpfen nicht die gleiche Wahrscheinlichkeit hat wie 4 Köpfe. Dies liegt daran, dass es verschiedene Möglichkeiten gibt, das Auftreten von 4 Köpfen zu ordnen, und dass die Anzahl solcher Ordnungen durch den Binomialsatz gegeben ist. So muss irgendwie gewichtet werden, und zwar durch den binomischen Koeffizienten gewichtet werden müssen. Dies gibt uns die PMF der Binomialverteilung, P ( k  Erfolge ) = ( nP(4 Köpfe). Es mag überraschendass dieser Ausdruck eine PMF ist,zwarweil es nicht sofort offensichtlich istdass es auf 1 fasstum zu überprüfen, haben wir zu überprüfendassΣ n k = 0 ( nP(k Erfolge)=(nk)pk(1-p)n-k, dies ist jedoch nur ein Problem der Binomialkoeffizienten:1=1n=(p+1-p)n= n k = 0 ( nk=0n(nk)pk(1p)nk=1.1=1n=(p+1p)n=k=0n(nk)pk(1p)nk

Sycorax sagt Reinstate Monica
quelle
Das macht Sinn ... aber würden wir dann nicht erwarten, dass 15, 30, 60, 120 und 240 ein höheres Gewicht in der Verteilung haben als 0 oder 255?
glasigen
1
Ich glaube, ich verstehe es jetzt. Ich werde diese Antwort akzeptieren, weil ich denke, dass der Schlüssel hier die Reihenfolge ist, auf die Sie aufmerksam gemacht haben. Danke
glasig
Noch eine Anmerkung - um mein Münzbeispiel zu verwenden, das ist wirklich, 8 Münzen gleichzeitig zu werfen, im Gegensatz zu 8 Versuchen, eine Münze zu werfen. Darin lag meine Verwirrung.
glasigen
2
Das Konzept des "Platzwertes" aus der "Grundrechenart" ist hier besonders anwendbar; um eine dezimale Analogie zu verwenden, muss man ganz andere Zahlen betrachten 10001000und bezeichnen 10000001.
JM ist
17

Warum ist eine Folge von 8 Nullen oder 8 Einsen genauso wahrscheinlich wie eine Folge von 4 und 4 oder 5 und 3 usw

Das übergeordnete Paradoxon kann in zwei Aussagen zusammengefasst werden, die widersprüchlich erscheinen könnten:

  1. Die Folge (acht Nullen) ist ebenso wahrscheinlich wie die Folge s 2 : 01010101 (vier Nullen, vier Einsen). (Im Allgemeinen: Alle 2 8 Sequenzen haben die gleiche Wahrscheinlichkeit, unabhängig davon, wie viele Nullen / Einsen sie haben.)s1:00000000s2:0101010128

  2. Das Ereignis " : Die Sequenz hatte vier Nullen " ist wahrscheinlicher (tatsächlich 70- mal wahrscheinlicher) als das Ereignis " e 2 : Die Sequenz hatte acht Nullen ".e170e2

Diese Aussagen sind beide wahr. Weil das Ereignis viele Sequenzen enthält.e1

Leonbloy
quelle
8

Alle Sequenzen haben die gleiche Wahrscheinlichkeit 1/2 8 = 1/256. Es ist falsch anzunehmen, dass die Folgen, die näher an einer gleichen Anzahl von Nullen und Einsen liegen, wahrscheinlicher sind, wenn die Frage interpretiert wird. Es sollte klar sein, dass wir bei 1/256 ankommen, weil wir die Unabhängigkeit von Versuch zu Versuch annehmen . Deshalb multiplizieren wir die Wahrscheinlichkeiten und das Ergebnis eines Versuchs hat keinen Einfluss auf den nächsten.2828

Michael R. Chernick
quelle
2
Dies wäre eine gute, wenn auch kurze Antwort ... wenn die Frage nicht das Wort "Warum" enthielte. So wie es ist, wiederholen Sie einfach eine der Aussagen in der Frage, ohne dass eine Erklärung gegeben wird.
Tin Man
1
Eigentlich ... Diese Antwort ist sachlich falsch, siehe Leonbloys Antwort für das Warum.
Tin Man
3
@Walt es ist nicht falsch. Subtilität der Sprache. Eine gegebene Sequenz ist nicht wahrscheinlicher, da sie ein geringeres Ungleichgewicht zwischen 0 und 1 aufweist. Es gibt einfach mehr solche Sequenzen .
Hobbs
4
Ist jemand mit mir einverstanden? Wenn a 0 hat Wahrscheinlichkeit 1/2 und 1 hat Wahrscheinlichkeit 1/2 und ein Term in der Folge unabhängig von dem nächsten die Wahrscheinlichkeit einer gegebenen Sequenz mit einer Länge von 8 Wahrscheinlichkeit hat . und so auch jede andere Sequenz von 8.1/28=1/256
Michael R. Chernick
4
@Michael I fully agree and am pleased to see--at last!--an explicit appeal to the very heart of the matter: independence. I would be happy to upvote your answer if you would include that comment in it.
whuber
7

EXAMPLE with 3 bits (often an example is more illustrative)

I will write the natural numbers 0 through 7 as:

  • A number in base 10
  • A number in base 2 (i.e. a sequence of bits)
  • A series of coin flips implied by the base 2 representation (1 denotes a flip of heads and 0 denotes a flip of tails).

Base 10Base 2 (with 3 bits)Implied Coin Flip SeriesHeadsTails0000TTT031001TTH122010THT123011THH214100HTT125101HTH216110HHT217111HHH30

Choosing a natural number from 0 through 7 with equal probability is equivalent to choosing one of the coin flip series on the right with equal probability.

Hence if you choose a number from the uniform distribution over integers 0-7, you have a 18 chance of choosing 3 heads, 38 chance of choosing 2 heads, 38 chance of choosing 1 head, and 18 chance of choosing 0 heads.

Matthew Gunn
quelle
3

Sycorax's answer is correct, but it seems like you're not entirely clear on why. When you flip 8 coins or generate 8 random bits taking order into account, your result will be one of 256 equally likely possibilities. In your case, each of these 256 possible outcomes uniquely map to an integer, so you get a uniform distribution as your result.

If you don't take order into account, such as considering just how many heads or tails you got, there are only 9 possible outcomes (0 Heads/8 Tails - 8 Heads/0 Tails), and they're no longer equally likely. The reason for this is because out of the 256 possible results, there are 1 combination of flips that gives you 8 Heads/0 Tails (HHHHHHHH) and 8 combinations that give 7 Heads/1 Tails (a Tails in each of the 8 positions in the order), but 8C4 = 70 ways to have 4 Heads and 4 Tails. In the coin flipping case each of those 70 combinations maps to 4 Heads/4 Tails, but in the binary number problem each of those 70 outcomes maps to a unique integer.

Blacksteel
quelle
2

The problem, restated, is: Why is the number of combinations of 8 random binary digits taken as 0 to 8 selected digits (e.g., the 1's) at a time different from the number of permutations of 8 random binary digits. In the context herein, random choice of 0's and 1's means that each digit is independent of any other, so that digits are uncorrelated and p(0)=p(1)=12; .

The answer is: There are two different encodings; 1) lossless encoding of permutations and 2) lossy encoding of combinations.

Ad 1) To lossless encode the numbers so that each sequence is unique we can view that number as being a binary integer i=182i1Xi, where Xi are the left to right ith digits in the binary sequence of random 0's and 1's. What that does is make each permutation unique, as each random digit is then positional encoded. And the total number of permutations is then 28=256. Then, coincidentally one can translate those binary digits into the base 10 numbers 0 to 255 without loss of uniqueness, or for that matter one can rewrite that number using any other lossless encoding (e.g. lossless compressed data, Hex, Octal). The question itself, however, is a binary one. Each permutation is then equally probable because there is then only one way each unique encoding sequence can be created, and we have assumed that the appearance of a 1 or a 0 is equally likely anywhere within that string, such that each permutation is equally probable.

Ad 2) When the lossless encoding is abandoned by only considering combinations, we then have a lossy encoding in which outcomes are combined and information is lost. We are then viewing the number series, w.l.o.g. as the number of 1's; i=1820Xi, which in turn reduces to C(8,i=18Xi), the number of combinations of 8 objects taken i=18Xi at at time, and for that different problem, the probability of exactly 4 1's is 70 (C(8,4)) times greater than obtaining 8 1's, because there are 70, equally likely permutations that can produce 4 1's.

Note: At the current time, the above answer is the only one containing an explicit computational comparison of the two encodings, and the only answer that even mentions the concept of encoding. It took a while to get it right, which is why this answer has been downvoted, historically. If there are any outstanding complaints, leave a comment.

Update: Since the last update, I am gratified to see that the concept of encoding has begun to catch on in the other answers. To show this explicitly for the current problem I have attached the number of permutations that are lossy encoded in each combination.enter image description here

Note that the number of bytes of information lost during each combinatorial encoding is equivalent to the number of permutations for that combination minus one [C(8,n)1, where n is the number of 1's], i.e., for this problem, from 0 to 69 per combination, or 2569=247 overall.

Carl
quelle
2
Using the conventional way to name numbers--by omitting all reference to preceding zeros--potentially confuses this explanation. Don't you think the situation would become much clearer by writing 0 as 00000000, 1 (which you inadvertently omitted) as 00000001, and so on?
whuber
16
Frankly this is all correct as far as it goes but it doesn't address the question. You've done a fine job of showing how eight ordered bits can represent numbers in the range, but haven't explained why selecting those bits at random give a uniform distribution (something which is, admittedly, so simple that explaining it clearly takes some subtlety).
dmckee
9
Wouldn't it be simpler to say that 8 (independently) random bits is uniformly distributed on [00000000, 11111111] for the same reason that 3 random digits is uniformly distributed on [000, 999]? The side rant about how/why computers use binary and the fractional bases is totally unnecessary and unrelated. I mean, the fact that binary uses only the symbols 0 and 1 is just an inherent property of base 2... no need to explain that. If you wanted to keep that kind of explanation in there, it would probably be more useful to explain how bases work in general, but it would still be beside the point.
Blackhawk
3
I am glad to see how much this answer has improved. However, I have difficulty seeing what base-10 representations have to do with this question (wouldn't base-3 or base-17 work just as well?) and I cannot see what might be special about 8 bits that doesn't also generalize to any finite number of bits. That suggests that most of the considerations in this answer are tangential or irrelevant.
whuber
3
And I wish to thank you for that felicitous characterization of the confusion expressed in the question: "lossy" and "lossless" encoding. It's memorable, slightly different than other perspectives, insightful, and potentially could clear up that confusion quickly.
whuber
1

I'd like to expand a little bit on the idea of order dependence vs. independence.

In the problem of calculating the expected number of heads from flipping 8 coins, we're summing the values from 8 identical distributions, each of which is the Bernoulli distribution [; B(1, 0.5) ;] (in other words, a 50% chance of 0, a 50% chance of 1). The distribution of the sum is the binomial distribution [; B(8, 0.5) ;], which has the familiar hump shape with most of the probability centered around 4.

In the problem of calculating the expected value of a byte made of 8 random bits, each bit has a different value that it contributes to the byte, so we're summing the values from 8 different distributions. The first is [; B(1, 0.5) ;], the second is [; 2 B(1, 0.5) ;], the third is [; 4 B(1, 0.5) ;] , so on up to the eighth which is [; 128 B(1, 0.5) ;]. The distribution of this sum is understandably quite different from the first one.

If you wanted to prove that this latter distribution is uniform, I think you could do it inductively — the distribution of the lowest bit is uniform with a range of 1 by assumption, so you would want to show that if the distribution of the lowest [; n ;] bits is uniform with a range of [; 2^n - 1} ;] then the addition of the [; n+1 ;]st bit makes the distribution of the lowest [; n + 1 ;] bits uniform with a range of [; 2^{n+1} - 1 ;], achieving a proof for all positive [; n ;]. But the intuitive way is probably the exact opposite. If you start at the high bit, and choose values one at a time down to the low bit, each bit divides the space of possible outcomes exactly in half, and each half is chosen with equal probability, so by the time you get to the bottom, each individual value must have had the same probability to be chosen.

hobbs
quelle
It is not a continuous uniform. The bit is either 0 or 1 and nothing in between.
Michael R. Chernick
@MichaelChernick of course we're only dealing with discrete distributions here.
hobbs
The OP said that the bits are only 1 or 0 and nothing in between.
Michael R. Chernick
1
@MichaelChernick correct.
hobbs
1

If you do a binary search comparing each bit, then you need the same number of steps for each 8 bit number, from 0000 0000 to 1111 1111, they both have the length 8 bit. At each step in the binary search both sides have a 50/50 chance of occuring, so in the end, because every number has the same depth and the same probabilities, without any real choice, each number must have the same weight. Thus the distribution must be uniform, even when each individual bit is determined by coin flips.

However, the digitsum of the numbers isn't uniform and would be equal in distribution to tossing 8 coins.

HopefullyHelpful
quelle
1

There is only one sequence with eight zeros. There are seventy sequences with four zeros and four ones.

Therefore, while 0 has a probability of 0.39%, and 15 [00001111] also has a probability of 0.39%, and 23 [00010111] has a probability of 0.39%, etc., if you add up all seventy of the 0.39% probabilities you get 27.3%, which is the probability of having four ones. The probability of each individual four-and-four result does not have to be any higher than 0.39% for this to work.

Random832
quelle
This doesn't change the fact that all 256 sequences are equally probable.
Michael R. Chernick
@MichaelChernick I didn't say it did, I explicitly said that they all have a probability of 0.39%, I'm addressing OP's assumptions.
Random832
You are right. It is another way of saying what I said in my answer. Some of the other answers are wrong.
Michael R. Chernick
1

Consider dice

Think about rolling a couple of dice, a common example of non-uniform distribution. For the sake of the math, imagine the dice are numbered from 0 to 5 instead of the traditional 1 to 6. The reason the distribution is not uniform is that you are looking at the sum of the dice rolls, where multiple combinations can yield the same total like {5, 0}, {0, 5}, {4, 1}, etc. all generating 5.

However, if you were to interpret the dice roll as a 2 digit random number in base 6, each possible combination of dice is unique. {5, 0} would be 50 (base 6) which would be 5*(61) + 0*(60) = 30 (base 10). {0, 5} would be 5 (base 6) which would be 5*(60) = 5 (base 10). So you can see, there is a 1 to 1 mapping of possible dice rolls interpreted as numbers in base 6 versus a many to 1 mapping for the sum of the two dice each roll.

As both @Sycorax and @Blacksteel point out, this difference really boils down to the question of order.

Blackhawk
quelle
0

Each bit you choose is independent from each other bit. If you consider for the first bit there is a

  • 50% probability it will be 1

and

  • 50% probability it will be 0.

This also applies to the second bit, third bit and so on so that you end up with so for each possible combination of bits to make your byte you have (12)8 = 1256 chance of that unique 8 bit integer occurring.

Ahemone
quelle
All of these statements are true, but this doesn't address why coin tosses, which are also fair and independent, have only 9 distinct outcomes when an outcome is defined as the number of heads and tails.
Sycorax says Reinstate Monica
That is only a result of placing the results into an ordered system after choosing them. The same distribution would be achieved even if the random bits were placed into random positions on the byte. You also will get the same distribution on coin tosses by the way you frame the question to finding the chance of getting a particular combination of heads and tails, such as HHTHTTTH. You will have a 1/256 chance of getting that exact sequence of coin tosses for the 8 coin tosses being performed each time.
Ahemone
This is all good information to include in the answer itself. My comment doesn't take issue with what you've said so much as the omission of a direct address of OP's source of confusion: the relationship between bits and coin flips.
Sycorax says Reinstate Monica
I should also say in order to get to the OP's expected value of 4 they are trying to find the probability of n many 1's or n many 0's in a given byte. This framing of the question would give the binomial distribution they were expecting in their mind rather than the uniform distribution of finding the probability of obtaining a certain value from those random bits.
Ahemone