Random walk hitting times in random trees
Date
2017-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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.
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2017
Keywords
Combinatorial probabilities, Probabilities, Random trees (Mathematics), Random walks (Mathematics), Wiener index, UCTD, Dickman distributions