Persisting randomness in randomly growing discrete structures: graphs and search trees
Persisting randomness in randomly growing discrete structures: graphs and search trees
复制标题
在随机增长的离散结构中保持随机性：图和搜索树
DOI：
10.46298/dmtcs.644
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Grübel
中科院分区：
文献类型：
--
作者：
R. 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.
搜索树：度量方面和强极限定理
影响因子：
1.8
作者：
Rudolf Grubel
通讯作者：
Rudolf Grubel
Doob--Remy 树生长链的 Martin 边界
DOI：
10.1214/16-aop1112
发表时间：
2017
期刊：
arXiv: Probability
影响因子：
--
作者：
Rudolf Grubel;Steven N. Evans;Anton Wakolbinger
通讯作者：
Anton Wakolbinger