Does this random sequence contain the number 1?

Randomly choose a number from 1 to 3 and call it $$a_1$$;

Randomly choose a number from 1 to 3$$a_1$$ and call it $$a_2$$;

Randomly choose a number from 1 to 3$$a_2$$ and call it $$a_3$$;

$$\cdots$$

Repeat this process ad infinitum to get a sequence $$s=a_1,a_2,a_3,...$$

Question: does $$s$$ contain the number 1 with probability 1?

• Just for clarity, do you mean an integer and are the endpoints included? Dec 8, 2023 at 17:47
• @WeatherVane Probability 1 doesn’t mean absolute certainty: if I tell you to pick a random real number, the probability I’m wrong by saying « you picked 5 » is 1, but it’s actually possible for you to have picked 5. Dec 8, 2023 at 18:29
• $0.\dot{9}$ is $1$. See math.stackexchange.com/questions/11/… Dec 8, 2023 at 18:50
• Probability 1 actually means almost surely Dec 8, 2023 at 21:58
• @hexomino Yes, we randomly choose integers and end points are included.
– Eric
Dec 9, 2023 at 4:20

Supposing that the number following any integer $$n$$ is another integer in $$[1,3n]$$, here's a partial answer, showing that

in the long run, $$1$$ (or any other fixed number) appears in any fixed position with probability $$0$$.

Let $$p_n$$ be the long-run probability that $$n$$ appears in some position. What came before $$n$$? If it was $$k$$, where $$k = \lceil\frac{n}{3}\rceil$$, then there was a $$\frac{1}{3k}$$ chance of $$n$$ following it. If it was $$k+m$$, then $$n$$ followed with probability $$\frac{1}{3(k+m)}$$.

We can thus say, in an informal sense, that $$p_n = \frac{p_k}{3k}+\frac{p_{k+1}}{3(k+1)}+\frac{p_{k+2}}{3(k+2)}+\dots$$. The first few examples of this are:
\begin{align} p_1=&\frac{p_1}{3}+&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_2=&\frac{p_1}{3}+&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_3=&\frac{p_1}{3}+&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_4=&&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_5=&&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_6=&&\frac{p_2}{6}+&\frac{p_3}{9}+&\dots\\p_7=&&&\frac{p_3}{9}+&\dots\end{align}
We can solve for later series in terms of earlier ones - a bit of manipulation yields the recurrence $$p_{3k+1}=p_{3k+2}=p_{3k+3}= p_{3k}-\frac{p_k}{3k}$$. However, there's a problem: if we substitute a multiple of $$\frac{1}{n}$$ for $$p_n$$, say, the left-hand side is greater than the right! This implies that the real $$p_n$$ decrease slower than the harmonic series - and since the sum of the $$p_n$$ can't diverge, none of them can be positive.

Does this help solve the main problem?

Suppose the answer to the original question was "Yes". Find the next 1 in the sequence, and remove everything up to it - what remains is an identically-generated sequence, which contains another 1 with probability 1. Therefore, a positive answer to the main problem implies a positive answer to the stronger question of whether such a sequence contains infinitely many 1's with probability 1.
However, we've shown that a sequence contains a positive proportion of 1's with probability 0, so the distribution of "repeat times" has infinite expectation. Althiugh this doesn't imply that infinite values appear with positive probability (which would constitute a negative answer), it definitely makes it more likely.

I think the short answer is

Yes

Why? Well because logically

If we repeat this process infinitely we have to get $$1$$ eventually since if we don't get one we just do it again infinitely. So logically the answer is yes.

But let's look at it from a mathematical standpoint

We can define 3 possible outcomes, choosing the number $$1$$,choosing a number from $$[1,2\infty]$$, or choosing a number from $$[1,3\infty]$$. Since $$\infty$$ is an unreachable value we can consider $$\infty *$$ any number $$= \infty$$ effectively. Therefore all in all possible outcomes we are choosing a number from $$[1,\infty]$$. So, assuming that we never get 1 the probability of getting a 1 the next time $$\frac{1}{\infty}$$. However, since we know $$\infty$$ can never be reached essentially the probability is $$0$$. So mathematically the probability of getting a 1 is p(getting a 1)=1-p(not getting a 1) which we can rewrite as $$1-0$$ so the probability of getting a 1 is always 1 if we repeat this infinetly.

Note: I'm not a math guy so if someone could look at my math proof and clean it up that would be great!

When I say "Assuming that we never get 1 the probability of getting a 1" what I mean is assuming worse case. Not sure if I can do that when making a mathematical proof. But hopefully someone can make that make sense?

Hopefully this helps someone

• "If we repeat this process infinitely we have to get 1 eventually since if we don't get one we just do it again infinitely." This, if I understand, is wrong (or insufficient). For example, instead choose $a_i$ to be (independently) $1$ with probability $p_i$ with the infinite product of $(1 - p_i)$ equal to some number between $0$ and $1$. For a less abstract (but less elementary) example, take the probability of returning to the origin in a 3d random walk. Dec 9, 2023 at 2:27