Un paseo aleatorio número teórico en los enteros

Question

Supongamos que un azar walker comienza a $S_0 = 2$, y camina de acuerdo a las siguientes probabilidades de transición:

• Si el caminante es en el $n$th el primer número $p_n$, ella se desplaza a $p_n + 1$ o $p_{n+1}$, con igual probabilidad.
• Si el caminante se encuentra en un número compuesto $x$, se traslada a uno de los principales factores de $x$, cada uno con una probabilidad de $1/\omega(x)$ donde $\omega(n)$ denota la número de distintos factores primos de a $n$.

Estoy interesado en la determinación de la cantidad de $\mathbb{P}(\sup_{n\ge 0} S_n = \infty)$. En particular, es esta probabilidad 1 o menor que 1? De forma heurística, hay muchas "trampas" para el caminante a perder el progreso que parece posible que la probabilidad será menor que 1. Por otro lado, el infinito es bastante tiempo, y siempre hay una probabilidad positiva, aunque pequeña, de ir más lejos que el punto más lejano alcanzado hasta ese momento.

Answer 1

Esta caminata aleatoria es altamente sesgada a la izquierda. Por el teorema de los números primos, $p_n$ crece asintóticamente como $n \ln n$, así que a partir de un primer número $p_n$, hay un $1/2$ de probabilidad de pasar a $p_{n+1}$ en un solo paso, que en promedio para los grandes números primos es un aumento de un factor de $\frac{(n+1) \ln(n+1)}{n \ln n} \approx 1+1/n$, mientras que con una probabilidad de $1/2$ en dos pasos se mueve a un número $\le \frac{p_n+1}2$, con una disminución del factor de $\le 1/2$. Esto demuestra que este paseo va a ser recurrente, pero ya que nunca se absorbe, la probabilidad de alcanzar o exceder el $N$-ésimo número primo, comenzando en cualquier lugar, siempre es $\ge 2^{-N}>0$, por lo que por la ley de los grandes números esto ocurrirá casi sin duda, infinitamente a menudo, y por lo $\sup S_n = \infty$ casi seguramente.