Permutations in an Infinite List of Random Numbers

Question

In an infinite list of random numbers from a to b, prove that in this list, there are all possible permutations of n numbers from the list, where n can be any number. Here are some versions of the problem in context:

"Every phone number in the world appears among the decimal places of pi... and if you converted the numbers to letters, you'd find every book that's ever been written or will be written." (from Think of a Number, by Johnny Ball)

"Consider Coin Man, who makes decisions based on the flip of a coin. Let's say that if he flips heads, he moves one step up the page, and if he flips tails, he moves a step down the page... if we imagine that at a certain distance from the starting point in one direction there is a barrier, there is a 100 per cent chance that eventually Coin Man will hit the barrier." (from Alex's Adventures in Numberland, by Alex Bellos)

For the first version, how do we know that it contains every phone number or book in the world? For the second version, how do we know that Coin Man will hit the barrier? I can sort of visualise it, but I'd really like a rigorous proof.

Edit: "Does Ball actually say that "Every phone number in the world appears among the decimal places of pi"? People think this is likely, but it's not known to be true. You can't believe everything you read. (It is true for "almost every" number in place of π.)" - a commenter. Maybe this is true, in which case, you can simply ignore the first example. Or, where pi is mentioned, just think of any infinite sequence of digits.

Answer 1

For the first question :

An irrational number $x$ is called a 'normal number' if for any natural number $n$ with $m$ digits, the density of $n$ in the decimal digits of $x$ is $\frac{1}{10^m - 10^{m-1}}$ in all bases (i.e. you see every natural number (with the same number of digits) in the decimal digits the same time). It is a conjecture that whether $\pi$ is a normal number or not and we don't know much about the normal numbers (the first example of a normal number is $0.123456789101112...$ and it is found much after the definition of a normal number).

For the second question :

Law of large numbers states that if an event is possible then it'll eventually happen if you make the experiment sufficiently. There is a possibility that Coin Man hits the barrier thus it'll eventually happen if he flips so many times.

https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Law_of_large_numbers

Answer 2

The statement about the digits of $\pi$ is not known to be true.

But the corresponding statement is true for a random sequence of digits. Say we're looking for the sequence 1243. That could be the first four digits, or the next four digits... Probability problems with "and" are often easier than problems with "or". Say the sequence 1243 does not appear in out random sequence.

That means the first four digits are not 1243, and the next four digits are not 1243, and the four digits after that are not 1243... The probability of each miss is $9999/10,000$. So the probability that we miss infinitely many times is the infinite product $$(9999/10,000)(9999/10,000)\dots=0.$$