Coverage probabilities of edges in a regular graph by a random walk

Thesis

We investigate the probability that a random walk covers a given edge in a connected regular network. For a complete graph or a circle graph, we obtain an explicit expression of the coverage probability by using the walk generating function. Alternatively, for any fixed connected regular network, we use the largest eigenvalue of the adjacency matrix of the network with the given edge removed from the original network to give a lower bound for the coverage probability. Finally, we give the results by Cooper and Frieze (2013) on the coverage probabilities of nice edges for random regular networks.

The motivation of this project is to obtain properties of a network from a new perspective, which is through primes of a network using random walks. Primes are simple paths and simple cycles in a network, which can be seen as building blocks of a network. A network is uniquely determined by its set of primes.

A network can be explored through a random walk on it, and the random walk can be used to detect primes of the network. A necessary condition for retrieving all the primes in a network is that a random walk visits all edges in the network. The approach of investigating the coverage probability of a given edge serves as a first step to investigate the coverage probabilities of primes.

Authors: Choo, Z

• Publication date: 2014
• Type of award: MSc by Research
• Level of award: Masters
• Awarding institution: Oxford University, UK
• Language: English
• Keywords: random walk; primes; coverage probability of an edge; regular graphs; accumulative prime factorisation
• Subjects: Probability; Graph Theory; Network Analysis; Combinatorics