Random Blog

From Ick Wiki
Jump to: navigation, search

The idea here would be blog posts of true random numbers generated manually in different ways. For example, the first post would be flipping a quarter 100 times. The next post might be rolling a six sided die 100 times. Maybe I would roll the die more times. I would want a good sample size, as I would also be adding some basic statistics on the results. The more possible results, the higher the sample size would have to be.

In addition, I would provide a binary version of the random numbers. This is where it gets a little tricky. Take the example of a four sided die. The binary representations of the numbers 1 through 4 are:

1 001
2 010
3 011
4 100

Note that there is only one number where the most significant binary digit is 1. Therefore, the digits in the binary representation will be biased towards zero. Worse, every third digit will be biased towards zero. If we assume that the original values from the four sided die are truly random, then the results will be identically and independently distributed (IID). This is an important statistical feature. However, the digits in the binary representation will not be IID. How do we fix this?

First, we zero index the results. That is, we adjust them so that the lowest value is zero. In the four sided die example we would subtract one from each value before converting to binary:

1 00
2 01
3 10
4 11

Now we don't need a third digit, and the other digits remain evenly distributed. But then we run into problems with the six sided die:

1 000
2 001
3 010
4 011
5 100
6 101

Now there's an uneven distribution for both the most and second-most significant digit. The method I came up with to solve this problem is to treat the 1 to 4 values differently than the 5 and 6 values. The 1 to 4 values we convert to two binary digits, the 5 and 6 values we convert to one binary digit:

1 00
2 01
3 10
4 11
5 0
6 1

Now every binary digit will have an even distribution, and they will be IID (if the original values are IID). In general, if n is the highest power of two in the results, you convert the 1 to n values to n digit binary numbers, and subtract n from the values greater than n before converting. You may have to iterate this process. Say your values are 1 to 14. 1 to 8 would be converted to three binary digits, 9 to 12 would be converted to two binary digits after subtracting 8, and 13 and 14 would be converted to one binary digit after subtracting 12.

The last wrinkle comes with an odd number of values, such as with a seven sided die. What do you do with the 7 results? If you subtract 6, it's always 0. That may be an even distribution, but it is not identical to the distribution of the other digits. My solution is to convert a 7 to a 0 if there have been an even number of results since the last 7, and to a 1 otherwise. I believe that retains the IID property.