The limiting probability distribution of a prime random walk

markov chainsprime numbersprobabilityrandom 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)?$$

Best Answer

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!

Related Solutions

[Math] Small primes attract large primes

The phenomenon you describe seems to be the concept behind the Sieve of Eratosthenes.

Every number below $ \sqrt{N} $ where $ N $ is the number you want to factorize will appear at least once in the list of possible factors. Looking at the list generated by the Sieve, it will become obvious that only primes remain. A factorization using the Sieve then implies trial division by the primes up to $ \sqrt{N}$. This concept lets us see that obviously, if "many" small primes were used to remove elements in the Sieve, the remaining elements will have larger prime factors, possibly being primes themselves.

However: no generalization of any kind is possible, since every number's occurence is cyclic. Think of a Fourier Transform , using prime factors as frequencies. 2 appears every second number, 3 every third and so on. At any point $N$, there is no way to determine if there are primes nearby of if the numbers nearby will have "large primes" as factors without it's value.

I could also relate what you're saying to the concept of Mersenne Primes. Essentially, primes in the form $2^{n}–1$ the largest known being $(2^{43,112,609} – 1)$, which also happens to be the largest prime known. In this case, they are looking for primes in the viscinity of exponents of 2, which is also saying the that largest factor is a large prime, right?

So yes, it stands to reason that if $N$ isn't a prime and has small factors, numbers nearby have a chance to have greater factors. No quantification of that is useful, however.

Probability that random walk returns to starting vertex in at most 20 moves

The values $k\leq 20$ aren't too big to brute force. Because you need to come back, you only have to consider the graph up to $\frac{k}{2}$ distance to the origin. Then remove the origin and for each pair of neighbors of the origin count $k-2$-walks on that graph starting from first and ending in second. Sum those up and that's your answer. We get

2 :  3
4 :  6
6 :  30
8 :  180
10 :  1188
12 :  8322
14 :  60714
16 :  456174
18 :  3504630
20 :  27398106

Here's the Sage code I used:

def f(k):
    if k<2: return 0
    g = Graph()
    lim = k//2
    for y in range(-lim, lim+1):
        for x in range(-lim, lim+1):
            g.add_edge((x,y), (x+1, y))
            if (x+y)%2==0: g.add_edge((x,y), (x,y-1))
    g.delete_vertex((0,0))
    vs = list(g.vertices())
    origNbs = [vs.index(v) for v in [(-1,0), (1,0), (0,-1)]]
    A = g.adjacency_matrix()
    A = A^(k-2)
    return sum(A[vI][vJ] for vI in origNbs for vJ in origNbs)

for k in range(2, 21, 2):
    print (k, ": ", f(k))

I'm probably exaggerating on the $y$-range because you need two steps to move a level, but it's not too slow even like that.

Best Answer

Related Solutions

[Math] Small primes attract large primes

Probability that random walk returns to starting vertex in at most 20 moves

Related Question