Monday, July 13, 2015

Möbius function two-dimensional (pseudo)random walk vs random walks

Playing with random walks is quite fascinating, in this case instead of using a random generator I have applied the Möbius function to decide the next step in a two-dimensional walk. It is said that the behavior of the Möbius function is pseudorandom. Indeed looking at the output of the walk it looks really like a "standard" random walk. Here is the output:


And this is a random walk generated with a random seed:

I posted a question regarding "reset random walks" at MSE recently. Basically, when a reset condition is added to the random walk, sometimes there is a clear symmetry on the graph, and sometimes not, so it is not clear which reset conditions have as a result a symmetrical graph or not. Here is an example of symmetry:



Here is the link to the question: Why does symmetry happen in reset-based random walks?

And here is the Python code. Have fun!

# Mobius walk vs Random walk
# by David M.@http://hobbymaths.blogspot.jp/

def mbrw():
    from sympy import mobius
    import matplotlib.pyplot as plt
    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
        # mobius or random (uncomment for random seed)
        tmpval=mobius(n)
        #myrand = randint(0,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
           
            # This is a sample of symmetrical reset condition
            # uncomment to apply a reset condition
            #if is_square(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()

No comments:

Post a Comment