This ties back to a SO question, where someone wanted to increase performance of an algorithm, and part of the solution was "test the most likely situation first". The question involved checking for the presence of one or more of a particular subset of base-10 digits, and so the answer involved first testing that each digit wasn't in the subset, because that was more likely.

This got me thinking. In the infinite set of all natural base-10 numbers, is any single digit more prevalent than any other? And a corollary: is the answer to that question different for a different number base (such as binary, octal, or hexadecimal)?

The common-sense answer to both questions would be "no". However, a simple exercise in binary numbers would demonstrate that the digit 1 is more common than the digit 0 in the significand of a fixed set of binary digits:

11 //maximum value of 2 bits; there have been 4 1s and 2 0s.
111 //maximum value of 3 bits; 12 1s and 6 0s have occurred.
1111 //maximum value of four bits; 32 1s and 18 0s have occurred.

I know enough about math to know the common-sense answer is often wrong; for instance, trans-infinite numbers defining differing cardinalities of "infinite" sets. There are also pseudo-rules that look like a sure thing until the problem space becomes large; you can already see just through four bits that, while 1 is more common than 0, 0 is occurring more often as the number of bits in the significand increases. So, I thought I'd ask and see if anyone else could prove or disprove it in the general case.

  • 3
    $\begingroup$ That depends on what you mean by "more." $\endgroup$ – Qiaochu Yuan Feb 23 '12 at 20:21
  • 8
    $\begingroup$ Sounds a little like Benford's Law. $\endgroup$ – draks ... Feb 23 '12 at 20:33
  • 2
    $\begingroup$ Your listing has hidden some $0$'s. For example, the byte $00001101$ would represent "thirteen." In your count, you eliminated these leading $0$'s. The lack of uniformity is entirely due to this sort of thing. In the same way, in the numbers $0$ to $9999$, there aren't "enough" $0$'s, but the rest of the digits are fine. $\endgroup$ – André Nicolas Feb 23 '12 at 20:41
  • 1
    $\begingroup$ But I state that I'm talking about the set of all natural numbers. Natural numbers are neither said nor written with leading zeroes, and so I structured the example in a similar way. $\endgroup$ – KeithS Feb 23 '12 at 20:47
  • 1
    $\begingroup$ Besides, if you DO count leading zeroes, then for any finite N binary digits there would be exactly N(N-1)/2 zeroes that are not part of the significand (the space in which 1 cannot occur by definition), and less than N(N-1)/2 ones in the significand (because zeroes also occur in the significand), which would prove that zero occurs more often than one. However, this is flawed; natural numbers are not stated in terms of a maximum possible order of magnitude; only the maximum significant order of magnitude for the specific number. $\endgroup$ – KeithS Feb 23 '12 at 20:53

If you order them, 0.1234567891011..., then this is Champernowne's constant, which is normal (a much stronger condition of uniformity) in base-10.

| cite | improve this answer | |
  • 1
    $\begingroup$ I think normality is actually less strong than the OP is talking about; it only says that all digit patterns occur with asymptotically equal frequency, but it's easily possible for this to happen while one digit always has more occurrences 'so far' than another. (Consider the string AABABAB...; then the asymptotic frequency of As and Bs is identical, but any initial substring always has more As than Bs.) $\endgroup$ – Steven Stadnicki Feb 23 '12 at 20:50
  • $\begingroup$ Except that we're considering the general case, in which there is no "so far". The article states it's proven that for base 10 in the general case, all digits occur with equal frequency, which is the answer to my question in base 10. Now the corollary is, will you get a different answer for any other base? The article says that is unknown (not proven at least). $\endgroup$ – KeithS Feb 23 '12 at 21:26
  • 2
    $\begingroup$ KeithS: there's always a 'so far' - none of these concepts considering the entire list of numbers at once; they're all limiting processes. The 'equal frequency' just says that the limit of ('# of As in the first n symbols'/n) is the same as the limit of ('# of Bs in the first n symbols'/n), but it's still possible to have this happen while '# of As in the first n symbols' is greater than '# of Bs in the first n symbols' for all n. It does come down to your definition of 'more prevalent', but there are multiple valid interpretations of that phrase. $\endgroup$ – Steven Stadnicki Feb 23 '12 at 22:34

For finite intervals you will have a lack of zeros as you have seen. If you go up to $b^n-1$ in base $b$ the rest of the digits will be even. The discrepancies get fractionally smaller as you go up. In the interval $[b^n,b^{n+1}-1]$ you will have $n(b^{n+1}-b^n)$ digits total. All but the leading digit will be equidistributed, giving $(n-1)(b^n-b^{n-1})$ of each. The leading digit will contribute an additional $(b^n-b^{n-1})$ of all the digits except $0$. The fractional excess is then $\frac 1{n-1}$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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