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.)


1 Answer 1


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.

  • $\begingroup$ No! My definition is normality, which is simple normality in bases b, b^2, b^3, .... $\endgroup$
    – Charles
    Commented Feb 3, 2011 at 19:59
  • $\begingroup$ But thanks for answering my question. :) $\endgroup$
    – Charles
    Commented Feb 3, 2011 at 20:00
  • $\begingroup$ @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. $\endgroup$
    – mjqxxxx
    Commented Feb 3, 2011 at 20:29
  • $\begingroup$ 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! $\endgroup$
    – Charles
    Commented Feb 4, 2011 at 0:42
  • $\begingroup$ And that was with p = 0.001 -- if I actually allowed a reasonable amount of error it would perform even better. $\endgroup$
    – Charles
    Commented Feb 6, 2011 at 3:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .