Collatz meets Markov: a Different Look at an Old Impossible Problem

4 November 2018 (Edited for flow)

This is a quick popular write up about an interesting take on the Collatz conjecture. It's meant to be understood by people who competed in maths Olympiads in high school. This is also known as the '3n +1' problem and the simplest impossible problem. I intend to have a technical write up on arXiv soon for my peers.

First, the Rules:

Pick any natural number greater than 0
Rules:
    If number is even, divide by 2
    If number is odd, multiply by 3 and plus 1
    Repeat Rules

Take the Rules for a test drive, go ahead! I've done this and plotted the result in the main picture.

You should find something very interesting within a short while. If you keep following the rules for long enough; you should find that you settle into the sequence 1,4,2,1,4,2 and so on.

Congratulations, you will have observed some evidence for the Collatz conjecture. He believed that this will always happen but couldn't prove it. To date, no one has managed to do it and they have thrown everything at this problem, including crowd sourcing computers. For a very good (fairly) recent summary on results so far, see Professor Lagarias' work.

Whilst preparing a more in depth article (to follow this), I found a really cool result. After scouring the existing knowledge, it looks like the result may be novel. I borrowed the tools from applied probability theory to answer this question; which has no random variables in it whatsoever!

In English: By looking at a large collection of natural numbers at arms length, a lovely pattern arises. Kind of like how you see those 3D images in those stereograms when you un-focus your eyes.

Before presenting my take, we turn to a very important man who made this problem famous, Paul Erdos.

Paul who?

In case you don't know, Paul Erdos was Brilliant, with a capital 'B'. Paul Erdos was so brilliant, it is a mark of pride and a badge of honour to have written a paper with him. He was so brilliant, it is a mark of pride to have written a paper with someone who wrote a paper with someone who wrote a paper with someone who wrote a paper with him. He's really brilliant is what I am saying.

You keep score of how cool you are with your Erdos number. If you wrote a paper with Paul Erdos, you have an Erdos number of 1. If you wrote a paper with someone who wrote a paper with Paul, you have an Erdos number of 2.

Just so you know; I have a friend who has an Erdos number of 6.

Yes, I have friends who are that cool.

I do not have an Erdos number and no, I don't know why my friends accept me.

Back to Paul Erdos.

This is a guy who would eat, sleep and breathe mathematics. He LIVED for mathematics, dying only a few hours after solving a math problem in geometry at a conference. He has given us lots and lots and lots (over 1,500 papers) of really useful mathematics and he's the guy who offered 500 bucks for the person who could prove the conjecture.

Answer First

In English:

• If you grab a big bag of natural numbers, initially half will be even and half will be odd.
• When you apply the Rules once to these numbers, you will find one quarter of the new numbers in the bag are now odd and three quarters are even. (Try it!)
• Keep applying the Rules though and very soon, one third of the numbers in your bag will odd and two thirds will be even.
• This ratio of odd to even will not change; no matter how long you keep applying the rules.

These fractions become exactly true when we put all natural numbers in our bag (in sympathy with the law of large numbers for random variables).

Essentially, after a few initial applications of the Rules for all natural numbers X; we will '3 X plus 1' a third of all these and '1/2 X' the other two thirds of them.

We now use a property called ergodicity, which says whatever happens to the entire bag of numbers also happens to any given number you choose to follow as you apply the Rules. This is because all natural numbers are in our bag and the Rules clearly keep natural numbers, well, natural.

So, for any given natural number we pick; we will (over a long enough time frame) multiply it by 3 once for every two occasions we multiply it by 1/2. I'm deliberately ignoring the technical details about what happens to all the '+1's, this is big picture stuff here.

Since 3*1/2*1/2=3/4, we are effectively repeatedly multiplying each number by (3/4) over and over again when we consider lots of iterations. If we let the application of the rules be denoted as T(k) where k is a natural number; we are saying that

T(T(T(...T(T (k))) ~ k (3/4)^n + ...,

where we have applied T( ) a total of 3n times. The + ... is for the technical write up but the main idea is clearly presented here.

Hence, the numbers must keep getting smaller (for enough iterations n) and we will reach the 1,4,2... sequence if we keep applying the rules. This is true for all natural numbers since that is what we have in the bag.

Don't believe me? Have a look! Here, our bag of numbers contains all natural numbers from 1 to 1 Million in Figure 1. As predicted, one third of the numbers in the bag become odd. From there on our bag always contains one third odd numbers.

Figure 1: Fraction of Odd Natural Numbers after Repeated Application of the Rules (1 to 1,000,000)

This was calculated with code segment 1 and the python computer language. You can easily see that our predictions have been confirmed even when we do not include an infinite number of natural numbers.

As a cute little side note; see that 1,4,2,... is odd once and even twice, forever! So our assertion is true for the final sequence as well.

Repeated application of the Rules: Markov property

To be clear, there is no uncertainty or randomness here, we are merely looking at a big collection of natural numbers all at once. We are going to use a neat trick from probability theory applied to this really large collection of numbers and see what happens as you keep following the Rules.

The trick we will use is called the Markov property. It may sound scary but it is quite easy to understand when you look at the picture in Figure 2, which describes how it works.

Figure 2: Markov Model of Number Label under Transition Rules

Each circle in Figure 1 is a possible label for a number. Either a number is even or it is odd so these two labels represent all natural numbers for our purposes. The arrows represent a change of label when the Rules are applied. The numbers are the proportion of all numbers with that label which change their label as the Rules are applied. The Markov property is that a number changing its label depends only on what its current label is, it does not matter what its label was in the past.

We are stating in Figure 2 that every odd number becomes even when you apply the Rules. Also, half of all even numbers stay even and the other half become odd.

Time to show you how you to get this result.

Derivation of Markov model

Every odd number is given by 2k+1 where k is a positive integer. When you apply the Rules to this number you get,

3(2k + 1) + 1 = 6k + 4

Observe that this number is neatly divisible by 2 for all values of k. Hence, all odd numbers become even after a single application of the Rules, and this is the number on the arrow away from the odd label in Figure 2.

Every even number can be represented by 2k where k is a natural number. When you apply the Rules to even numbers you get,

(1/2) 2 k = k

which means that half of these new numbers are even and the other half are odd. This explains the two arrows pointing away from the even label in Figure 1. You should already be able to easily prove that half of all natural numbers are even and the other half are odd. So this is our starting position.

Equilibrium of the Markov model

Applying the Rules and then counting the labels is the same as updating the Markov model and watching the fractions of the labels change.

To update the Markov model, you only need to know how to multiply matrices. Google used what we'll do next to work out how to rank websites, so we are in good company.

Firstly, let the fraction of numbers in our bag which are even be given by fe and the fraction of integers which are odd be given by fo. Initially these will each be equal to 1/2 as previously stated.

Now,

fe' = (1/2) fe + fo

fo' = (1/2) fe

where fe' is the fraction of even numbers in the bag after a single application of the Rules, and similarly for fo'. In words, the first equation here says the new fraction of even numbers is equal to half the old fraction plus all of the odd fraction. The second equation says that the new fraction of odd numbers is equal to half the old even fraction.

These two equations are a direct translation from the arrows in Figure 2 and can be quickly solved iteratively using matrix multiplication. When you keep recursively applying these two equations with the initial condition of 1/2 each, you find the numbers settle down into,

fe* = 0.6666...

fo* = 0.3333...,

and we have the evidence for our main claim.

What this tells us is that, when you repeatedly apply the Rules to all of the natural numbers, eventually 1/3 of them will be odd and 2/3 of them will be even at any one instant.

To see that this equilibrium remains: the total number of new even numbers is equal to the the fraction of even numbers which stay even plus all of the fraction of odd numbers.

Mathematically this is fe* = (1/2) 2/3 + 1/3 = 2/3, so you can see fe* will remain this value forever once it attains it. Likewise f0* will remain equal to 1/3 forever since (1/2)2/3 = 1/3 which is the fraction of even numbers which become odd when you apply the Rules.

Python Code

Code segment 1: Fraction of odd integers after repeated application of the Rules

import pylab

#Transition function
def transF(x):
    #even
    if x % 2 == 0:
        return x//2
    else: return 3*x+1

#Return ratio of odd to total
def oddRatio(x):
    #odds
    nO = 0
    #Assuming a list is passed in
    for i in range(len(x)):
        if x[i] % 2 != 0:
            nO+=1
    return nO/len(x)

# All positive integers up to size
size=10**6
v = []
k= 1
for i in range(size):
    v.append(i+1)
    # Progress report
    if i == size//10*k:
        print(str(k*10)+'% done initialising')
        k+=1
    if i == size-1:
        print('Initialisation complete')

##Odd ratio vector
oR = []
##Initial ratio
oR.append(oddRatio(v))

# Iterations
N = 30
k= 1
#Simulation
for i in range(N):
    #Mapping
    for j in range(len(v)):
        v[j] = transF(v[j])
    ##Append new odd ratio
    oR.append(oddRatio(v))
     # Progress report
    if i == N//10*k:
        print(str(k*10)+'% done simulating')
        k+=1

# Plot ratio of odd numbers to total number
pylab.xlabel('Iterations')
pylab.ylabel('Odd Ratio')
pylab.plot(oR)
pylab.grid()
pylab.show()