La probabilidad y el Problema de Collatz

Question

Hace mucho tiempo yo estaba jugando con el problema de Collatz y me topé con una "prueba" de que las iteraciones convergen. Yo estaba demasiado avergonzado para mostrar a nadie, y yo recientemente acabo de recordar. Así que voy a poner un bosquejo de aquí y quiero saber donde cae hacia abajo. Definir $C(n)$ como una iteración de la función de Collatz en un entero positivo $n$. Suponemos que de inicio al azar positivo incluso entero $n$. Definir la probabilidad de que $C(n)$ es incluso por $P(C(n)\in Even)$, o sólo $P(C(n))$. Para un arranque aleatorio número $P(C(n))=0.5$. (recuerde que n es impar)

Pero $P(C^{2}(n))=1/2\times P((C(n))+ (1-P(C(n)))$. (Por simple probabilidad de árbol)

Y así sucesivamente, en 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))$ Lo que nos da una progresión geométrica (con múltiples -1/2) como trabajamos nuestro camino de regreso en términos de $P(C(n))$.

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

Entonces, ¿qué? Bien, esto implica que a medida que k crece nuestra iteraciones se establecen a algo así como un par,impar ciclo (2/3). Suponga que en k iteraciones de la función de Collatz, terminamos en un número mayor que el de nuestro primer número. Esto implica (suponiendo WLOG tenemos un número par, x) $3\times \frac{x}{4}+1$ es mayor que $x$. O, $x<4$. Pero hemos comprobado para todos los números menos de cuatro y la Collatz función converge, así que no hay ningún número que van a divergir.

Sé que este es un boceto boceto de una "prueba". Sólo quiero saber lo que usted piensa. Si es una tontería, por favor decirlo.

Edit: también he probado diferentes Collatz estilo iteración, con $3x-1$ en lugar de $3x+1$. Como es observable, esto no parecen converger. Utilizando los mismos argumentos que mi pregunta original, podemos ver por qué. $3\times \frac{x}{4}-1$ es mayor que $x$ al $x<-4$.

También traté de similares otros cambios de uso$3x+a$$a\in {3,5,7,...}$. Si las iteraciones convergen para todos los valores enteros menos de $4\times a$ entonces es convergente para todos (suponiendo que mi "prueba" tiene sentido)

Segunda Edición: Quiero responder a algunas de las cuestiones planteadas. Ten en cuenta que esto no es una prueba formal, es sólo una idea de una manera de hacer una prueba.

Sobre la objeción de que, simplemente porque, en promedio, las iteraciones producirá un 2/3 de probabilidad de un número, puede ser, de hecho, secuencias que no se reducen a un par-impar secuencia:

Si una secuencia particular no termina en un 2/3 de probabilidad de un número par, y en el hecho de que contiene más de números impares, entonces (ahora no estoy seguro de cómo decir esto matemáticamente) que la secuencia es tan densa en los enteros como las secuencias que el ciclo de 1-4-2, como para cualquier número en la secuencia hay un número infinito de números que también se unen a esta secuencia (es decir, exactamente el doble de cualquier número en la secuencia una y otra vez...).

Por lo tanto, dado que el promedio de la secuencia termina en un 2/3 de probabilidad de un número después de $k\to \infty$ iteraciones, debe haber una secuencia que tiene más de 2/3 de probabilidad de obtener un número par. No puedo probarlo aún , pero creo que, sólo en la consideración de que es así, que una secuencia no puede existir, porque:

• como la secuencia de progresa, los números se hacen más pequeños y más pequeños (por ejemplo, si la prob de que un número par es de 3/4, a continuación, se puede considerar un aún-incluso-par-impar secuencia, que es el mismo que el de un even-par-impar secuencia, pero con un extra de la división por dos, por lo que no tendría que ser necesariamente menor que el número de partida. Significado (a) que no podía ciclo (b) no diverge a infinito. es decir, es imposible.

(Por CIERTO, el anterior tipo de prueba que estoy tratando de hacer que se basa en un tipo de prueba de que se me olvide el nombre de - si el promedio de algo es x, pero se puede encontrar algo con un valor inferior a x, entonces debe existir un objeto con un valor mayor que x.)

Sobre la objeción de que estoy abusando del término probabilidad y que esto es similar a decir "no existen números primos, ya que, al llegar a más y más números, la probabilidad de que un cierto número de primos se aproxima a cero:

Creo que, aunque yo no lo he definido cómo estoy usando axiomas de probabilidad, creo que decir $C(n)$ puede ser par o impar, y debido a un arbitrario $n$ es posible hablar de la probabilidad de que incluso. Si $C(n)$ es incluso, a continuación, $C(n+2)$ es extraño por lo tanto no importa dónde usted está en los números enteros, la probabilidad siempre es 1/2. No estoy seguro de por qué esto es controversial.

Answer 1

Uno de los problemas de su enfoque es que un argumento probabilístico no te deja hacer nada de nada con la declaración sobre el comportamiento de todos los números naturales como la Collatz regla es iterado. Por ejemplo, hay infinidad de aumento de las secuencias de números naturales tales que la probabilidad de que un número natural entre el $1$ $n$ es entre esta secuencia va a $0$. Pero también hay otro fallo en su sistema de enfoque, que es que usted calcula el $P(C^k(n))$ como si sólo dependiera de $P(C^{k-1})$. De acuerdo a la fórmula $$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$ para ser ignorado, sin embargo la información es demasiado sutil en la actualidad, nos cuenta.

Answer 2

A primera vista, esta aproximación heurística se ve muy similar a un "paseo aleatorio argumento" que ha sido propuesto por Randall, cf párrafo 3 de este artículo, o aquí para una breve exposición.

Answer 3

Además, ¿qué podemos hacer ? (por supuesto, si su estimación de la asintótica de la frecuencia relativa de los números dentro de la secuencia de Collatz $\{ C^k(n):k \in N\}$ es válido para cada una de las $n \in N$) -Esta una idea de por qué debemos continuar la prueba: Vamos a tomar cualquier número natural $n$. Supongamos que tenemos que $$\lim_{m \to \infty}\frac{\#(\{C(n),C^2(n),\cdots, C^m(n)\}\cap 2N)} {m}=2/3.$$ Then there is a natural number $M$ que $$\frac{\#(\{C(n),C^2(n),\cdots, C^M(n)\}\cap 2N)} {M} \approx 2/3.$$ The latter relation means that $C^M(n)$ approximately is obtained from $n$ multiplied on $(1/2)$ --${M\times (2/3)}$-times and on $(3)$-- ${M\times (1/3)}$-times, i.e. $$C^M(n)\approx n\times (1/2)^{M\times (2/3)}\times (3)^{M\times (1/3)}=n\times (1/4)^{M\times (1/3)}\times (3)^{M\times (1/3)}=n\times (3/4)^{M\times (1/3)}.$$ But this is valid for some increasing subsequence $(M_k)_{k \N}$ which tends to infty. But $$ \lim_{k \to \infty} n\times (3/4)^{M_k\times (1/3)}=0.$$ Hence we can choose such $k_0$ that the number $n\times (3/4)^{M_k\times (1/3)}$, and correspondingly $C^{M_{k_0}}(n)$ will be in an interval $[1,A]$ para que la conjetura de Collatz es comprobado y es válido.