35
$\begingroup$

I am generating 8 random bits (either a 0 or a 1) and concatenating them together to form an 8-bit number. A simple Python simulation yields a uniform distribution on the discrete set [0, 255].

I am trying to justify why this makes sense in my head. If I compare this to flipping 8 coins, wouldn't the expected value be somewhere around 4 heads/4 tails? So to me, it makes sense that my results should reflect a spike in the middle of the range. In other words, why does a sequence of 8 zeroes or 8 ones seem to be equally as likely as a sequence of 4 and 4, or 5 and 3, etc.? What am I missing here?

$\endgroup$
  • 17
    $\begingroup$ The expected value of the distribution of bits in a uniform random the range [0,255] is also somewhere around 4 1's/4 0's. $\endgroup$ – user253751 Jan 17 '17 at 0:58
  • 2
    $\begingroup$ Just because you give an equal weight to each number 0 through 255, doesn't mean the function result "difference between count of 1s and 0s" will also occur once and only once. I could give an equal weight to every person in my organization. Doesn't mean the their ages would be equally weighted. Some ages might be much more common than others. But one person is not more common than any other person. $\endgroup$ – Brad Thomas Jan 17 '17 at 16:55
  • 2
    $\begingroup$ Think of it this way... Your first random bit will determine the value of bit 7, a 1 is worth 128 and a 0 worth 0. Out of 256 numbers you have a 50% chance of the number being 0-127 if the bit is 0 and 128-255 if the bit is 1. Let's say it's 0, then the next bit determines if the result will be 0-63 or 64-127. All 8 bits are required to form one of 256 equally likely outcomes. You're thinking of adding totals like you would with dice. The odds of getting 4 1s and 4 0s is higher than getting 8 1s, but there are more ways they can be arranged to give you a different result. $\endgroup$ – Jason Goemaat Jan 18 '17 at 7:17
  • 2
    $\begingroup$ Suppose you roll a fair 256-sided die labeled with the numbers 0 to 255. You'd expect a uniform distribution. Now suppose you relabel the die so that one side says 0, 8 sides say 1, 28 sides say 2, and so on; each side is now labeled with the number of on bits in the number that used to be on that side. You roll the die again; why would you expect to get a uniform distribution of the numbers from 0 to 8? $\endgroup$ – Eric Lippert Jan 18 '17 at 16:32
  • $\begingroup$ If the distribution worked like this, then I could make a lot of money betting on roulette only after 7 reds came up in a row. 7 and 1 is more 8 times more likely than 8 and 0! (ignoring 0's, but this skew far outweighs the 0, and 00 skew) $\endgroup$ – Cruncher Jan 19 '17 at 18:51

11 Answers 11

62
$\begingroup$

TL;DR: The sharp contrast between the bits and coins is that in the case of the coins, you're ignoring the order of the outcomes. HHHHTTTT is treated as the same as TTTTHHHH (both have 4 heads and 4 tails). But in bits, you care about the order (because you have to give "weights" to the bit positions in order to get 256 outcomes), so 11110000 is different from 00001111.


Longer explanation: These concepts can be more precisely unified if we are a bit more formal in framing the problem. Consider an experiment to be a sequence of eight trials with dichotomous outcomes and probability of a "success" 0.5, and a "failure" 0.5, and the trials are independent. In general, I'll call this $k$ successes, $n$ total trials and $n-k$ failures and the probability of success is $p$.

  • In the coin example, the outcome "$k$ heads, $n-k$ tails" ignores the ordering of the trials (4 heads is 4 heads no matter the order of occurrence), and this gives rise to your observation that 4 heads are more likely than 0 or 8 heads. Four heads are more common because there are many ways to make four heads (TTHHTTHH, or HHTTHHTT, etc.) than there are some other number (8 heads only has one sequence). The binomial theorem gives the number of ways to make these different configurations.

  • By contrast, the order is important to bits because each place has an associated "weight" or "place value." One property of the binomial coefficient is that $2^n=\sum_{k=0}^n\binom{n}{k}$, that is if we count up all the different ordered sequences, we get $2^8=256$. This directly connects the idea of how many different ways there are to make $k$ heads in $n$ binomial trials to the number of different byte sequences.

  • Additionally, we can show that the 256 outcomes are equally likely by the property of independence. Previous trials have no influence on the next trial, so the probability of a particular ordering is, in general, $p^k(1-p)^{n-k}$ (because joint probability of independent events is the product of their probabilities). Because the trials are fair, $P(\text{success})=P(\text{fail})=p=0.5$, this expression reduces to $P(\text{any ordering})=0.5^8=\frac{1}{256}$. Because all orderings have the same probability, we have a uniform distribution over these outcomes (which by binary encoding can be represented as integers in $[0,255]$).

  • Finally, we can take this full circle back to the coin toss and binomial distribution. We know the occurrence of 0 heads doesn't have the same probability as 4 heads, and that this is because there are different ways to order the occurrences of 4 heads, and that the number of such orderings are given by the binomial theorem. So $P(\text{4 heads})$ must be weighted somehow, specifically it must be weighted by the binomial coefficient. So this gives us the PMF of the binomial distribution, $P(k \text{ successes})=\binom{n}{k}p^k(1-p)^{n-k}$. It might be surprising that this expression is a PMF, specifically because it's not immediately obvious that it sums to 1. To verify, we have to check that $\sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}=1$, however this is just a problem of binomial coefficients: $1=1^n=(p+1-p)^n=\sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That makes sense... but then wouldn't we expect 15, 30, 60, 120 and 240 to have a higher weight in the distribution than 0 or 255? $\endgroup$ – glassy Jan 16 '17 at 19:41
  • 1
    $\begingroup$ I think I understand it now. I'm going to accept this answer because I think the key here is the order, which you called attention to. Thanks $\endgroup$ – glassy Jan 16 '17 at 19:47
  • $\begingroup$ One more note - to use my coin example, this is really flipping 8 coins at the same time as opposed to 8 trials of flipping a coin. Therein lied my confusion. $\endgroup$ – glassy Jan 16 '17 at 19:49
  • 2
    $\begingroup$ The concept of "place value" from "elementary grade arithmetic" is especially applicable here; to use a decimal analogy, one considers 10001000 and 10000001 to be quite different numbers. $\endgroup$ – J. M. is not a statistician Jan 17 '17 at 9:32
17
$\begingroup$

why does a sequence of 8 zeroes or 8 ones seem to be equally as likely as a sequence of 4 and 4, or 5 and 3, etc

The aparent paradox can be summarized in two propositions, that might seem contradictory:

  1. The sequence $s_1: 00000000$ (eight zeroes) is equally probable as sequence $s_2: 01010101$ (four zeroes, four ones). (In general: all $2^8$ sequences have the same probability, regardless of how many zeroes/ones they have.)

  2. The event "$e_1$: the sequence had four zeroes" is more probable (indeed, $70$ times more probable) than the event "$e_2$: the sequence had eight zeroes".

These propositions are both true. Because the event $e_1$ includes many sequences.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

All of the $2^8$ sequences have the same probability 1/$2^8$=1/256. It is a wrong to think that the sequences that have closer to an equal number of 0s and 1s is more likely as the question is interpreted.. It should be clear that we arrive at 1/256 because we assume independence from trial to trial. That is why we multiply the probabilities and the outcome of one trial has no influence on the next.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This would be an ok, if short, answer... if the question didn't include the word "why". As it is, you simply reiterate one of the givens in the question, with no explanation given. $\endgroup$ – Tin Wizard Jan 17 '17 at 0:19
  • 1
    $\begingroup$ Actually... This answer is factually wrong, see leonbloy's answer for why. $\endgroup$ – Tin Wizard Jan 17 '17 at 3:37
  • 3
    $\begingroup$ @Walt it's not incorrect. Subtlety of language. Any given sequence is not more likely because it has less imbalance between 0s and 1s. There are simply more such sequences. $\endgroup$ – hobbs Jan 17 '17 at 4:09
  • 4
    $\begingroup$ Does anybody agree with me? If a 0 has probability 1/2 and a 1 has probability 1/2 and one term in the sequence is independent of the next the probability of a given sequence of length 8 has probability $1/2^8 = 1/256$. and so does any other sequence of 8. $\endgroup$ – Michael R. Chernick Jan 17 '17 at 5:24
  • 4
    $\begingroup$ @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. $\endgroup$ – whuber Jan 17 '17 at 23:17
7
$\begingroup$

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).

$$\begin{array} &\text{Base 10} & \text{Base 2 (with 3 bits)} & \text{Implied Coin Flip Series} &\text{Heads} & \text{Tails}\\ 0 & 000 & TTT & 0 & 3 \\ 1 & 001 & TTH & 1 & 2\\ 2 & 010 & THT & 1 & 2\\ 3 & 011 & THH & 2 & 1\\ 4 & 100 & HTT & 1 & 2\\ 5 & 101 & HTH & 2 & 1\\ 6 & 110 & HHT & 2 & 1\\ 7 & 111 & HHH & 3 & 0 \end{array} $$

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 $\frac{1}{8}$ chance of choosing 3 heads, $\frac{3}{8}$ chance of choosing 2 heads, $\frac{3}{8}$ chance of choosing 1 head, and $\frac{1}{8}$ chance of choosing 0 heads.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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)=\frac{1}{2}$; .

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 $\sum_{i=1}^82^{i-1}{X_i}$, where ${X_i}$ are the left to right $i^{th}$ 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 $2^8=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; $\sum_{i=1}^82^{0}{X_i}$, which in turn reduces to $C(8,\sum_{i=1}^8{X_i})$, the number of combinations of 8 objects taken $\sum_{i=1}^8{X_i}$ 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 $256-9=247$ overall.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – whuber Jan 16 '17 at 21:15
  • 16
    $\begingroup$ 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). $\endgroup$ – dmckee --- ex-moderator kitten Jan 17 '17 at 3:42
  • 9
    $\begingroup$ 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. $\endgroup$ – Blackhawk Jan 17 '17 at 22:38
  • 3
    $\begingroup$ 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. $\endgroup$ – whuber Jan 18 '17 at 15:17
  • 3
    $\begingroup$ 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. $\endgroup$ – whuber Jan 18 '17 at 19:52
1
$\begingroup$

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 $(\frac{1}{2})^8$ = $\frac{1}{256}$ chance of that unique 8 bit integer occurring.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sycorax Jan 18 '17 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Ahemone Jan 18 '17 at 18:31
  • $\begingroup$ 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. $\endgroup$ – Sycorax Jan 18 '17 at 19:22
  • $\begingroup$ 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. $\endgroup$ – Ahemone Jan 18 '17 at 19:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This doesn't change the fact that all 256 sequences are equally probable. $\endgroup$ – Michael R. Chernick Jan 17 '17 at 18:38
  • $\begingroup$ @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. $\endgroup$ – Random832 Jan 17 '17 at 18:48
  • $\begingroup$ You are right. It is another way of saying what I said in my answer. Some of the other answers are wrong. $\endgroup$ – Michael R. Chernick Jan 17 '17 at 18:53
1
$\begingroup$

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*($6^1$) + 0*($6^0$) = 30 (base 10). {0, 5} would be 5 (base 6) which would be 5*($6^0$) = 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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is not a continuous uniform. The bit is either 0 or 1 and nothing in between. $\endgroup$ – Michael R. Chernick Jan 17 '17 at 5:54
  • $\begingroup$ @MichaelChernick of course we're only dealing with discrete distributions here. $\endgroup$ – hobbs Jan 17 '17 at 6:53
  • $\begingroup$ The OP said that the bits are only 1 or 0 and nothing in between. $\endgroup$ – Michael R. Chernick Jan 18 '17 at 1:41
  • 1
    $\begingroup$ @MichaelChernick correct. $\endgroup$ – hobbs Jan 18 '17 at 1:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.