Abstract
M.Sc. (Mathematics)
In chapter 1, we give the reader some background concerning digraphs that are used in the discussion of
Markov chains; namely, their Markov digraphs. Warshall’s Algorithm for reachability is also introduced as
this is used to define terms such as transient states and irreducibility.
Some initial theory and definitions concerning Markov chains and their corresponding Markov digraphs
are given in chapter 2. Furthermore, we discuss l–step transitions (walks of length l) for homogeneous and
inhomogeneous Markov chains and other generalizations.
In chapter 3, we define terms such as communication, intercommunication, recurrence and transience. We
also prove some results regarding the irreducibility of some Markov chains through the use of the reachability
matrix. Furthermore, periodicity and aperiodicity are also investigated and the existence of walks of
any length greater than some specified integer N is also considered. A discussion on random walks on an
undirected torus is also contained in this chapter.
In chapter 4, we explore stationary distributions and what it means for a Markov chain to be reversible.
Furthermore, the hitting time and the mean hitting time in a Markov digraph are also defined and the proof
of the theorems regarding them are done. The demonstrations of the theorems concerning the existence and
uniqueness of stationary distributions and the Markov Chain Convergence Theorem are carried out. Later
in this chapter, we define the Markov digraph of undirected graphs, which are Markov chains as well. The
existing theory is then applied to these.
In chapter 5, we explore and see how to simulate Markov chains on a computer by using Markov Chain
Monte Carlo Methods. We also show how these apply to random q–colourings of undirected graphs.
Finally, in chapter 6, we consider a physical application of these Graph Theoretical concepts—the simulation
of the Ising model. Initially, the relevant concepts of the Potts model are given and then the Gibbs
sampler algorithm in chapter 5 is modified and used to simulate the Ising model. A relation between the
chromatic polynomial and the partition function of the Potts model is also demonstrated.