Abstract – The proposed system intends to provide a framework for exploring random walks on graphs. The overall architecture of the system is described in brief. It consists of six modules. The system would be implemented using C++ and Java language. Linked list data structure is

used to store the graphs. The system would be applied to selected theoretical results in the field of random walks. The result of the analysis would be displayed in form of graphs and charts.

Index Terms – Graphs G (V, E), Nodes, Adjacency Matrix, Transitional Probability matrix, Walk, Pseudorandom, Mean time of return, Link list.

INTRODUCTION

A graph G is a pair G = (V, E) where V is a finite set and E is a set of 2-element subsets of V. An element of V is called a vertex of the graph and an element of E is called an edge of the graph. The order of a graph is its number of vertices. The degree of each vertex v is the number of edges with which it

is incident, it is represented as d(v). Given an undirected, connected graph G(V,E) with |V| =n, |E| = m a random “step” in G is a move from some node u to a randomly selected neighbor v. A random walk is a

sequence of these random steps starting from some initial node.

For example, a walk on a Graph is X0, X1, X2, X3 … Xn where Xi € V(G). In a random walk on a graph, X0 is chosen, X1 is chosen randomly out of the neighbours of X0, X2 is chosen randomly out of the neighbours of the X1 and so on.

In our study, we will restrict ourselves initially to simple graphs without loops i.e. no parallel edges and undirected. G will be a fixed graph with n vertices and m edges. We will further take the transition probability matrix P = [pij]. Where, pij = 1/d(i) if ij € E(G)= 0 otherwise

Given any initial probability distribution,

p = [pi] = [p1 p2 p3 p4 … pn]

Then, after one step the probability distribution will be pP. Typically, we will take the initial probability distribution in one of the three ways:-

(a) Π = di / 2m = (d1/2m, d2/2m, d3/2m ... , dn/2m)

(b) Π = (0,0,0,0,0 … 1 … 0)

(c) Π = (1/n, 1/n, 1/n … 1/n)

MOTIVATION

Graph theory demands prominence because of its status as that branch of pure mathematics which is closest to computer science. This proximity enriches both disciplines: not only is graph theory fundamental to theoretical computer science, but problems arising in computer science and other

areas of application greatly influence the direction taken by graph theory.

Random walks on graph finds its use in a wide variety of applications like economics, share prices, physics, electrical networks, Brownian motion, mathematics, sampling problem, finding volumes of convex bodies etc.

PROBLEM DEFINITION

The problem statement for the project is to design and implement a system that simulates the various theoretical results relating to random walks and provide an experimental verification for the same by simulating a large number of random walks on graphs belonging to different families.

PROJECT APPROACH

1. Designing a system to simulate random walks on graphs.

2. Implementing the system to perform the random walks.

3. Simulate a large number of walks for each graph to explore the theoretical results related to random

walks.