Paper Info
Title
Persisting randomness in randomly growing discrete structures: graphs and search trees.
Abstract
The successive discrete structures generated by a sequential algorithm from random input constitute a Markov chain that may exhibit long term dependence on its first few input values. Using examples from random graph theory and search algorithms we show how such persistence of randomness can be detected and quantified with techniques from discrete potential theory. We also show that this approach can be used to obtain strong limit theorems in cases where previously only distributional convergence was known.
Year
Venue
Keywords
2015
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Boundary theory,Markov chains,random graphs,search trees
Field
DocType
Volume
Convergence (routing),Graph,Discrete mathematics,Potential theory,Combinatorics,Search algorithm,Random graph,Markov chain,Sequential algorithm,Mathematics,Randomness
Journal
18.0
Issue
ISSN
Citations 
1.0
1462-7264
0
PageRank 
References 
Authors
0.34
1
1
Name
Order
Citations
PageRank
Rudolf Grübel1154.71