4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You might be interested in this picture at mathoverflow.net/a/200126/7710 which was made from that probability-estimates. $\endgroup$ Commented Sep 11, 2017 at 9:12
  • $\begingroup$ @GottfriedHelms thanks. Yes that is potentially interesting. You know that the orbit of the $4x+1$ function under composition is at the heart of the problem. And the fact that the orbit of the function $f(x)=3x+2^{v_2(x)}$ is orthogonal to it in $\mathbb{N}_2^{\times}\setminus 1$. But my p-adic calculus is inadequate at the moment to go further. $\endgroup$ Commented Sep 11, 2017 at 10:10

3 Answers 3

2
$\begingroup$

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$"

$\endgroup$
8
  • $\begingroup$ @RobertFrost $X_n = 1$ if $n$ is even, $X_n = 0$ otherwise $\endgroup$
    – reuns
    Commented Sep 10, 2017 at 18:56
  • $\begingroup$ ok thank-you.... $\endgroup$ Commented Sep 10, 2017 at 18:57
  • $\begingroup$ @RobertFrost anything unclear about why it is hard to randomize number theory conjectures ? $\endgroup$
    – reuns
    Commented Sep 10, 2017 at 19:23
  • $\begingroup$ Well I should start by saying I knew it would be hard. We need to replace independence of $X_n$ with the sequences of divisions by $2$. Which are described by this generating function math.stackexchange.com/questions/2357850 at each step. It's not getting any simpler! $\endgroup$ Commented Sep 10, 2017 at 19:32
  • $\begingroup$ @RobertFrost Your linked question is very unclear. You meant $y = 2^l (2m+1) +1$. And in this question here you didn't make precise your statements (you would have seen what mixedmaths said) $\endgroup$
    – reuns
    Commented Sep 10, 2017 at 19:38
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The bit we don't know so much about is the way the function $3x+2^{v_2(x)}$ navigates through the ruler sequence $2^{v_2(x)}$. $\endgroup$ Commented Sep 10, 2017 at 20:50
0
$\begingroup$

The convergence of the Collatz conjecture has already been proved probabilistically. Please see: https://doi.org/10.1155/2019/6814378 . The approach is really simple and straight forward. The new approach towards probabilistic proof of the convergence of the Collatz conjecture is described via identifying a sequential correlation of even natural numbers by divisions by 2 that follows a recurrent pattern of the form 𝑥, 1, 𝑥, 1 . . ., where 𝑥 represents divisions by 2 more than once. The sequence presents a probability of 50:50 of division by 2 more than once as opposed to division by 2 once over the even natural numbers.The sequence also gives the same 50:50 probability of consecutive Collatz even elements when counted for division by 2 more than once as opposed to division by 2 once and a ratio of 3:1. Considering Collatz function producing random numbers and over sufficient number of iterations, this probability distribution produces numbers in descending order that lead to the convergence of the Collatz function to 1, assuming that the only cycle of the function is 1-4-2-1. In other words, starting with an odd number,the function produces a random even integer on the even positive integers, which in tern either will be divisible by 2 once or more than once with probability 50:50 and higher counts for division by 2 more than once for all even integers to infinity, which leads to convergence of the function. This is clear since division by 2 once increases the start odd number while division by 2 more than once decreases it.

$\endgroup$
1
  • $\begingroup$ Very nice to see you expanded your previous comment by the line of thoughts. The sun is on my head so I've difficulties to really perceive what you've written here, anyway for the effort of the newcomer: upvote $\endgroup$ Commented Aug 12, 2019 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .