What is the limiting probability distribution of a prime random walk This random walk has an infinite amount of possibility. these are the moves ranked most common to least $(\times 0+1,+1,\times2,\times3,\times5,\times7,\times11,\times13,\times17,\times19,\times23,\times29,...,\times P(n),...)$
the most common operation has a probability of 1/2, the second 1/4, the kth most common has a $1/(2^k)$ chance to happen.
So a possible walk would be $((((((1)\times0+1)+1)\times7)+1)\times2)$ the place it would have landed on would be $30$.
so let's say $P_m(k)$ is the probability that k is the end of an m step walk
I would like to know the limit as m goes to infinity or a good estimation for $f(k)$ $$f(k) = \lim_{m \to \infty} P_m(k)?$$
 A: This is an interesting question, and I'm unsure if there is a nice answer. However, we can note that the function $f$ satisfies the recurrence
$$f(k) = \frac14 f(k - 1) + \sum_{p | k} \frac{f(k / p)}{2^{m(p) + 2}}$$
where $p$ is a prime number and $p$ is the $m(p)$th prime number. For example, $m(2) = 1$ and $m(7) = 4$. This is because $P_m(k)$ satisfies the recurrence
$$f(k) = \frac14 P_{m-1}(k - 1) + \sum_{p | k} \frac{P_{m-1}(k / p)}{2^{m(p) + 2}}$$
and $P_{m - 1} \sim P_m$ in the limit of $m \to \infty$ (supposing that the limit $f(k)$ exists, of course).
Some properties that we can observe:

*

*For all $k$, $f(k) > 0$. This is due to the fact that no matter what state you are in, it's always possible to return to any other state (if you think of this as an infinite state space Markov chain, it is recurrent).


*$f(k)$ is generally decreasing (but not monotonically so). Your state is overwhelmingly likely to be a low number in the limit $m \to \infty$, as calculations can show that
$$f(1) = \lim_{m \to \infty} P_m(1) = 1/2, f(2) = 3/16, f(3) = 1/16, f(4) = 7/256$$


*Allowing $+1$ to be a transition makes $f(k)$ computationally intensive (at least with what I know) to compute, since $f(k)$ depends on $f(k - 1)$. (If you are interested in complexity theory, it seems that $f(k)$ probably cannot be calculated in polynomial time in the number of bits of $k$. But don't quote me on it.) On the other hand, if $+1$ was not an allowed state transition, then $f(k)$ would be quite easier to compute.
This is all I have for now; I'll try to see if an asymptotic expression of $f(k)$ can be obtained when I have time. Hope this helps!
