What is the chance that an infinite series of random numbers will, at some point, repeat all previously generated numbers in that order?

Question

The main reason of this post is to provide a writeup of what I think is a correct solution to this problem from the r/math subreddit. I'll quote the poster to phrase the problem:

What is the chance that an infinite series of random numbers will, at some point, repeat all previously generated numbers in that order?

While there was some confusion in the comments, I believe what the poster means is something like the sequences below: $$7,7,...$$ $$3,2,3,2,...$$ $$7,8,6,7,8,6,...$$ Where the dots afterward are arbitrary as the condition has already been fulfilled. If we start writing out a sequence of digits in this way, where the probability of selecting any digit is equal, what is the probability that something like this will happen?

I'll post my solution below. Feel free to comment or correct me.

Answer 1

EDIT: This answer is incorrect, but I'll leave it up as it was my original approach.

First, some definitions. Let the digits of the sequence be defined as the list $a_0,a_1,a_2,...$ Let the blocks of $2^n$ digits be defined as $b_1,b_2,...$ What I mean by this is more easily illustrated by looking at the decimal expansion of $e$: $$ \underbrace{2.7}_{b_0}\underbrace{18}_{b_1}\underbrace{2818}_{b_2}\underbrace{28459045}_{b_3}\underbrace{2353602874713526}_{b_4}...$$ $b_n$ is the $n$th block of $2^n$ numbers, save for the first one. I will also define $c_n$ as the $n$th partial sequence - eg for $\pi$, $$c_5=3,1,4,1,5$$ With that out of the way, the solution is rather simple. Let the probability of such a sequence occurring be $p$. Then we can write $$p=\Pr(a_1=a_0)+\Pr(b_1=c_2)\Pr(a_1\neq a_0)+\Pr(b_2=c_4)\Pr(b_1\neq c_2)+\Pr(b_3=c_8)\Pr(b_2\neq c_4)+...$$ $$p=0.1+0.01\cdot0.9+\sum_{n=2}^\infty \Pr(b_n=c_{2^n})\Pr(b_{n-1}\neq c_{2^{n-1}})$$ $$p=0.109+\sum_{n=2}^\infty \left(\frac{1}{10}\right)^{2^n}\left(\frac{9}{10}\right)^{2^{n-1}}$$ $$p\approx 0.1090810065610000431...$$

Perhaps someone can find a closed form for the above sum.

Answer 2

Your solution is hard to follow, even the definitions. Not sure why you skip from using $e$ as an example to using $\pi$, nor why you appear to make an issue of the first decimal in $e$. A string of digits doesn't have a natural location for the decimal point. Also, why the special interest in powers of $2$?

In any case, let's just consider the simpler problem of the first $6$ digits.

There is, of course, a $\frac 1{10}$ chance that the first two digits match. So $p_1=.1$ There are, of course, $10$ strings of length $2$ of that form.

Failing that, we consider strings of the form $XYXY$ where $X\neq Y$. There are $90$ strings of that form, out of a possible $10^4$. So $p_2=\frac {90}{10000}=.009$

For $p_3$, there are $10^6$ strings of length $6$ of which $10^3$ have the same first $3$ and last $3$ digits. Of these, only those where the first and third digits match replicate after $4$, and only those where the first and seconds digit match replicate after $2$. So we just need the first digit to be distinct from the second two. There are, therefore, $10\times 9^2$ good strings of length $6$, so $$p_3=\frac {10\times 9^2}{10^6}=.00081$$

But then $$p_1+p_2+p_3=.10981$$ which is already greater than your answer.

Answer 3

In base 2, the answer is

$$ \sum_{i=1}^{\infty}\frac{a(i)}{4^i} $$

where $a(i)$ is OEIS A216958. Per comments, there is no known closed solution or recurrence for that sequence, so it seems unlikely there will exist one for this sum.

The 20th partial sum of the above is ~ 0.72995609.