# Can it be proven (or disproven) that a particular digit is more prevalent than another digit in the set of all natural numbers?

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:

0
1
10
11 //maximum value of 2 bits; there have been 4 1s and 2 0s.
100
101
110
111 //maximum value of 3 bits; 12 1s and 6 0s have occurred.
1000
1001
1010
1011
1100
1101
1110
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.

• That depends on what you mean by "more." – Qiaochu Yuan Feb 23 '12 at 20:21
• Sounds a little like Benford's Law. – draks ... Feb 23 '12 at 20:33
• 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. – André Nicolas Feb 23 '12 at 20:41
• 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. – KeithS Feb 23 '12 at 20:47
• 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. – KeithS Feb 23 '12 at 20:53

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}$