3

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.

Blue
  • 75,673
K.defaoite
  • 12,536
  • Yep, I'll close. EDIT: It seems I can't close my own question as a duplicate on my own. Can a moderator step in here? – K.defaoite Dec 14 '20 at 16:52

3 Answers3

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.

ecatmur
  • 131
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.

K.defaoite
  • 12,536
  • Aren't you missing some events in your equation for $p$? E.g.what about your example 7.6876811111111...? The length of the repeat doesn't have to be a power of two, does it? – Neal Young Dec 14 '20 at 14:23
  • @Neal Young I was considering looking back on the entire string and either repeating it or not repeating it, but I obviously missed this simple possibility. Thanks for pointing this out. – K.defaoite Dec 14 '20 at 14:58
  • 1
    here is a duplicate, but it does not contain an answer. – lulu Dec 14 '20 at 15:19
1

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.

lulu
  • 70,402
  • Nice. Strangely, in base 2 the probability is 1 $(={1\over 2}+{1\over 4} \cdots )$ – user619894 Dec 14 '20 at 14:52
  • The interest in powers of $2$ is that I am looking at the entire previous string and computing the probability that it is repeated. This leads to chunks of size $2^n$. – K.defaoite Dec 14 '20 at 14:56
  • 1
    @user619894 Even base $2$ is complicated. You are getting things like $\frac 14$ because you are arguing that that there is a $\frac 14$ chance that the third digit matches the first and the fourth matches the second, but that double counts $00$ and $11$. For binary length $4$, there are only $2$ strings to consider, namely $10$ and $01$. – lulu Dec 14 '20 at 14:57
  • @K.defaoite Not following. Any length string can be replicated. In my calculation for $p_3$ I am looking at the length $3$ strings which replicate (producing a length $6$ string in the end). I don't see anything special about powers of $2$. – lulu Dec 14 '20 at 14:58
  • @lulu Yes, I see this now. Thanks for the observation. – K.defaoite Dec 14 '20 at 15:00
  • 1
    @K.defaoite Should add: hastily written code appears to suggest that the answer approaches $.11$ but I didn't take time to debug it properly. – lulu Dec 14 '20 at 15:01
  • Any ideas as to how we might express this probability as an infinite sum? – K.defaoite Dec 14 '20 at 15:03
  • @K.defaoite Not immediately. My code works recursively which makes computation fast but which doesn't appear to lend itself to general expressions. i suggest analyzing base $2$ first. Same problem but the patterns are simpler. – lulu Dec 14 '20 at 15:10