The
Random Infinite
Nick
Ascroft
Two
statements on infinity are below, the
second seems to be demonstrably untrue,
but how does the first differ?
(1)
Any infinite random string of units
will contain every possible combination
of those units.
(2)
Any infinite non-random but unrestricted
string of units will contain every possible
combination of those units.
The
first claim is the (necessarily) modified
version of the assertion that a monkey
(or an infinite number of monkeys) jabbing
randomly at a typewriter would eventually
type the complete works of Shakespeare.
I bracket out 'necessarily' as I find
the hidden but wilful abstraction of
this idea irritating. The nature and
finiteness of monkeys is ignored. Point
one, no monkey will produce a random
string. Point one clarified, no monkey,
even no chimp, will hit the space bar
enough, nor hold the shift key down
enough for capitals, let alone hit all
of the keys. Point two, no monkey has
an infinite life, the word monkey
defines a member of a set of very real
animals with specific lifespans. This
characteristic is essential to their
monkeyhood. A godlike immortal monkey
is quite a fictitious and fantastical
place to start. Nor is it possible for
there to be infinite monkeys, whose
finite populations will over the course
of the universe eventually become extinct.
This
last point however is the easiest to
let slide into hypothetical abstraction.
And such pooh-poohing stickler pragmatics
may seem absurd and unbefitting of an
essentially mathematical problem simply
being colourfully illustrated. (I find
a good counter-illustration to express
why the monkey-typewriter scenario is
a dud: imagine an immortal chimpanzee
(who never learns) faced with the typesetting
program InDesign: if placed in front
of an immortal computer running this
software forever, would the monkey eventually
typeset an exact replica of the Oxford
University Press's latest edition of
The Oxford Shakespeare: The
Complete Works -- including page
numbers, the running heads, the font
style variation, the italicisation?
Clearly not. It is an ape. The typewriter
likewise is too difficult a technology.)
But
if the assertion is to be truly considered,
such obvious stumbling blocks should
be removed. Nevertheless the idea behind
the conundrum is easily modified and
it's best to get to its heart, that
these imagined monkeys, not understanding
the meanings of the typewriter keys
would produce a random string of letters,
numbers, symbols and punctuation.
Must
then a truly random infinite string
contain all possible variations of that
string? One could quibble over the definition
of 'random' . It has been argued that
this is a fictitious notion, that all
random generators to date are based
on some algorithm or other. Is it possible
for instance for any existing random
number generators to produce a nine
repeatedly, and only a nine for four
billion years? This, like any slice,
is a small slice of the infinite and
just as random an occurrence as any
other four-billion-year string.
However,
let's imagine that randomness is real,
and that a truly random generator exists.
In fact let's make it even easier. Imagine
this generator only generates words
and only those which are in Shakespeare's
vocabulary. Ignoring punctuation and
spaces, over an infinite period must
this generator write Shakespeare's complete
works in perfect order? A better and
more probing question is this: is it
possible for there to be an infinite
string created by this generator which
does not contain Shakespeare's
complete works? Just as it is possible
for there to be an infinite string of
numbers which does not contain the number
three (all even numbers for instance),
is it conceivable that the generator
could go forever creating combinations
of Shakespearean words which every time
failed to be the complete works? There
are after all infinite strings of Shakespearean
words which do not contain the complete
works. For instance, an infinite string
of Shakespearean words in which the
word 'but' never occurs. Could the random
generator not generate one of these?
To
limit the generator further, imagine
if it generated a random string of Shakespearean
words the exact length of the complete
works. There are only a finite number
of combinations of this string and one
of them clearly is the complete works.
But if left to generate these forever
would it necessarily go through all
combinations, or could it perhaps just
endlessly repeat combinations that weren't
the complete works?
This
is like asking: would a random number
generator set to endlessly pick numbers
between zero and nine ever fail to pick
the number five for eternity? Or, could
a coin flipped endlessly always land
on heads? Instinct yells No! but hold
on. Some might rush to the defence in
the name of randomness, saying that
an inherent aspect of randomness is
that any combination is capable of appearing
and therefore over enough time all must.
This is a definition of randomness based
around this very problem and so is self-answering.
If randomness is defined at the level
of each single instance, however, the
prospect seems more believable. With
each instance just as likely to be any
of a variety of options, on each occasion
it is just as likely to be any one of
these, and if one of these is heads
over tails, it is just as likely to
be heads each time even if it has been
heads for a massively large number of
times on preceding flips.
To
go further, imagine a series of infinite
binary strings, and instead of one and
zero you have heads and tails. The first
might start HTTTHHTHTHHTTT ... and a
second might start TTTHTHHTTTHHT ...
How many of these possible infinite
binary strings exist? Clearly this too
is infinite. Numbered among these infinite
possible strings however, must there
not be one combination which begins
HHHHHHHHHHHHH and continues like that
forever? And if a truly random generator
was to select one of these possible
infinite binary strings would it not
be just as likely to select the one
that was always heads as any other?
That is to say, doesn't this mean an
infinite random series might not contain
every possible combination of the units
it is choosing from?
Let's
return to the random complete-works-length
generator running forever. Among all
the possible random infinite strings
of complete-works-length sets of random
Shakespearean words, is there not a
string which, for instance, starts with
the complete works exactly but for the
last two words being in reverse order
and then, like endless heads, repeats
this same combination forever (or any
other of the many possible infinite
iterations of the generator which do
not include spitting out the complete
works)? And of all possible infinite
strings of complete-works-length sets
of random Shakespearean words (of which
there are an infinite number), is this
one not just as likely to be selected
randomly as any other?
I
believe so, but perhaps there is a hole
in my logic as infinity is clearly a
slippery body. But if so, the first
proposition above is false. Not every
random infinite string need contain
every possible iteration of the units
of that string. That is, the highly
hypothetical monkeys even over infinity
can fail. Which leads to the second
proposition above, widely implied as
true and from which many dubious entailments
follow. This I will discuss shortly
...
