Studying the basic concepts about random walks / brownian motion, and based on the idea of a Möbius-based walk in Wolfram's website, I wanted to try my own version of it in Python to compare it with standard random walks, but adding some reset condition, and the results seemed intriguing.
Note: this question has been reformulated after reading the comment of Greg Martin (below).
This is the test:
Initial setup: in plane $xy$, starting point $(x,y)$ is $(0,0)$, the first element by default is $n=1$ whose associated point is $(1,0)$, and the last direction of movement was $R$, right, from (0,0) to (1,0).
Calculation of next direction: $\forall n\in\Bbb[2,\Bbb N]$, if $\mu(n)=-1$, turn left $90^o$, if $\mu(n)=1$, turn right $90^o$, if $\mu(n)=0$, go ahead.
The displacement is +1 in the calculated direction.
Reset condition ($R$): $n \in \Bbb P \to (0,0)$. If $n$ is prime, reset.
Tested with Python, this is how it looks like:
This is the last graph in detail, for $n\in[1,1000000]$
It seems very symmetric, the points in which a reset occurs seem symmetrically distributed around the center $(0,0)$ and the generated "mesh" of the Möbius walk seems also to cover symmetrically the area of the walk (no empty spaces).
Just to compare, this is how it looks like the same Möbius walk without the reset condition (looks more like a "standard" random walk):
Update: After reading the comment of Greg Martin, I did the same test instead of using the Möbius function, using a random generator that produces a number from $0$ to $9$, so now:
Calculation of next direction: $\forall n\in\Bbb[2,\Bbb N]$, if $rnd(1,9)\le 3$, turn left $90^o$, if $3\lt rnd(1,9)\le 6$, turn right $90^o$, if $6\lt rnd(1,9) \le 9$, go ahead.
And the pattern looks very similar, e.g. $[1,1000000]$:
Update 2015/07/31:
As explained in the comments, I did the same exercise in the question with a random generator and reset condition being a power of 2, and it is not symmetric. In the other hand e.g. if the reset condition is being a perfect square the result is symmetric. So I do not see clearly which sequences are symmetric and which sequences not. It seems that if the reset condition follows a specific kind of distribution then the result is symmetric and in other cases not.
It is the first time I see this kind of graph, the usual random walk graphs are not symmetrical. My theoretical knowledge is very basic, so if somebody could share some light about the reasons behind that shape would be very appreciated.
Why does this symmetry happens? the reset condition $R$ biases the results? Thank you!
This is the Python code in case somebody wants to reuse it:
def mbrw():
from sympy import mobius, factorint
from gmpy2 import is_prime, is_square
import matplotlib.pyplot as plt
import csv
from random import randint
def calc_dir(last_dir,mob):
if last_dir == "R":
if mob == -1:
return "U"
if mob == 0:
return "R"
if mob == 1:
return "D"
elif last_dir == "D":
if mob == -1:
return "R"
if mob == 0:
return "D"
if mob == 1:
return "L"
elif last_dir == "L":
if mob == -1:
return "D"
if mob == 0:
return "L"
if mob == 1:
return "U"
elif last_dir == "U":
if mob == -1:
return "L"
if mob == 0:
return "U"
if mob == 1:
return "R"
testlimit = 1000000
lox = []
loy = []
last_dir = "R"
is_first = True
for n in range (1,testlimit):
# Function used to decide the direction
#tmpval=mobius(n)
myrand = randint(1,9)
if myrand <=3:
tmpval = -1
elif myrand <=6:
tmpval = 0
else:
tmpval = 1
if is_first:
if n==1:
# Starting condition
last_dir = "R"
lox.append(0)
loy.append(0)
lox.append(1)
loy.append(0)
is_first = False
else:
# Calculation of next direction
last_dir = calc_dir(last_dir,tmpval)
nextx=0
nexty=0
# Displacement in the new direction
jumpvalue = 1
# Reset condition
if is_prime(n):
nextx=0
nexty=0
else:
# Calculation of next (x,y)
if last_dir=="R":
nextx=lox[n-1]+jumpvalue
nexty=loy[n-1]
elif last_dir=="D":
nextx=lox[n-1]
nexty=loy[n-1]-jumpvalue
elif last_dir=="L":
nextx=lox[n-1]-jumpvalue
nexty=loy[n-1]
elif last_dir=="U":
nextx=lox[n-1]
nexty=loy[n-1]+jumpvalue
lox.append(nextx)
loy.append(nexty)
plt.plot(lox,loy)
plt.show()
mbrw()
You haven't formalized what you mean by "the result is symmetric". The individual graphs are certainly not symmetric, you haven't specified a distribution whose symmetry we could inquire into, and if you had, it wouldn't be clear whether you could judge its symmetry by examining a couple of samples with the naked eye.
So presumably what you mean is roughly that the resulting graphs appear roughly symmetrical to the naked eye. If so, this can be explained. You used three different sequences for the reset: the primes, the squares, and the powers of two. The lengths of your random walks are determined by the gaps in these sequences. These gaps are of the order of $\log n$, $n$ and $2^n$, respectively. The distance that a random walk of length $l$ travels away from the origin goes as $\sqrt l$.
Thus, your walks end at distances of order $\sqrt{\log n}$, $\sqrt n$ and $2^{n/2}$ from the origin. Taking derivatives with respect to $n$ yields (up to logarithmic factors) $1/n$, $1/\sqrt n$ and $2^{n/2}$. That gives you the order of magnitude of the differences between expected distances from the origin of successive random walks. These differences go to zero in the first two cases and (exponentially) increase in the third.
So it makes sense that the random walks in the first two cases appear to extend symmetrically in all directions from the origin, since there will be many of them with similar average distances from the origin, which the naked eye can't distinguish because the small differences in their average distances get lost in the overall fluctuations, whereas in the third case each successive walk ends up roughly $\sqrt2$ as far away from the origin as the preceding one, so they can easily be distinguished by the naked eye, and the appearance is less symmetric.