Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Random walk hitting times in random trees
Thesis (PhD)--Stellenbosch University, 2017
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2017
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613751025336320 |
|---|---|
| access_status_str | Open Access |
| author | Oosthuizen, Joubert |
| author2 | Wagner, Stephan |
| author_browse | Oosthuizen, Joubert Wagner, Stephan |
| author_facet | Wagner, Stephan Oosthuizen, Joubert |
| author_sort | Oosthuizen, Joubert |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (PhD)--Stellenbosch University, 2017 |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/102727 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:41:06.301Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2017 |
| publishDateRange | 2017 |
| publishDateSort | 2017 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/102727 Random walk hitting times in random trees Oosthuizen, Joubert Wagner, Stephan Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Combinatorial probabilities Probabilities Random trees (Mathematics) Random walks (Mathematics) Wiener index UCTD Dickman distributions Thesis (PhD)--Stellenbosch University, 2017 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. Doctoral 2017-10-18T11:35:23Z 2017-12-11T10:46:40Z 2017-10-18T11:35:23Z 2017-12-11T10:46:40Z 2017-12 Thesis http://hdl.handle.net/10019.1/102727 en_ZA Stellenbosch University vii, 102 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Combinatorial probabilities Probabilities Random trees (Mathematics) Random walks (Mathematics) Wiener index UCTD Dickman distributions Oosthuizen, Joubert Random walk hitting times in random trees |
| title | Random walk hitting times in random trees |
| title_full | Random walk hitting times in random trees |
| title_fullStr | Random walk hitting times in random trees |
| title_full_unstemmed | Random walk hitting times in random trees |
| title_short | Random walk hitting times in random trees |
| title_sort | random walk hitting times in random trees |
| topic | Combinatorial probabilities Probabilities Random trees (Mathematics) Random walks (Mathematics) Wiener index UCTD Dickman distributions |
| url | http://hdl.handle.net/10019.1/102727 |
| work_keys_str_mv | AT oosthuizenjoubert randomwalkhittingtimesinrandomtrees |