2022.03.28 MATH 3600 Random 3n+1

96 days ago by calkin

Let us think about modeling the 3n+1 problem as a random process.

How does the 3n+1 process work? If we see an even number we divide it by 2.

If we see an odd number, we multiply by 3 and add 1. Since the result is even, we must then divide by 2.

So, let's replace f(n) by a new function g(n). 

Define $g(n) = n/2$ if $n$ is even, and $g(n)=(3n+1)/2$ if $n$ is odd.

It should be clear that iterating $f$ goes to 1 if and only if iterating $g$ goes to 1.

Instead of asking how many steps f takes, we can ask how many steps g takes.

Modeling this.  We could start with a real number $Y$, and with equal probability, divide it by 2,

or multiply by 3 and add 1, and divide by 2, and ask whether we ever get below 1.

Multiplicative process are a bit tricky to model, and the "add 1" part messes this up a bit.

Simpler model: start with a real number Y, and with equal probability, replace Y by Y/2 or 3Y/2.

Ask how long before we end up less than 1.

Now, if we consider $X=\log(Y)$, we get a new random process.

Start with a real value $X$, and with equal probability replace $X$ by $X - \log(2)$ or by $X+\log(3/2)$.  Now we want to ask how long it takes before we go past 0.

So we see that we are either going down by about 0.693 or up by about 0.405.

On average, each step averages out to going down by about 0.288.

So, to go from an initial value $X$ to 0 will probably take something like $X/0.288$ steps.

This model suggests that the "average" number of steps $g$ should take to go from a starting value $n$ to 1 should be about \[\frac{\log(n)}{\log(4/3)}.\]

Project: code $g()$ and compute how long it takes to reach 1.  Plot the results and compare with \[\frac{\log(n)}{\log(4/3)}.\]

If we toss a fair coin $N$ times, how many heads will we see?

The probability that we see exactly $k$ heads is \[\binom{N}{k}2^{-N}\]

So the probability that we see at least $M$ heads is 

\[ \sum_{k\geq M} \binom{N}{k} 2^{-N}  \]

What does this look like?  Let us plot it.

def manyheads(k,N): manyheads_prob=0. # This is the probability that we see at least k heads for i in srange(k,N+1): manyheads_prob+= binomial(N,i)*2^(-N) return(manyheads_prob) 
N=1000 manyheads_list=[] for k in srange(0, N+1): manyheads_list.append([k,manyheads(k,N)]) list_plot(manyheads_list) 

We could now ask the question: what is the maximum number of steps we expect to take before $X$ gets below 0?  Also, what is the minimum number of steps?  How do these answers compare to how $g(n)$ behaves?