Rudolf Grübel - Persisting randomness in randomly growing discrete structures: graphs and search trees

dmtcs:644 - Discrete Mathematics & Theoretical Computer Science, October 1, 2015, Vol. 18 no. 1 - https://doi.org/10.46298/dmtcs.644
Persisting randomness in randomly growing discrete structures: graphs and search trees

Authors: Rudolf Grübel

    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.


    Volume: Vol. 18 no. 1
    Section: Analysis of Algorithms
    Published on: October 1, 2015
    Accepted on: October 1, 2015
    Submitted on: September 30, 2015
    Keywords: Mathematics - Probability,68Q87, 05C80, 60J10, 60J50

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo DOI 10.2307/3213469
    • 10.2307/3213469
    Chernoff's theorem in the branching random walk

    2 Documents citing this article

    Consultation statistics

    This page has been seen 947 times.
    This article's PDF has been downloaded 568 times.