11
$\begingroup$

Assume a data file with 80+ million ones and zeros, randomly generated.

From this file, we want to create a list of random decimal integers.

This is the plan to do this conversion.

  1. Divide the 80 million digits into groupings of 4 binary digits.
  2. Convert each 4-digit binary to decimal.
  3. Discard all decimal values greater than 9.

This should result in a string of random integers from 0-9

Here is the concern. The 24 binary digits that comprise the 6 groupings of 4 binary digits that correspond to the values 10 to 15 contain 17 ones and only 7 zeros. Will this imbalance affect the distribution of even vs. odd integers, or compromise randomness of the final string of decimal digits in any way?

Update: From the answers posted, it seems the method enumerated above is sound. I agree with that conclusion. However, I still do not understand why removing more than twice as many ones as zeros from the binary string does not bias the outcome toward fewer odd numbers. I seek explanations.

Improve this question
$\endgroup$
1
  • 9
    $\begingroup$ There are more efficient methods. For instance, you could partition the bit string into groups of 10, convert them to their three-digit representations base 10, and discard any with values 1000 or greater. This would utilize 97.6% of the bits rather than just 62.5% of them. You can't do much better than that. (You could use groups of 681 and convert them to 205-digit base-10 strings, thereby utilizing almost 99.7% of the bits.) $\endgroup$
    – whuber ♦
    Jan 12, 2018 at 20:03

2 Answers 2

Reset to default
19
$\begingroup$

Let's count and see. By construction of the file, all 4-bit strings are equally likely. There are 16 such strings. Here they are:

 0. 0000
 1. 0001
 2. 0010
 3. 0011
 4. 0100
 5. 0101
 6. 0110
 7. 0111
 8. 1000
 9. 1001
10. 1010
11. 1011
12. 1100
13. 1101
14. 1110
15. 1111

Your procedure throws out strings 10 through 15. So in the cases that you actually use, you'll be choosing 0 through 9, each of which is equally likely, as desired. And we know the generated decimal digits are independent of each other because each uses a separate string of 4 bits and all the bits are independent. Your procedure constitutes a simple kind of rejection sampling.

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ I see that logic clearly. Yet I am concerned that I am discarding more binary 1's than 0's. Why does that imbalance not have any impact? $\endgroup$
    – Joel W.
    Jan 12, 2018 at 19:13
  • 5
    $\begingroup$ @JoelW I guess I don't see your argument. The final distribution concerns decimal digits, not bits, so the distribution of bits is irrelevant. $\endgroup$
    – Kodiologist
    Jan 12, 2018 at 19:53
  • 7
    $\begingroup$ This is correct, but it only partially addresses the question. To address the "compromise randomness ... in any way" part of the question, one also has to establish that the resulting decimal digits are, to an excellent approximation, independent. For completeness' sake, it's worth devoting one sentence of explanation to that (obvious) result. $\endgroup$
    – whuber ♦
    Jan 12, 2018 at 21:04
  • 7
    $\begingroup$ Joel, I see where you're coming from. There may be a misperception here: you cannot reverse the process. If you wanted to reconstruct a stream of bits from the stream of decimal digits, you would have to do something like delete all 8's and 9's and convert the remaining digits into binary triples. That will restore the balance. In fact, it's easy to see that this "round trip" amounts to breaking your original stream into four-bit nybbles and discarding their most significant bits, leaving a nice uniformly distributed sequence of 60 million bits. $\endgroup$
    – whuber ♦
    Jan 12, 2018 at 21:09
  • 1
    $\begingroup$ @whuber Fair enough; added. $\endgroup$
    – Kodiologist
    Jan 12, 2018 at 21:22
4
$\begingroup$

There is no bias since you just simulate some values that are discarded and all values including those that are kept are generated with the same probability: enter image description here

The R code for the above graph is

generza=matrix(sample(0:1,4*1e6,rep=TRUE),ncol=4)
uniz=generza[,1]+2*generza[,2]+4*generza[,3]+8*generza[,4]
barplot(hist(uniz[uniz<10],breaks=seq(-0.5,9.5,le=11))$counts,col="steelblue")
Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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