Why is generating 8 random bits uniform on (0, 255)?

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:

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

2. The event "E1: the sequence had four zeroes" is more probable than the event "E2: the sequence had eight zeroes".

These propositions are not contradictory; indeed, they are both true. Because the event E1 includes more sequences.

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.

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.

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.

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.

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.

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.

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.

The problem, restated, is: Why is the number of combinations of 8 binary digits taken in a range of 1 to 8 objects at a time different from the number of permutations of 8 binary digits.

The answer is: Those are two different encodings. To encode the numbers so that each sequence is unique we 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.

When the lossless encoding is abandoned (mentally, mind you), we then have a lossy encoding in which outcomes (and information) is combined. We are then viewing the number series as $\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.