Take the tour ×

If it true that for every $b$-normal number (where the base $b,b^2,b^3,\ldots$ digits are asymptotically equiprobable) that the first differences of the base-$b$ digits, interpreted as a (signed) base-$b$ expansion, form a $b$-normal number?

It seems 'obviously' true but I wanted to check.

This is actually a practical question in disguise! I want to detect when a (short) string of digits is 'probably' a normal number or something else. Of course in pure theory there's no reason the first billion digits of a normal number wouldn't be 7, but in this application I'm just looking for a best guess. I found that there are many times that the digits themselves have roughly even distributions but the first differences are decidedly not well-distributed -- the numbers are in 'clumps', perhaps, with small first differences.

Generally speaking my thought is to apply some sort of chi-square test to the numbers and first differences, but I wanted to make sure the theory was sound first. (If so, the next step will be testing it on the decimal expansions of random constants to see how well it works.)

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

The first differences of a normal sequence will be asymptotically equiprobable if they are computed modulo $b$. This follows from the fact that each pair of digits is equiprobable and there are exactly $b$ pairs $(x, (x+y)\text{ mod }b)$ that give rise to each first difference $y$. Similarly, the sequence of first differences modulo $b$ of a normal sequence must contain every $n$-digit string with asymptotic density $b^{-n}$, because the normal sequence contained every $(n+1)$-digit string with density $b^{-(n+1)}$.

We conclude that, for any sequence $S$ of digits in base $b$, the sequence $\Delta S\text{ mod }b$ is normal if $S$ is normal; but we cannot conclude that $\Delta S\text{ mod }b$ is simply normal just because $S$ is simply normal.

share|improve this answer
No! My definition is normality, which is simple normality in bases b, b^2, b^3, .... –  Charles Feb 3 '11 at 19:59
But thanks for answering my question. :) –  Charles Feb 3 '11 at 20:00
@Charles: Sorry, I read your question incorrectly... I thought that by "base b, b^2, b^3" digits you meant the first, second, third, ..., digits of the original sequence. But you're right, of course. –  mjqxxxx Feb 3 '11 at 20:29
OK, so I just implemented my first-difference chi^2 testing program. It is so good... it immediately cut out 65%+ of the junk, above and beyond what the earlier heuristics had removed. Thanks a lot! –  Charles Feb 4 '11 at 0:42
And that was with p = 0.001 -- if I actually allowed a reasonable amount of error it would perform even better. –  Charles Feb 6 '11 at 3:21
add comment

Your Answer


