From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
Subject: Re: Normal numbers (was Re: Number of numbers (Was Re: PI))
Organization: U of Cambridge, England
Date: Tue, 5 Jan 1993 01:51:51 GMT

In article <1993Jan4.205723.27180@oracle.us.oracle.com> mfriedma@uucp (Michael Friedman) writes:
>In article <1993Jan4.134418.25602@infodev.cam.ac.uk> gjm11@cus.cam.ac.uk (G.J. McCaughan) writes:

>>Yes. 0.12345678910111213141516171819202122...100101102103104105106...
    [is normal to base 10^anything]
>>(write down all the positive integers in order and stick 'em together).
>
>Not true.  Randomly chosen segments will be more than 10% ones.

Ho hum. I've been replying to people individually on this one, but perhaps
it's time to post a few more words of explanation.

(i) The statement I made is also in Hardy & Wright (intro. to thy of numbers)
    so it's not just me saying this. :-)

(ii) The point is that the funnies (too many 1's, not enough 0's, odd
     things happen at "edges" of integers...) don't matter because their
     contribution is asymptotically small.

So, pick a sequence of digits with length k.
Let N(s,m) be the number of occurrences of that sequence in the portion
of the number consisting of: integers starting with s [s is a digit string
not starting with 0] of length length(s)+m. Thus N("123",2) is the number
of occurrences of our selected sequence in the string 123001230112302...12399.
Write A(s,m) for N(s,m) divided by the length of that string. (in this case,
500).

Let N'(s,m) be the same, except that we only count occurrences of s in the
"varying" portions, and don't consider occurrences that straddle boundaries
between integers. So N'(s,m) doesn't really depend on s. For instance,
N("123",2) is the number of occurrences of our sequence in the string
00 01 02 03 ... 99 (the spaces are deliberate). Actually it's not quite
true that N'(s,m) doesn't depend on s, because when s is the empty string
we "lose" the numbers starting with 0. So when s=empty and our selected
string starts with 0, N'(s,m) may be less than the "obvious" value by
up to 10^(m-1). I'll write N'(s,m) for the "obvious" value, and include
that 10^(m-1) in with the "error term" I'm about to introduce.

Of course N(s,m) >= N'(s,m). Write R(s,m) for the difference. This difference
is no greater than the number of places where our selected string *could*
start, which would make it occur illegally. So, the places in question are
the first length(s) places of each integer, and the last k-1 places. When
m is not too big, these may overlap, but that doesn't matter: we're just
looking for a crude upper bound on R(s,m). And we mustn't forget that extra
term from the previous paragraph. So, in fact, we have
    R(s,m) <= (length(s)+k-1).10^m + 10^(m-1)
           <= (length(s)+k).10^m .
And it's easy to check that
    N'(s,m) = (m-k+1).10^(m-k) .
Write A'(s,m) for N'(s,m)/<same as for A()>
      T(s,m)  for  R(s,m)/<same again>.

Now, what we want to prove is that as n tends to infinity, 
    (number of occurrences of selected string in first n digits) / n
  = M(n)/n, say
tends to 1/10^k.

Well, suppose the first n digits get as far as the number h, followed
by some fragment (perhaps empty) of h+1. Suppose h has d digits, which
are h1,h2,...,hd (from left to right). Then M(n) is
    N(-,1) + ... + N(-,d-1)
  + N(1,d-1)+...+N([h1-1],d-1)
  + N([h1]0,d-2)+...+N([h1][h2-1],d-2)
  + N([h1h2]0,d-3)+...+N([h1h2][h3-1],d-2)
  + ...
  + N([h1..h(d-1)0],0)+...+N([h1..hd],0)
  + number of occurrences in fragment of h+1.

And n is 9+90.2+900.3+...+9.10^(d-2).(d-1) 
         + (h1-1).10^(d-1).d
         + h2.10^(d-2).d
         + ...
         + h(d-1).10.d
         + (hd+1).d
         + length of fragment (less than d) .

We can consider our ratio M(n)/n as a weighted average of the A(),
weighted according to the number of digits in the relevant portion
of our number.

Well, A'(s,m) = (m-k+1).10^(m-k) / (m+length(s)).10^m
              = (m-k+1)/(m+length(s)) / 10^k .

And the "error term" is
      T(s,m) <= (length(s)+k).10^m / (m+length(s)).10^m
              = (length(s)+k) / (m+length(s)) .

And A'(s,m) differs from 1/10^k by at most
                (length(s)+k-1)/(m+length(s)) / 10^k .

So the difference between A(s,m) and 1/10^k is at most
                2(length(s)+k)/(m+length(s))
   = E(s,m), say.

Now, let's think about that weighted average. The number of different
N(...,...) terms is (d-1) + (h1-1) + h2 + h3 + ... + hd,
which is less than 10d. Suppose we consider only those terms
N(...,r) where r > R. (I'll decide what R has to be shortly.)
There are at most 10d other ones, trivially, and the weight corresponding
to any other is at most d.10^R; so the total "weight" for the other terms
is at most 10d^2.10^R. The total of all the weights is n, which from our
earlier expression is at least 9(d-1).10^(d-2). Since E(s,m) is at most
2(1+k), which doesn't depend on s,m, the total error contributed by these
terms is at most d^2.10^(R+1).2(1+k) / {9(d-1).10^(d-2)}
              <= 2000d(1+k) / 10^(d-R)
so if we make d-R = log_10(2000d^2(1+k)) this error tends to 0 as d does,
hence also as n does.
We must also consider the error from the terms we have included. They all
have length(s) <= d-r <= d-R = log(C.d^2), and so the corresponding
A() differs from 1/10^k by at most 
       2(k+log(C.d^2))/R
     = 2(k+log(C.d^2))/(d-log(C.d^2))
    <= constant/root(d), say
as d tends to infinity; so the contribution of these terms' errors tends
to zero too.

So the total error term is bounded by the sum of these two error terms,
and since these both tend to zero, so does the overall error. QED.

Right, that's it. In gory, gruesome detail. Any questions?

-- 
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]