# A number-theoretic random walk on the integers

Suppose a random walker starts at $S_0 = 2$, and walks according to the following transition probabilities:

• If the walker is on the $n$th prime number $p_n$, she moves to either $p_n + 1$ or $p_{n+1}$ with equal probability.
• If the walker is on a composite number $x$, she moves to one of the prime factors of $x$, each with probability $1/\omega(x)$, where $\omega(n)$ denotes the number of distinct prime factors of $n$.

I am interested in determining the quantity $\mathbb{P}(\sup_{n\ge 0} S_n = \infty)$. In particular, is this probability 1 or less than 1? Heuristically, there are so many "traps" for the walker to lose progress that it seems possible for the probability to be less than 1. On the other hand, infinity is quite a while, and there is always a positive chance, however small, of going further than the furthest point reached at up to that time.

This random walk is highly biased to the left. By the prime number theorem, $p_n$ grows asymptotically like $n \ln n$, so starting from a prime number $p_n$, there is a $1/2$ probability of moving to $p_{n+1}$ in one step, which on average for large primes is an increase of a factor of $\frac{(n+1) \ln(n+1)}{n \ln n} \approx 1+1/n$, whereas with probability $1/2$ in two steps it moves to a number $\le \frac{p_n+1}2$, a decrease of factor of $\le 1/2$. This shows that this walk will be recurrent, but since it never gets absorbed, the probability of reaching or exceeding the $N$-th prime number, starting anywhere, is always $\ge 2^{-N}>0$, so by the law of large numbers this will happen almost surely, infinitely often, and so $\sup S_n = \infty$ almost surely.