Definir la función $$f(4n)=6n+1\\ f(4n+1)=6n+2\\ f(4n+2)=6n+3\\ f(4n+3)=6n+5$$ y la secuencia $u_0=2$ , $u_{k+1}=f(u_k)$ .
Dejemos que $d_1\le d_2$ sean la densidad asintótica inferior y superior de los números Impares en $u_k$ .
Desde $f(n)$ es impar para incluso $n$ no hay dos términos consecutivos que puedan ser tan evidentes $d_1\ge 1/2$ . Experimentalmente, parece razonable conjeturar $d=d_1=d_2=2/3$ .
Heurísticamente, cuando $n$ es impar, $f(n)$ tiene "probabilidad 1/2" de ser par, por lo que obtenemos esta cadena de Markov:
que es coherente con $d=2/3$ . Pero, ¿podemos demostrar rigurosamente que la heurística funciona, es decir, que $u_k$ ¿es lo suficientemente aleatorio para que esto sea cierto? En su defecto, un límite inferior más agudo en $d_1$ podría ser un resultado interesante.
(Un enfoque podría ser dejar que $a_k=1$ si $u_k$ es par y $0$ de lo contrario, y examinar las probabilidades del $p$ -subpalabras de bits $(a_k,\dots,a_{k+p-1})$ . Por desgracia, todas las palabras de Fibonacci, es decir, las que no contienen el patrón 11, parecen aparecer con una frecuencia infinita en $a_k$ . Esto es coherente con el modelo de cadena de Markov).
PD: Si te lo preguntas, el problema surgió de esta pregunta .
Respuesta a los comentarios:
- Alguien sugirió trabajar en módulo con algún número mayor, como el 12. El problema con este enfoque es que si la entrada se considera mod $2^a 3^b$ , la salida sólo se conocerá mod $2^{a-1} 3^{b+1}$ por lo que no vas a poder decir mucho sobre el comportamiento de $f$ al iterar más de $a$ tiempos. Y parece que $010101\dots$ siempre puede aparecer como una subpalabra de $a_k$ Así que no podrás demostrar nada que no sea trivial sobre la densidad demostrando algo sobre la densidad después de $k$ iteraciones partiendo de un estado arbitrario (es decir, examinando $f^k$ para un límite de $k$ ).
- Los primeros términos son 2, 3, 5, 8, 13, 20, 31, 47, 71, 107, 161, 242. La secuencia crece como $\Theta((3/2)^n)$ . Es interesante observar cómo los primeros términos coinciden con la secuencia de Fibonacci (lo que puede explicarse por la cercanía de $3/2$ es a la proporción áurea y por el hecho de que módulo 2, ninguna de las dos secuencias contiene el patrón 00).
