Random walk hitting times in random trees
| dc.contributor.advisor | Wagner, Stephan | en_ZA |
| dc.contributor.author | Oosthuizen, Joubert | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. | en_ZA |
| dc.date.accessioned | 2017-10-18T11:35:23Z | |
| dc.date.accessioned | 2017-12-11T10:46:40Z | |
| dc.date.available | 2017-10-18T11:35:23Z | |
| dc.date.available | 2017-12-11T10:46:40Z | |
| dc.date.issued | 2017-12 | |
| dc.description | Thesis (PhD)--Stellenbosch University, 2017 | en_ZA |
| dc.description.abstract | 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. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING : Die treftyd Hxy, tussen twee punte x en y in 'n grafiek, is die gemiddelde tyd wat die ewekansige toevallige wandeling vat om te beweeg van x na y. Eerstens gee ons 'n rekursiewe formule vir die hoër momente van die treftyd wat ons in staat stel om twee bekende resultate oor die treftyd uit te brei na alle momente. Die hoofdeel van hierdie tesis handel oor die verdeling van die treftyd tussen twee lukraak gekose punte in 'n lukrake boom. Ons beskou beide ewekansige lukrake gemerkte bome en 'n meer algemene model met geweegde punte soortgelyk aan eenvoudig gegenereerde bome. Ons wys dat die r-de moment van die treftyd van asimptotiese orde n3r=2 is in bome van orde n en ons beskryf die limietverdeling na normalisering deur middel van sy momente. Verder verkry ons ook gesamentlike momente met die afstand tussen die twee gekose punte asook die eerste moment van die treftyd variansie. Uiteindelike beskou ons drie klasse van lukraak toenemende bome. Die wortel van die boom is hier van spesiale belang en dus beskou ons die treftyd van die wortel na 'n lukrake punt, van 'n lukrake punt na die wortel en ook tussen twee lukrake punte. Die treftye, vir al drie klasse van toenemende bome, van die wortel asook tussen twee lukrake punte is van orde n log n met 'n normale limietverdeling. Andersyds is die treftyd na die wortel slegs van lineeêre orde en konvergeer die verdelings in die limiet, vir die verskillende klasse van toenemende bome, na verskillende Dickman verdelings. | af_ZA |
| dc.format.extent | vii, 102 pages | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/102727 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Combinatorial probabilities | en_ZA |
| dc.subject | Probabilities | en_ZA |
| dc.subject | Random trees (Mathematics) | en_ZA |
| dc.subject | Random walks (Mathematics) | en_ZA |
| dc.subject | Wiener index | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Dickman distributions | en_ZA |
| dc.title | Random walk hitting times in random trees | en_ZA |
| dc.type | Thesis | en_ZA |