Random walks on graphs

Description

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: We study random walks on nite graphs. The reader is introduced to general
Markov chains before we move on more specifically to random walks on graphs.
A random walk on a graph is just a Markov chain that is time-reversible. The
main parameters we study are the hitting time, commute time and cover time.
We nd novel formulas for the cover time of the subdivided star graph and
broom graph before looking at the trees with extremal cover times.
Lastly we look at a connection between random walks on graphs and electrical
networks, where the hitting time between two vertices of a graph is expressed
in terms of a weighted sum of e ective resistances. This expression in turn
proves useful when we study the cover cost, a parameter related to the cover
time. / AFRIKAANSE OPSOMMING: Ons bestudeer toevallige wandelings op eindige gra eke in hierdie tesis. Eers
word algemene Markov kettings beskou voordat ons meer spesi ek aanbeweeg
na toevallige wandelings op gra eke. 'n Toevallige wandeling is net 'n Markov
ketting wat tyd herleibaar is. Die hoof paramaters wat ons bestudeer is die
treftyd, pendeltyd en dektyd. Ons vind oorspronklike formules vir die dektyd
van die verdeelde stergra ek sowel as die besemgra ek en kyk daarna na die
twee bome met uiterste dektye.
Laastens kyk ons na 'n verband tussen toevallige wandelings op gra eke en
elektriese netwerke, waar die treftyd tussen twee punte op 'n gra ek uitgedruk
word in terme van 'n geweegde som van e ektiewe weerstande. Hierdie uitdrukking
is op sy beurt weer nuttig wanneer ons die dekkoste bestudeer, waar
die dekkoste 'n paramater is wat verwant is aan die dektyd.

Links & Downloads

1. http://hdl.handle.net/10019.1/86244

Tags

Cover time

Dissertations -- Mathematics

Theses -- Mathematics

Theses -- Mathematical sciences

Random walks (Mathematics)

Markov processes

Graph theory

UCTD

Additional Fields

Identifer	oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/86244
Date	04 1900
Creators	Oosthuizen, Joubert
Contributors	Wagner, S., Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
Publisher	Stellenbosch : Stellenbosch University
Source Sets	South African National ETD Portal
Language	en_ZA
Detected Language	Unknown
Type	Thesis
Format	72 p.
Rights	Stellenbosch University