How might we approach Collatz Conjecture by probabilistic method?

Question

How might we approach Collatz Conjecture by probabilistic method - or similar?

I was thinking along the following lines. Suppose we select some integer at random. What is the expected value of the number that it converges to?

Am I right in thinking if so much as a single number converges to infinity, this would set the answer to infinity?

Therefore if we can prove the expected value is finite we have proven no sequence ascends infinitely. If we can prove the expected value is $>1$ there are nontrivial loops and if we can prove the expected value is $1$ we prove the conjecture in full.

We would have to define the lowest integer in some loop as the convergent point, or find some other general definition of the value of a loop.

Answer 1

Let $X_n = 1_{n \text{ is even}}$ so that $$f(n) = \frac{n}{2} X_n+\frac{3n+1}{2}(1-X_n)$$

Clearly it is not true, but you can assume the $X_n$ are independent random variables with $P(X_n=1) =P(X_n=0) =\frac{1}{2}$.

In that case for every $n$, the sequence $Y(k) = Y_n(k) = \underbrace{f \circ \ldots \circ f}_k(n)$ is bounded with probability $1$.

---

Note if we look instead at $g(n) = \frac{n}{2} X_n+(3n+1)(1-X_n)$ then the sequence grows without bound almost surely... So independence of the $X_n$ is really far from the truth.

---

Then you can compute the mean value and the variance of the random variable $Y_n(1),Y_n(2)$ and $Y_n(k)$ as well as $Z_K(n)=\max_{k \le K} Y_n(k)$. You'll get statement such as "with probability $p $, $\frac{Z_K(n)}{n} \le \epsilon$"

Answer 2

Up to some details, your intuition is correct. If we define the function $f(n)$ to mean the smallest number that occurs in the Collatz sequence starting from $n$, then the expected value of $f$ being greater than $1$ implies that the Collatz conjecture is false.

The challenge with this is that it is rather complicated to actually compute these expected values. The Collatz conjecture can be thought of as saying something about the relationship between the factors of $n$ and $3n+1$, and we don't know so much about this.