4

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.

it's a hire car baby
  • 9,243
  • You might be interested in this picture at https://mathoverflow.net/a/200126/7710 which was made from that probability-estimates. – Gottfried Helms Sep 11 '17 at 09:12
  • @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. – it's a hire car baby Sep 11 '17 at 10:10

3 Answers3

2

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

reuns
  • 77,999
  • @RobertFrost $X_n = 1$ if $n$ is even, $X_n = 0$ otherwise – reuns Sep 10 '17 at 18:56
  • ok thank-you.... – it's a hire car baby Sep 10 '17 at 18:57
  • @RobertFrost anything unclear about why it is hard to randomize number theory conjectures ? – reuns Sep 10 '17 at 19:23
  • 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 https://math.stackexchange.com/questions/2357850/ at each step. It's not getting any simpler! – it's a hire car baby Sep 10 '17 at 19:32
  • @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) – reuns Sep 10 '17 at 19:38
  • The linked question gives a generating function for the number of divisions by 4 which will take place from one odd number to its odd successor when applying the Collatz function. – it's a hire car baby Sep 10 '17 at 20:42
  • @RobertFrost If you say so. Making things precises, making it clear why "this generating function" is trivial and hence useless is what you need. – reuns Sep 10 '17 at 21:00
  • P.s. thanks for the helpful answer. – it's a hire car baby Sep 10 '17 at 21:12
1

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.

davidlowryduda
  • 91,687
0

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.

kamal barghout
  • 11
  • 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 – Gottfried Helms Aug 12 '19 at 07:49