Random walk modelling



In [ ]:

    
import numpy as np
import matplotlib.pyplot as plt
from numpy.random import choice, rand 
import networkx as nx
%matplotlib inline

During this seminar we will immulate the random walk on knight's network, which you should build in the first place.

Consider $n \times n$ chessboard with a single knight on it. <br>

Construct a network with all knight's possible moves. In this network each node represents chessboard locations and an edge between two locations appears if knight is admitted to move from one to another.
Implement simulation of knight random walk on chessboard
- Calculate average probability to visit chessboard locations
- Calculate average recurrence probability of a node

Knight's Network



In [ ]:

    
def GenKnightNetwork( boardSize, spacing = 1 ) :
    layers = np.arange( boardSize*boardSize, dtype = np.int ).reshape((boardSize,boardSize))
    G = nx.Graph( )
    pos = list( )
## Start your code here
    grid = np.arange( boardSize, dtype = np.float ) * spacing
    X, Y = np.meshgrid( grid, grid )
    for l in xrange( boardSize - 1 ) :
        edge_list = list( )
        l0 = layers[l+0,:]
        l1 = layers[l+1,:]
## Add the first layer nodes: RRD
        edge_list.extend( [ ( l0[ i ], l1[ i+2 ] ) for i in xrange( boardSize - 2 ) ] )
## Add the first layer nodes: LLD
        edge_list.extend( [ ( l0[ i+2 ], l1[ i ] ) for i in xrange( boardSize - 2 ) ] )
        if l < boardSize - 2 :
            l2 = layers[l+2,:]
## Add the first layer nodes: DDR
            edge_list.extend( [ ( l0[ i ], l2[ i+1 ] ) for i in xrange( boardSize - 1 ) ] )
## Add the first layer nodes: DDL
            edge_list.extend( [ ( l0[ i+1 ], l2[ i ] ) for i in xrange( boardSize - 1 ) ] )
        G.add_edges_from( edge_list )
## Add position coordinates make the mesh into a dictionary
        pos.extend( ( (X[l,i], Y[l,i]) for i in xrange( boardSize ) ) )
    pos.extend( ( (X[l+1,i], Y[l+1,i]) for i in xrange( boardSize ) ) )
    return G, {n: p for (n, p) in zip( layers.flatten(), pos )}

Random Walk Process



In [ ]:

    
def RandomWalk(G, xi, n = 100, till_first_return = False):
## Your function should terminate after all iterations OR after you reach the initial node
    Q = list( [ xi ] )
    i = 0 ; xi = None
    while i < n :
## Choose a node at random from the neighbours
        xi = np.random.choice( G[ Q[-1] ].keys( ), size = 1 )[ 0 ]
        Q.append( xi )
        if( till_first_return and xi == Q[ 0 ] ) :
            break
        i += 1
    return Q



In [ ]:

    
boardSize = 16
(G,pos) = GenKnightNetwork(boardSize)



In [ ]:

    
traj = list( )
for xi in np.random.choice( G.nodes(), size = 10 ):
## Pick a node at random
    traj.append( RandomWalk( G, xi, 10, till_first_return = False ) )

edgeSeq = list()
for t in traj :
    edgeSeq.extend( [ ( i, j ) for i,j in zip( t[:-1],t[1:] ) ] )



In [ ]:

    
fig = plt.figure( figsize = (16,16) )
ax = fig.add_subplot( 1,1,1, axis_bgcolor = 'black' )
nx.draw(G, pos, ax = ax, node_size = 1, edge_color = 'gray')
nx.draw(G, pos, ax = ax, edgelist = edgeSeq, edge_color='blue', width=2, node_size = 1 )



In [ ]:

    
traj = list( )
for xi in np.random.choice( G.nodes(), size = 100 ):
## Pick a node at random
    traj.append( RandomWalk( G, xi, 1000, till_first_return = False ) )



In [ ]: