7
$\begingroup$

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?

$\endgroup$
10
  • 4
    $\begingroup$ Just for clarity, do you mean an integer and are the endpoints included? $\endgroup$
    – hexomino
    Dec 8, 2023 at 17:47
  • 3
    $\begingroup$ @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. $\endgroup$
    – Jujustum
    Dec 8, 2023 at 18:29
  • 1
    $\begingroup$ $0.\dot{9}$ is $1$. See math.stackexchange.com/questions/11/… $\endgroup$
    – Jujustum
    Dec 8, 2023 at 18:50
  • 2
    $\begingroup$ Probability 1 actually means almost surely $\endgroup$
    – hexomino
    Dec 8, 2023 at 21:58
  • 3
    $\begingroup$ @hexomino Yes, we randomly choose integers and end points are included. $\endgroup$
    – Eric
    Dec 9, 2023 at 4:20

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
-3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ "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. $\endgroup$
    – tehtmi
    Dec 9, 2023 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.