Browsing by Author "Oosthuizen, Joubert"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
- ItemRandom walk hitting times in random trees(Stellenbosch : Stellenbosch University, 2017-12) Oosthuizen, Joubert; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.ENGLISH ABSTRACT : The hitting time Hxy, between two vertices x and y of a graph, is the average time that the standard simple random walk takes to get from x to y. We start by giving a recursive formula for higher moments of the random time the simple random walk takes to get from x to y, that allows us to extend two well-known results for the hitting time on trees to all higher moments. The main part of this thesis is concerned with the distribution of the hitting time between two randomly chosen vertices of a random tree. We consider both uniformly random labelled trees and a more general model with vertex weights akin to simply generated trees. We show that the r-th moment of the hitting time is of asymptotic order n3r=2 in trees of order n, and we describe the limiting distribution upon normalisation by means of its moments. Moreover we also obtain joint moments with the distance between the two selected vertices and also the first moment of the hitting time variance. Finally we consider three classes of random increasing trees. In this setup, the root is of special importance, and so we study the hitting time from the root to a random vertex, from a random vertex to the root and between two random vertices. The hitting times, for all three classes of increasing trees, from the root as well as between two random vertices is of order n log n, with a normal limit law. On the other hand the hitting time to the root is only of linear order and converges in the limit to different Dickman distributions for the different classes of increasing trees.
- ItemRandom walks on graphs(Stellenbosch : Stellenbosch University, 2014-04) Oosthuizen, Joubert; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.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.