Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A long time ago I was messing around with the Collatz problem and I stumbled across a "proof" that the iterations will converge. I was too embarrassed to show anyone, and I recently just remembered it. So I will put a sketch of it here and I want to know where it falls down. Define $C(n)$ as one iteration of the Collatz function on a positive integer $n$. Assume we start at a random positive even integer $n$. Define the probability that $C(n)$ is even by $P(C(n)\in Even)$, or just $P(C(n))$. For a random start number $P(C(n))=0.5$. (remember n is even)

But $P(C^{2}(n))=1/2\times P((C(n))+ (1-P(C(n)))$. (By simple probability tree)

And so on, in general $P(C^{k}(n))=1/2\times P(C^{k-1}(n))+(1-P(C^{k-1}(n)))$ $=1-1/2\times P(C^{k-1}(n))$ Which gives us a geometric progression (with multiple -1/2) as we work our way back into terms of $P(C(n))$.

As $k \to \infty $, $P(C^{k}(n))\to \frac{1}{1-(-1/2)}=2/3$.

So what? Well, this implies that as k gets bigger our iterations will settle down to something like an even,even,odd cycle (2/3 are even). Assume that on k iterations of the Collatz function, we end up at a larger number than our initial number. This implies (assuming WLOG we have an even number, x) $3\times \frac{x}{4}+1$ is greater than $x$. Or, $x<4$. But we have checked for all numbers less than four and the Collatz function converges, so there is no number that will diverge.

I know this is a very sketchy sketch of a "proof". I just want to know what you think. If it is nonsense please say so.

Edit: I also tried a different Collatz style iteration, with $3x-1$ instead of $3x+1$. As is observable this doesn't seem to converge. Using the same arguments as my original question, we can see why. $3\times \frac{x}{4}-1$ is greater than $x$ when $x<-4$.

I also tried similar other changes using $3x+a$ for $a\in {3,5,7,...}$. If the iterations converge for all integers less than $4\times a$ then it is convergent for all (assuming my "proof" makes sense)

Second Edit: I want to reply to some issues raised. Bare in mind this is not a formal proof, it's just an idea of a way of making a proof.

On the objection that, just because on average the iterations will yield a 2/3 chance of an even number, there may in fact be sequences that do not reduce to an even-even-odd sequence:

If a particular sequence doesn't end in a 2/3 chance of an even number, and in fact it contains more odd numbers, then (now I'm not sure how to say this mathematically) that sequence is as dense in the integers as the sequences that cycle to 1-4-2, as for any even number in the sequence there is an infinite number of even numbers that also join this sequence (i.e. just double any even number in the sequence again and again...).

Therefore since the average sequence ends in a 2/3 chance of an even number after $k\to \infty$ iterations, there must be a sequence that has a higher than 2/3 chance of yielding an even number. I cannot prove it yet but I think, just on considering it, that such a sequence cannot exist, because:

  • as the sequence progresses the numbers would get smaller and smaller (e.g. if the prob of an even number is 3/4 then we can consider a even-even-even-odd sequence, which is the same as a even-even-odd sequence but with an extra division by two, so it would necessarily be smaller than the starting number. Meaning (a) it couldn't cycle (b) it couldn't diverge to infinity. i.e. it is impossible.

(BTW the above type of proof I'm trying to make is based on a type of proof I forget the name of - if the average of something is x, but you can find something with a value less than x, then there must exist an object with a value greater than x.)

On the objection that I am abusing the term probability and that this is akin to saying "there are no primes, because as we get to bigger and bigger numbers the probability of a certain number being prime approaches zero:

I think that, although I haven't defined how I'm using probability axioms, I think saying $C(n)$ can either be even or odd, and given an arbitrary $n$ it is possible to talk about the probability of it being even. If $C(n)$ is even, then $C(n+2)$ is odd so it doesn't matter where you are in the integers, the probability is always 1/2. I'm not sure why this is controversial.

share|improve this question
    
Two problems I see right off the bat: 1. The probability that $C^k(n)$ depends on $C^{k-1}(n)$ in a more complicated manner then simply on whether $C^{k-1}(n)$ is even or not. 2. Just because the probability that any given number will not enter some cycle other than 4-2-1 or diverge is low doesn't mean that no number will. –  Alex Becker Dec 30 '11 at 4:44
    
Thanks for the reply. (1) I dont think it does depend on anything more complicated. Assume arbitrary positive integer n. Draw a probability tree for yourself. SInce no other information about n is known, we don't need to consider anything else. I'll have a think about (2). –  JJG Dec 30 '11 at 4:48
    
Looks like an original approach. But not sure whether probability helps us out in making claims like "so there is no number that will diverge". –  Roupam Ghosh Dec 30 '11 at 4:48
3  
P_Q/JJG: I flagged for moderator attention. The merging of your accounts should be taken care of shortly. –  t.b. Dec 30 '11 at 5:02
2  
When you're saying "probability" of an even number is $\frac{1}{2}$, in the same spirit the "probability" of a prime number is 0 (they occur less and less often), and yet there are infinitely many prime numbers. In other words, low "probability" does not mean much. To talk about real probability, you need to define it with probability axioms. –  sdcvvc Dec 30 '11 at 5:51
show 6 more comments

2 Answers

One problem with your approach is that a probabilistic argument doesn't let you do much of anything with the statement about the behavior of all natural numbers as the Collatz rule is iterated. For example, there are infinite increasing sequences of natural numbers such that the probability that a natural number between $1$ and $n$ is among this sequence goes to $0$. But there is also another flaw in your approach, which is that you calculate $P(C^k(n))$ as if it only depended on $P(C^{k-1})$. According to your formula $$P(C^3(n)) = 1-1/2\times P(C^2(n)) = 1-1/2\times (1-1/2\times P(C(n))) = 1-1/2\times(1-1/4)=5/8$$ meaning that $P(C^3(n))$ does not depend on whether or not $C(n)$ is odd. This seems reasonable on the surface, as you would expect $\frac{3C(n)+1}{2}$ to be even just as often as it is odd (which is the assumption being made). However, this is not necessarily the case (I believe it to be false, and if it is true it certainly requires lots of justification), as the values produced by the Collatz iteration are not evenly distributed (for example, powers of two show up a lot), so we cannot use that this is true for evenly distributed $C(n)$ (note that since you are inducting, $C(n)$ may have gone through many Collatz iterations). If you are still not convinced, there is another stumbling block due to a property of the distribution of prime numbers called Chebyshev's bias. $\frac{3C(n)+1}{2}\cong 0\mod 2$ iff $C(n)\cong 1\mod 4$, which requires that $C(n)$ have an even number of prime factors congruent to $3\mod 4$. But Chebyshev's bias indicates that more of its factors are probably congruent to $3\mod 4$ than to $1\mod 4$, meaning we would expect the probability that $\frac{3C(n)+1}{2}\cong 0\mod 2$ not to conform nicely to $1/2$ (and it wouldn't stick to one side either, but fluctuate) even if we appeal to a distribution based on factors rather than size. This is but one of the many examples of complications in the distribution of primes and factors that make any inductive statement like yours impossible to make. The sequence $C(n)\mod 2,C^2(n)\mod 2,\ldots$ simply gives too much information about the upcoming terms $\mod 2$ to be ignored, yet the information is too subtle at present for us to account for.

share|improve this answer
    
I would like to offer a thought experiment: If you pick one thousand positive even integers randomly and do one iteration, $C(n)$ of each, then on average, half the results will be even. If you do this again $C^{2}(n)$ then 5/8 will be even, and so on. As you keep going, I think you will find that the average settles at 2/3. I don't think Chebyshev's inequality matters, as that is asking a different question. –  JJG Dec 30 '11 at 10:55
    
@JJG But if you randomly pick one thousand results of ten iterations of the $C$ function, the behave very very differently, which is the heart of my objection to your approach. The reason you need to consider numbers that have gone through the $C$ function many times is because you are using induction to prove your formula for $C^k$ for arbitrary $k$. –  Alex Becker Dec 30 '11 at 18:10
add comment

At first sight, this heuristic approach looks very similar to a "random walk argument" that has been proposed by Randall, cf paragraph 3 of this paper, or here for a short exposition.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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