Persisting randomness in randomly growing discrete structures: graphs and search trees
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 dete...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/644/pdf |
| _version_ | 1797270074196754432 |
|---|---|
| author | Rudolf Grübel |
| author_facet | Rudolf Grübel |
| author_sort | Rudolf Grübel |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:29Z |
| format | Article |
| id | doaj.art-600f4b75386b4cbf98c7f02ad9d8e3e7 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:29Z |
| publishDate | 2015-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-600f4b75386b4cbf98c7f02ad9d8e3e72024-03-07T15:29:46ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-10-01Vol. 18 no. 1Analysis of Algorithms10.46298/dmtcs.644644Persisting randomness in randomly growing discrete structures: graphs and search treesRudolf GrübelThe 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.https://dmtcs.episciences.org/644/pdfmathematics - probability68q87, 05c80, 60j10, 60j50 |
| spellingShingle | Rudolf Grübel Persisting randomness in randomly growing discrete structures: graphs and search trees Discrete Mathematics & Theoretical Computer Science mathematics - probability 68q87, 05c80, 60j10, 60j50 |
| title | Persisting randomness in randomly growing discrete structures: graphs and search trees |
| title_full | Persisting randomness in randomly growing discrete structures: graphs and search trees |
| title_fullStr | Persisting randomness in randomly growing discrete structures: graphs and search trees |
| title_full_unstemmed | Persisting randomness in randomly growing discrete structures: graphs and search trees |
| title_short | Persisting randomness in randomly growing discrete structures: graphs and search trees |
| title_sort | persisting randomness in randomly growing discrete structures graphs and search trees |
| topic | mathematics - probability 68q87, 05c80, 60j10, 60j50 |
| url | https://dmtcs.episciences.org/644/pdf |
| work_keys_str_mv | AT rudolfgrubel persistingrandomnessinrandomlygrowingdiscretestructuresgraphsandsearchtrees |