Persisting randomness in randomly growing discrete structures: graphs and search trees
From MaRDI portal
Publication:2789549
zbMATH Open1355.60099arXiv1407.0808MaRDI QIDQ2789549
Publication date: 1 March 2016
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.
Full work available at URL: https://arxiv.org/abs/1407.0808
Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Strong limit theorems (60F15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)
This page was built for publication: Persisting randomness in randomly growing discrete structures: graphs and search trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789549)
