Collatz conjecture : The stochastic model of collatz sequences

This is the same contents as previous articles written in Japanese.

This article is NOT the proof of collatz conjecture, I constructed stochastic model of stopping times using Brownian motin model with constant drift.

Stopping times means operation times until natural number $n$ reaches 1.

We define $f(n)=3n+1, g(n)=n/2$ .

If $n$ is odd, the operation times increase by 2, if $n$ is even $g(n)$ operation times increase 1.

We assume the probability that f(n) and g(n) are even or odd is $\frac{1}{2}$ .

The variabe $x=\log(n)$ , "x" moves positive direction about $\log(\frac{3}{2})$ by probability 1/2, negative direction $\log(2)$ by probability 1/2.

First, we think about time "t" that "x" reaches "0" for the first time(first passage time).

We multiply scale factor $s=\frac{2}{\log(3)}$ ,

(Amount of positive direction movement)-(Amount of negative direction movement) =2 by f() or g() operation.

We define the rescaled variabe $X(n)=s\log(n)$ , and ommite "(n)" of $X(n)$ .

We approximate the movement of $X$ as Brownian motion with constant drift.Because $X$ drifts negative direction $v=\frac{s}{2}(\log(2)-\log(\frac{3}{2})=\frac{\log(\frac{4}{3})}{\log(3)}$ , and moves $\pm 1$ between $\Delta t=1$ .

We solve the first passage time of $-X$ in Brownian motion with negative constant drift.

Second, we derive the relation between the first passage time time "t " and stopping times $T_s$ .

We define the movement times to positive direction as $t_{+}$ , the negative movement times as $t_{-}$ .

$t_{-} + t_{+}=t$

$t_{-} - t_{+}+vt=X$

We deform

$t_{+}=\frac{(1+v)t-X}{2}$

$t_{-}=\frac{(1-v)t+X}{2}$

$t_{+}$ includes 2 steps, stopping times meet

$T_{s}=2t_{+} + t_{-}=\frac{(3+v)t-X}{2}$ eq.(1)

"t" confirms to inverse Gussian distribution, probability density function(PDF) is

$p(t)=\frac{X}{(2πt^3)^\frac{1}{2}}exp(-\frac{(X-vt)^2}{2t})$ .

https://en.m.wikipedia.org/wiki/Inverse_Gaussian_distribution

The expected value and variance of inverse Gussian distribution are

$E[t]=\frac{X}{v}$ , $V[t]=\frac{X}{v^3}$ , and by using epuation (1), we derive the formula,

$E[T_{s}]=\frac{3X}{2v}$

$V[T_{s}]=\frac{(3+v)^2X}{4v^3}$

$\frac{1}{n}\sum_{k=1}^{n}E_n[T_{s}]\sim\frac{3s}{2v}(\frac{X}{s}-1)$

We substitue epuation (1) to PDF and deform measure

$2dT_s=(3+v)dt$

, the PDF of stopping times is

$p_{X}(T_{s})=\frac{2(3+v)^{\frac{1}{2}}X}{(2\pi(2T_{s}+X)^3)^{\frac{1}{2}}}exp(-\frac{(3X-2vT_{s})^2}{2(3+v)(2T_{s}+X)})$

This epuation means the probability that stopping times $T_s$ is included in $[T_{s}, T_{s} + dT_{s}]$ is

$p_{X}(T_{s})dT_{s}$ .

We sum $p_X$ from 1 to $n$ , we derive the frequency distribution of stopping times $F(T_s)$ in $[1,n]$

$F(T_{s}) = \sum_{k = 1}^{n}p_{X}(T_{s})\sim\frac{1}{s}\int_{0}^{X}p_x(T_{s})exp(\frac{x}{s})dx$ eq.(2)

Next,we derive the formula of the maximum value of stopping times in $[1,n]$ by using the frequency distribution function.stopping times.

We define the maximum value of stopping times as $T_M$ .

In epuation (2), we convert $u=\frac{x}{T_s}$ ,

$\frac{\sqrt{T_s(s+v)}}{\sqrt{2\pi}s}\int_{0}^{X/T_s} \frac{u}{(u+2)^{3/2}}exp(T_s(- \frac{(3u-2v)^2}{2(3+v)(u+2)}+ \frac{u}{s})$ eq.(3)

First, we perform integration.

Considering $E[T_s]=\frac{3X}{2v}$ and $\frac{3}{2v}\sim 6$ , we find $T_s$ is learger than $X$ .

Then, we expand the primary term of "u" for integrand,

$\frac{u}{2\sqrt(2)}\exp(-\frac{T_sv^2}{3+v})\exp(T_s(\frac{3v}{3+v}-\frac{v^2}{2(3+v)}+\frac{1}{s})u)$

We define $\beta=\frac{3v}{3+v}+\frac{1}{s}-\frac{v^2}{2(3+v)}$ , we represent the integral,

$\exp(-\frac{v^2T_s}{3+v})\exp(\beta X) (\frac{X}{T_s}\frac{1}{\beta T_s}+\frac{1}{(T_s\beta)^2})-\frac{1}{(T_s\beta)^2})$

We consider about the case $T_s$ is learger than $O(10)$ , and considering $\beta\sim 1$ , we neglect 2nd and 3rd term.

Since the value of equation (3) at the maximum stopping times is O(1),

$\frac{-v^2}{(3+v)}T_s+\beta X-\frac{1}{2}\log(T_s)+\log(\frac{T_S}{X})\sim0$

We expand $T_M$ at $T_{M0}=\frac{(3+v)\beta X}{v^2}$ ,

$-\frac{v^2}{3+v}\Delta T_s\sim\frac{1}{2}\log{T_{M0}}+\log(\frac{T_{M0}}{X})$

Therefore,

$T_M\sim\frac{3+v}{v^2}(\beta X-\frac{1}{2}\log(\frac{(3+v)\beta X}{v^2})-\log(\frac{(3+v)\beta}{v^2}))$

$\gamma=\frac{3+v}{v^2}\beta=\frac{3}{v}+\frac{3+v}{sv^2}-\frac{1}{2}$

$T_M\sim\gamma X-\frac{3\gamma}{2\beta}\log(\gamma)-\frac{\gamma}{2\beta}log(X)$

Finaly, we consider about the maximum number of Collatz sequences in $[1,n]$ .

We define this number as $M$ .

In the Brownian motion with negative constant drift, the probability arriving Y>X from $X$

$p_n(Y)=\exp(-2v(Y-X(n)))$

We find the sum of $p_k(Y)$ from 1 to $n$ , the sum result represents the expected number that reaches $Y$ starting from $X\in [1,n]$ .

We deform the measure as

$dn=s\frac{dX}{n}$ , then

$\sum_{k=1}^{n}exp(-2v(Y-X(n))\sim\frac{1}{s}\int_{0}^{s\log(n)}exp(-2v(Y-X)+X/s)dX$

$\sim(2vs+1)exp(-2vY+(2vs+1)\log(n))$

eq(4)

If $Y$ equals to the maximum number of Collatz sequences in $[1,n]$ , the result of eq(4) is $O(1)$ .

Considering $Y=s\log(M)$ , we derive the formula,

$M\sim n^{1+\frac{1}{2vs}}$

趣味の研究

趣味の数学を公開しています。初めての方はaboutをご覧ください。

Collatz conjecture : The stochastic model of collatz sequences