A prime number random walk

Question

This question came to my mind thanks to this question which I found really interesting (and beautiful! Like the mathematician Philippe Caldero said in his book Histoires Hédonistes de Groupes et de Géométries (roughly translated) "Let us stop for a moment to contemplate the beauty of mathematics, that is after all the point of figures".).

It is also related to this other question.

---

The idea is to perform a walk following the following rules:

• Initialisation: You start on the point $(0,0)$ which correspond to the integer $n=0$, and you will walk from one point of $\mathbb Z^2$ to another. You start by walking on the right.

• Each horizontal step you take increases the integer $n$ by $1$.

• When $n$ is equal to a prime number, you take one step up, and you change the direction you were going to (if you were walking from left to right you will walk from right to left, and reciprocally).

To illustrate the rules, a drawing will perhaps be more explicit:

$$\begin{matrix} & 7 & 8 & 9 & 10\\ & 7 & 6 & 5 \\ & 3 & 4 & 5 \\ & 3 & 2 & \\ 0&1&2& & \end{matrix}$$

Or with blue lines:

---

Well now nothing stops us from going a little further, which we will do until $n=100$, and then until $n=1\,000$.

It seems that the walk is almost always on the right side of the $y$-axis. Though the walk is crossing the axis a few times.

Let us walk until $n=10\,000$.

Then we realise that we have completely changing the side of the axis we were walking on.

Which rises some questions:

• Will we cross the $y$-axis infinitely many times?

• Will we be walking as much on each side of the plane? In the sense that if we denote by $L_n$ the set of integers less or equals to $n$ on the left side of the plane and $R_n$ the set of integers less or equals to $n$ on the left side of the plane:

$$\lim_{n\to\infty} \frac {L_n}n=\lim_{n\to\infty} \frac {R_n}n=\frac 12.$$

• Will we walk out of any fixed vertical band centred on the $y$-axis?

Though any other result, or drawing (I did not succeed in drawing it for $n=10^5$), references about this walk would be of great interest.

Answer 1

Will we walk arbitrarily far off the y-axis?

Yes, because there are arbitrarily long gaps between consecutive primes.

---

For every gap $n\in\mathbb{N}$, there is a sequence of $n-1$ consecutive numbers, none of which is prime:

$$n!+2,n!+3,\dots,n!+n$$

In other words, there is no finite bound on the gap between two consecutive primes.

Hence there is no limit as to how far off the y-axis your illustration goes...

Answer 2

Some more graphs:

Up to $n=100000 = 10^5$:

Up to $n=1000000 = 10^6$:

Up to $n=10000000 = 10^7$:

Up to $n=100000000 = 10^8$:

And finally, up to $n=1000000000 = 10^9$:

Answer 3

Will we cross the $y$-axis infinitely many times?

Firstly, Let's lay out the assumptions related to this.

• There are infinitely many primes.
• The spacing between primes is Arbitrary.

Given that both of these are true, the answer is Yes for any point along the $x$ axis.

Given infinite time, and an infinite random walk left or right, any walk will eventually pass through any point.

EDIT:

Any walk which exists in a single axis, in this case, the $x$, will pass through any value of $x$ an infinite amount of times, given infinite time.

Assume the target $x=0$, where the walk is currently at $x=1$. The walk, has a $1/2$ chance to either, cross the $x=0$ within the next move.

But we need the chance that $x$ will ever cross $0$ again.

The percent chance for $x=2$ to reach $0$, within two turns, is $1/4$, which means that $x=1$ has, at least, a $1/2+1/4=3/4$ chance to successfully cross the $0$ in 3 turns.

As such, the chances that $x$ will be $0$ in exactly $x$ turns are $1/2^x$

This means that $x\to\inf$, $p\to0$ where $p$ is the chance that $x$ will equal $0$ in exactly $x$ moves.

$x$ cannot be $\inf$, so $p>0$. There is always a chance, and there are infinite tries. Even after failing,there's a 50% chance that your odds increase.

Thus, a Random Walk, given infinite time, will cross $x=0$, infinite times.

This Applies to Prime Gaps.

In this case, the Prime Gaps are just a random walk which changes direction at a Prime.

Below is a diagram showing how the Prime Walk (Blue) and Random Walk (Red) compare for values up to $y=500$.

Even though the Prime walk is strongly biased towards smaller numbers, there is no known maximum distance between prime gaps which means there is a chance, albeit an even smaller than normal, yet a non-zero chance that the next prime is far enough away to $x\le0$.

Of course, this proof is destroyed if Primes are either Proven non-infinite, against current proofs, or predictable.