The Mathematical Intelligencer
ISSN 0343-6993
Volume 35
Number 1
Math Intelligencer (2013) 35:42-60
DOI 10.1007/s00283-012-9340-x
Walking on Real Numbers
Francisco J. Aragón Artacho, David
H. Bailey, Jonathan M. Borwein & Peter
B. Borwein
1 23
Your article is protected by copyright and all
rights are held exclusively by Springer Science
+Business Media New York. This e-offprint is
for personal use only and shall not be self-
archived in electronic repositories. If you
wish to self-archive your work, please use the
accepted author’s version for posting to your
own website or your institution’s repository.
You may further deposit the accepted author’s
version on a funder’s repository at a funder’s
request, provided it is not made publicly
available until 12 months after publication.
Walking on Real
Numbers
F
RANCISCO
J. A
RAGO
´
N
A
RTACHO
,D
AVID
H. B
AILEY
,J
ONATHAN
M. B
ORWEIN
,
AND
P
ETER
B. B
ORWEIN
T
T
he digit expansions of
p
;
e
;
ffiffiffi
2
p
, and other mathemat-
ical constants have fascinated mathematicians from
the dawn of history. Indeed, one prime motivation
for computing and analyzing digits of
p
is to explore the
age-old question of whether and why these digits appear
˜˜random.” The first computation on ENIAC in 1949 of
p
to
2037 decimal places was proposed by John von Neumann
so as to shed some light on the distribution of
p
(and of
e
)
[
15
, pg. 277“281].
One key question of some significance is whether (and
why) numbers such as
p
and
e
are ˜˜normal.” A real constant
a
is
b
-normal if, given the positive integer
b
C
2, every
m
-long
string of base-
b
digits appears in the base-
b
expansion of
a
with precisely the expected limiting frequency 1/
b
m
.Itisa
well-established, albeit counterintuitive, fact that given an
integer
b
C
2, almost all real numbers, in the measure theory
sense, are
b
-normal. What’s more, almost all real numbers are
b
-normal simultaneously for all positive integer bases (a
property known as ˜˜absolutely normal”).
Nonetheless, it has been surprisingly difficult to prove
normality for well-known mathematical constants for any
given base
b
, much less all bases simultaneously. The first
constant to be proven 10-normal is the Champernowne
number, namely the constant 0
:
12345678910111213141516
¦
,
produced by concatenating the decimal representation of all
positive integers in order. Some additional results of this sort
were established in the 1940s by Copeland and Erd
}
os [
26
].
At present, normality proofs are not available for any well-
known constant such as
p
;
e
;
log 2
;
ffiffiffi
2
p
. We do not even know,
say, that a 1 appears one-half of the time, in the limit, in the
binary expansion of
ffiffiffi
2
p
(although it certainly appears to), nor
do we know for certain that a 1 appears infinitely often in the
decimal expansion of
ffiffiffi
2
p
. For that matter, it is widely believed
that
every
irrational algebraic number (i.e., every irrational root
of an algebraic polynomial with integer coefficients) is
b
-normal to all positive integer bases
b
, but there is no proof,
not for any specific algebraic number to any specific base.
In 2002, one of the present authors (Bailey) and Richard
Crandall showed that given a real number
r
in [0,1), with
r
k
denoting the
k
-th binary digit of
r
, the real number
a
2
;
3
ð
r
Þ
:
¼
X
1
k
¼
1
1
3
k
2
3
k
þ
r
k
ð
1
Þ
is 2-normal. It can be seen that if
r
=
s
, then
a
2,3
(
r
)
=
a
2,3
(
s
),
so that these constants are all distinct. Since
r
can range over
the unit interval, this class of constants is uncountable. So, for
example, the constant
a
2
;
3
¼
a
2
;
3
ð
0
Þ¼
P
k
1
1
=
ð
3
k
2
3
k
Þ¼
0
:
0418836808315030
¦
is provably 2-normal (this special
case was proven by Stoneham in 1973 [
43
]). A similar result
applies if 2 and 3 in formula (
1
) are replaced by any pair of
coprime integers (
b
,
c
) with
b
C
2 and
c
C
2[
10
]. More
recently, Bailey and Michal Misiurewicz were able to
establish 2-normality of
a
2,3
by a simpler argument, by uti-
lizing a ˜˜hot spot” lemma proven using ergodic theory
methods [
11
].
In 2004, two of the present authors (Bailey and Jonathan
Borwein), together with Richard Crandall and Carl Pomer-
ance, proved the following: If a positive real
y
has algebraic
degree
D
[
1, then the number #(
y
,
N
) of 1-bits in the binary
expansion of
y
through bit position
N
satisfies #(
y
,
N
)
[
CN
1/
D
,
for a positive number
C
(depending on
y
) and all sufficiently
large
N
[
5
]. A related result has been obtained by Hajime
Kaneko of Kyoto University in Japan [
37
]. However, these
results fall far short of establishing
b
-normality for any irra-
tional algebraic in any base
b
, even in the single-digit sense.
Supported in part by the Director, Office of Computational and Technology Research, Division of Mathematical, Information, and Computational Scien
ces of the U.S.
Department of Energy, under contract number DE-AC02-05CH11231.
42
THE MATHEMATICAL INTELLIGENCER
2012 Springer Science+Business Media New York
DOI 10.1007/s00283-012-9340-x
Author’s
personal
copy
1 Twenty-First Century Approaches
to the Normality Problem
In spite of such developments, there is a sense in the field that
more powerful techniques must be brought to bear on this
problem before additional substantial progress can be
achieved. One idea along this line is to study directly the
decimal expansions (or expansions in other number bases) of
various mathematical constants by applying some techniques
of scientific visualization and large-scale data analysis.
In a recent paper [
4
], by accessing the results of several
extremely large recent computations [
46
,
47
], the authors tes-
ted the first roughly four trillion hexadecimal digits of
p
by
means of a Poisson process model: in this model, it is
extraordinarily unlikely that
p
is not normal base 16, given its
initial segment. During that work, the authors of [
4
], like many
others, investigated visual methods of representing their large
mathematical data sets. Their chosen tool was to represent
these data as walks in the plane.
In this work, based in part on sources such as [
22
,
23
,
21
,
19
,
14
], we make a more rigorous and quantitative study of these
walks on numbers. We pay particular attention to
p
, for which
we have copious data and which”despite the fact that its
digits can be generated by simple algorithms”behaves
remarkably ˜˜randomly.”
The organization of the article is as follows. In Section
2
we
describe and exhibit uniform walks on various numbers, both
rational and irrational, artificial and natural. In the next two
sections, we look at quantifying two of the best-known fea-
tures of random walks: the expected distance traveled after
N
steps (Section
3
) and the number of sites visited (Section
4
)
In Section
5
we describe two classes for which normality and
nonnormality results are known, and one for which we have
only surmise. In Section
6
we show various examples and
leave some open questions. Finally, in Appendix
7
we collect
the numbers we have examined, with concise definitions and
a few digits in various bases.
2 Walking on Numbers
2.1 Random and Deterministic Walks
One of our tasks is to compare deterministic walks (such as
those generated by the digit expansion of a constant) with
pseudorandom walks of the same length. For example, in
Figure
1
we draw a uniform pseudorandom walk with one
million base-4 steps, where at each step the path moves one
unit east, north, west, or south, depending on the whether the
pseudorandom iterate at that position is 0, 1, 2, or 3. The color
indicates the path followed by the walk”it is shifted up the
spectrum (red-orange-yellow-green-cyan-blue-purple-red)
following an HSV scheme with
S
and
V
equal to one. The HSV
(hue, saturation, and value) model is a cylindrical-coordinate
representation that yields a rainbow-like range of colors.
Figure 1.
A uniform pseudorandom walk.
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦.
¦¦¦¦¦¦¦¦..
AUTHORS
FRANCISCO J. ARAGO
´
N ARTACHO
earned his Ph.D. in optimization in 2007 at
the University of Murcia, Spain. After work-
ing for a business in Madrid for a year, he
took a postdoctoral position at the Univer-
sity of Alicante, supported by the program
˜˜Juan de la Cierva.” In 2011, he became a
Research Associate at the Priority Research
Centre for Computer-Assisted Research
Mathematics and its Applications (CARMA),
University of Newcastle, Australia, under the
direction of Jonathan Borwein, with whom
he’s currently collaborating on several
projects.
Centre for Computer Assisted Research
Mathematics and its Applications
(CARMA)
DAVID H. BAILEY
is a Senior Scientist at
Lawrence Berkeley National Laboratory.
Before coming to the Berkeley Lab in 1998,
he was at NASA’s Ames Research Center for
14 years. Bailey has received the Chauvenet
Prize from the Mathematical Association of
America, the Sidney Fernbach Award from
the IEEE Computer Society, and the Gordon
Bell Prize from the Association for Computing
Machinery. He is the author of five books,
including
Mathematics by Experiment: Plausi-
ble Reasoning in the 21st Century
, coau-
thored with Jonathan Borwein.
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
USA
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
43
Author’s
personal
copy
The rational numbers
Q
1and
Q
2 represent the two possi-
bilities when one computes a walk on a rational number:
either the walk is bounded as in Figure
2
(a) (for any walk with
more than 440 steps one obtains the same plot), or it is
unbounded but repeating some pattern after a finite number
of digits as in Figure
2
(b).
Of course, not all rational numbers are that easily identified
by plotting their walks. It is possible to create a rational
number whose period is of any desired length. For example,
the following rational numbers from [
39
],
Q
3
¼
3624360069
7000000001
and
Q
4
¼
123456789012
1000000000061
;
have base-10 periodic parts with length 1,750,000,000 and
1,000,000,000,060, respectively. A walk on the first million
digits of both numbers is plotted in Figure
3
. These huge
periods derive from the fact that the numerators and
denominators of
Q
3 and
Q
4 are relatively prime, and the
denominators are not congruent to 2 or 5. In such cases, the
period
P
is simply the discrete logarithm of the denomi-
nator
D
modulo 10; or, in other words,
P
is the smallest
n
such that 10
n
mod
D
¼
1.
Graphical walks can be generated in a similar way for other
constants in various bases”see Figures
2
through
7
.Where
the base
b
C
3, the base-
b
digits can be used to a select, as a
direction, the corresponding base-
b
complex root of unity”a
multiple of 120
for base three, a multiple of 90
for base four, a
multiple of 72
for base 5, etc. We generally treat the case
b
=
2 as a base-4 walk, by grouping together pairs of base-2
digits (we could render a base-2 walk on a line, but the
resulting images would be much less interesting). In Figure
4
the origin has been marked, but since this information is not
that important for our purposes, and can be approximately
deduced by the color in most cases, it is not indicated in the
others. The color scheme for Figures
2
through
7
is the same as
the above, except that Figure
6
is colored to indicate the
number of returns to each point.
2.2 Normal Numbers as Walks
As noted previously, proving normality for specific constants
of interest in mathematics has proven remarkably difficult.
The tenor of current knowledge in this arena is illustrated by
[
45
,
14
,
34
,
38
,
40
,
39
,
44
]. It is useful to know that, while small
in measure, the ˜˜absolutely abnormal” or ˜˜absolutely non-
normal” real numbers (namely those that are not
b
-normal for
any integer
b
) are residual in the sense of topological category
[
1
]. Moreover, the Hausdorff“Besicovitch dimension of the set
of real numbers having no asymptotic frequencies is equal to
1. Likewise the set of Liouville numbers has measure zero but
is of the second category [
18
,p.352].
(a)
(b)
Figure 2.
Walks on the rational numbers
Q
1 and
Q
2.
Figure 4.
A million-step base-4 walk on
e
.
(a)(b)
Figure 3.
Walks on the first million base-10 digits of the rationals
Q
3 and
Q
4 from [
39
].
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
45
Author’s
personal
copy
One question that has possessed mathematicians for cen-
turies is whether
p
is normal. Indeed, part of the original
motivation of the present study was to develop new tools for
investigating this age-old problem.
In Figure
5
we show a walk on the first 100 billion base-4
digits of
p
. This may be viewed dynamically in more detail
online at
http://gigapan.org/gigapans/106803
, where the full-
sized image has a resolution of 372,224
9
290,218 pixels
(108.03 gigapixels in total). This must be one of the largest
mathematical images ever produced. The computations for
creating this image took roughly a month, where several parts
of the algorithm were run in parallel with 20 threads on
CARMA’s MacPro cluster.
By contrast, Figure
6
exhibits a 100 million base-4 walk on
p
, where the color is coded by the number of returns to the
point. In [
4
], the authors empirically tested the normality of its
first roughly four trillion hexadecimal (base-16) digits using a
Poisson process model, and they concluded that, according to
this test, it is ˜˜extraordinarily unlikely” that
p
is not 16-normal
(of course, this result does not pretend to be a proof).
In what follows, we propose various methods of analyzing
real numbers and visualizing them as walks. Other methods
widely used to visualize numbers include the matrix repre-
sentations shown in Figure
8
, where each pixel is colored
depending on the value of the digit to the right of the decimal
point, following a left-to-right up-to-down direction (in base 4
the colors used for 0, 1, 2, and 3 are red, green, cyan, and
purple, respectively). This method has been mainly used to
visually test ˜˜randomness.” In some cases, it clearly shows the
features of some numbers; as for small periodic rationals, see
Figure
8
(c). This scheme also shows the nonnormality of the
number
a
2,3
”see Figure
8
(d) (where the horizontal red bands
correspond to the strings of zeroes)”and it captures some of
the special peculiarities of the Champernowne’s number
C
4
(normal) in Figure
8
(e). Nevertheless, it does not reveal
the apparently nonrandom behavior of numbers such
as the Erd
}
os“Borwein constant; compare Figure
8
(f) with
Figure
7
(e). See also Figure
21
.
As we will see in what follows, the study of normal numbers
and suspected normal numbers as walks will permit us to
compare them with true random (or pseudorandom) walks,
obtaining in this manner a new way to empirically test ˜˜ran-
domness” in their digits.
3 Expected Distance to the Origin
Let
b
2f
3
;
4
;
¦
g
be a fixed base, and let
X
1
;
X
2
;
X
3
;
¦
be a
sequence of independent bivariate discrete random variables
whose common probability distribution is given by
PX
¼
cos
2
p
b
k
sin
2
p
b
k
¼
1
b
for
k
¼
1
;
¦
;
b
:
ð
2
Þ
Then the random variable
S
N
:
=
P
m
=1
N
X
m
represents a
base-
b
random walk in the plane of
N
steps.
The following result on the asymptotic expectation of the
distance to the origin of a base-
b
random walk is probably
known, but being unable to find any reference in the litera-
ture, we provide a proof.
T
HEOREM
3.1
The expected distance to the origin of a
base-b random walk of N steps is asymptotically equal
to
ffiffiffiffiffiffiffi
p
N
p
=
2.
P
ROOF
.
By the multivariate central limit theorem, the ran-
dom variable 1
=
ffiffiffiffi
N
p
P
N
m
¼
1
ð
X
m
l
Þ
is asymptotically
bivariate normal with mean
0
0
and covariance matrix
M
,
where
l
is the two-dimensional mean vector of
X
and
M
is its
2
9
2 covariance matrix. By applying Lagrange’s trigono-
metric identities, one obtains
l
¼
1
b
P
b
k
¼
1
cos
2
p
b
k
1
b
P
b
k
¼
1
sin
2
p
b
k
!
¼
1
b
1
2
þ
sin
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
1
2
cot
ð
p
=
b
Þ
cos
ð
b
þ
1
=
2
Þ
2
p
b
ðÞ
2 sin
ð
p
=
b
Þ
0
B
@
1
C
A
¼
0
0
:
ð
3
Þ
Thus,
M
¼
1
b
P
b
k
¼
1
cos
2
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
P
b
k
¼
1
sin
2
2
p
b
k
œ#
:
ð
4
Þ
Figure 5.
A walk on the first 100 billion base-4 digits of
p
(normal?).
Figure 6.
A walk on the first 100 million base-4 digits of
p
, col-
ored by number of returns (normal?). Color follows an HSV model
(green-cyan-blue-purple-red) depending on the number of returns
to each point (where the maxima show a tinge of pink/red).
46
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
Since
X
b
k
¼
1
cos
2
2
p
b
k
¼
X
b
k
¼
1
1
þ
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
sin
2
2
p
b
k
¼
X
b
k
¼
1
1
cos
4
p
b
k
2
¼
b
2
;
X
b
k
¼
1
cos
2
p
b
k
sin
2
p
b
k
¼
X
b
k
¼
1
sin
4
p
b
k
2
¼
0
;
ð
5
Þ
formula (
4
) reduces to
M
¼
1
2
0
0
1
2
:
ð
6
Þ
Hence,
S
N
=
ffiffiffiffi
N
p
is asymptotically bivariate normal with mean
0
0
and covariance matrix
M
. Because its components
ð
S
N
1
=
ffiffiffiffi
N
p
;
S
N
2
=
ffiffiffiffi
N
p
Þ
T
are uncorrelated, then they are inde-
pendent random variables, whose distribution is (univariate)
(a)(b)
(c)(d)
(e)(f)
Figure 7.
Walks on various numbers in different bases.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
47
Author’s
personal
copy
normal with mean 0 and variance 1/2. Therefore, the random
variable
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
ð
7
Þ
converges in distribution to a
v
random variable with two
degrees of freedom. Then, for
N
sufficiently large,
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ð
S
N
1
Þ
2
þð
S
N
2
Þ
2
q
¼
ffiffiffiffi
N
p
ffiffiffi
2
p
E
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
1
2
þ
ffiffiffi
2
p
ffiffiffiffi
N
p
S
N
2
2
s
0
@
1
A
ffiffiffiffi
N
p
ffiffiffi
2
p
C
ð
3
=
2
Þ
C
ð
1
Þ
¼
ffiffiffiffiffiffiffi
p
N
p
2
;
ð
8
Þ
where
E
ð Þ
stands for the expectation of a random
variable. Therefore, the expected distance to the
(a)(b)
(c)(d)
(e)(f)
Figure 8.
Horizontal color representation of a million digits of various numbers.
48
THE MATHEMATICAL INTELLIGENCER
Author’s
personal
copy
origin of the random walk is asymptotically equal to
ffiffiffiffiffiffiffi
p
N
p
=
2.
As a consequence of this result, for any random walk of
N
steps in any given base, the expectation of the distance to the
origin multiplied by 2
=
ffiffiffiffiffiffiffi
p
N
p
(which we will call
normalized
distance
to the origin) must approach 1 as
N
goes to infinity.
Therefore, for a ˜˜sufficiently” big random walk, one would
expect that the arithmetic mean of the normalized distances
(which will be called
average normalized distance
to the
origin) should be close to 1.
We have created a sample of 10,000 (pseudo)random
walks base-4 of one million points each in Python
1
,andwe
have computed their average normalized distance to the ori-
gin. The arithmetic mean of these numbers for the mentioned
sample of pseudorandom walks is 1.0031, whereas its stan-
dard deviation is 0.3676, so the asymptotic result fits quite well.
We have also computed the normalized distance to the origin
of 10,000 walks of one million steps each generated by the first
ten billion digits of
p
. The resulting arithmetic mean is 1.0008,
whereas the standard deviation is 0.3682. In Table
1
we show
the average normalized distance to the origin of various
numbers. There are several surprises in there data, such as the
Table 1. Average of the normalized distance to the origin of the walk of
various constants in different bases
Number Base Steps Average normalized
distance to the origin
Normal
Mean of 10,000
random walks
4 1,000,000 1.00315 Yes
Mean of 10,000 walks
on the digits of
p
4 1,000,000 1.00083 ?
a
2,3
3 1,000,000 0.89275 ?
a
2,3
4 1,000,000 0.25901 Yes
a
2,3
5 1,000,000 0.88104 ?
a
2,3
6 1,000,000 108.02218 No
a
4,3
3 1,000,000 1.07223 ?
a
4,3
4 1,000,000 0.24268 Yes
a
4,3
6 1,000,000 94.54563 No
a
4,3
12 1,000,000 371.24694 No
a
3,5
3 1,000,000 0.32511 Yes
a
3,5
5 1,000,000 0.85258 ?
a
3,5
15 1,000,000 370.93128 No
p
4 1,000,000 0.84366 ?
p
6 1,000,000 0.96458 ?
p
10 1,000,000 0.82167 ?
p
10 10,000,000 0.56856 ?
p
10 100,000,000 0.94725 ?
p
10 1,000,000,000 0.59824 ?
e
4 1,000,000 0.59583 ?
ffiffiffi
2
p
4 1,000,000 0.72260 ?
log 2 4 1,000,000 1.21113 ?
Champernowne
C
10
10 1,000,000 59.91143 Yes
EB
(2) 4 1,000,000 6.95831 ?
CE
(10) 4 1,000,000 0.94964 ?
Rational number
Q
1
4 1,000,000 0.04105 No
Rational number
Q
2
4 1,000,000 58.40222 No
Euler constant
c
10 1,000,000 1.17216 ?
Fibonacci
F
10 1,000,000 1.24820 ?
f
ð
2
Þ¼
p
2
6
4 1,000,000 1.57571 ?
f
ð
3
Þ
4 1,000,000 1.04085 ?
Catalan’s constant
G
4 1,000,000 0.53489 ?
Thue“Morse
TM
2
4 1,000,000 531.92344 No
Paper-folding
P
4 1,000,000 0.01336 No
Table 2. Number of points visited in various
N
-step base-4 walks. The
values of the two last columns are upper and lower bounds on the
expectation of the number of distinct sites visited during an
N
-step
random walk; see [31, Theorem 2] and [
32
]
Number Steps Sites visited Bounds on the expectation
of sites visited by a random
walk
Lower
bound
Upper
bound
Mean of 10,000
random walks
1,000,000 202,684 199,256 203,060
Mean of 10,000
walks on the
digits of
p
1,000,000 202,385 199,256 203,060
a
2,3
1,000,000 95,817 199,256 203,060
a
4,3
1,000,000 68,613 199,256 203,060
a
3,2
1,000,000 195,585 199,256 203,060
p
1,000,000 204,148 199,256 203,060
p
10,000,000 1,933,903 1,738,645 1,767,533
p
100,000,000 16,109,429 15,421,296 15,648,132
p
1,000,000,000 138,107,050 138,552,612 140,380,926
e
1,000,000 176,350 199,256 203,060
ffiffiffi
2
p
1,000,000 200,733 199,256 203,060
log 2 1,000,000 214,508 199,256 203,060
Champernowne
C
4
1,000,000 548,746 199,256 203,060
EB
(2) 1,000,000 279,585 199,256 203,060
CE(10) 1,000,000 190,239 199,256 203,060
Rational number
Q
1
1,000,000 378 199,256 203,060
Rational number
Q
2
1,000,000 939,322 199,256 203,060
Euler constant
c
1,000,000 208,957 199,256 203,060
f
ð
2
Þ
1,000,000 188,808 199,256 203,060
f
ð
3
Þ
1,000,000 221,598 199,256 203,060
Catalan’s
constant
G
1,000,000 195,853 199,256 203,060
TM
2
1,000,000 1,000,000 199,256 203,060
Paper-folding
P
1,000,000 21 199,256 203,060
1
Python uses the Mersenne Twister as the core generator and produces 53-bit precision floats, with a period of 2
19937
“
1
&
10
6002
. Compare the length of this period to the
comoving distance from Earth to the edge of the observable universe in any direction, which is approximately
4
:
6
10
37
nanometers, or to the number of protons in the universe,
which is approximately 10
80
.
2012 Springer Science+Business Media New York, Volume 35, Number 1, 2013
49
Author’s
personal
copy
fact that by this measure, Champernowne’s number
C
10
is far
from what is expected of a truly ˜˜random” number.
4 Number of Points Visited during an
N
-Step
base-4 Walk
The number of distinct points visited during a walk of a given
constant (on a lattice) can be also used as an indicator of how
˜˜random” the digits of that constant are. It is well known that
the expectation of the number of distinct points visited by an
N
-step random walk on a two-dimensional lattice is asymp-
totically equal to
p
N
/log(
N
); see, for example, [
36
,pg.338]or
[
13
, pg. 27]. This result was first proven by Dvoretzky and
Erd
}
os [
33
, Thm. 1]. The main practical problem with this
asymptotic result is that its convergence is rather slow; spe-
cifically, it has order of
ON
log log
N
=
ð
log
N
Þ
2
.In[
31
,
32
],
Downham and Fotopoulos show the following bounds on the
expectation of the number of distinct points,
p
ð
N
þ
0
:
84
Þ
1
:
16
p
1
log 2
þ
log
ð
N
þ
2
Þ
;
p
ð
N
þ
1
Þ
1
:
066
p
1
log 2
þ
log
ð
N
þ
1
Þ
!
;
ð
9
Þ
which provide a tighter estimate on the expectation than the
asymptotic limit
p
N
/log(
N
). For example, for
N
=
10
6
, these
bounds are (199256.1, 203059.5), whereas
p
N
/log(
N
)
=
227396, which overestimates the expectation.
In Table
2
we have calculated the number of distinct points
visited by the base-4 walks on several constants. One can see
that the values for different step walks on
p
fit quite well the
expectation. On the other hand, numbers that are known to be
normal such as
a
2,3
or the base-4 Champernowne number
substantially differ from the expectation of a random walk.
These constants, despite being normal, do not have a ˜˜ran-
dom” appearance when one draws the associated walk, see
Figure
7
(d).
At first look, the walk on
a
2,3
might seem random, see
Figure
7
(c). A closer look, shown in Figure
12
, shows a more
complex structure: the walk appears to be somehow self-
repeating. This helps explain why the number of sites visited
by the base-4 walk on
