2
$\begingroup$

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 Answers 1

3

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.

  • 0
    And that was with p = 0.001 -- if I actually allowed a reasonable amount of error it would perform even better.2011-02-06