Process convergence for the complexity of Radix Selection on Markov sources
Process convergence for the complexity of Radix Selection on Markov sources
复制标题
马尔可夫源上基数选择复杂性的过程收敛
DOI：
10.1016/j.spa.2018.03.009
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
H. Sulzbach
中科院分区：
文献类型：
--
作者：
Leckey;Neininger;H. Sulzbach
从有序集合的有限子集中选择秩的基本算法是基数选择。该算法要求数据以有序字母表上的符号串的形式给出，例如实数的二进制展开。它的复杂性是由需要读取的符号的数量来衡量的。本文研究了由马尔可夫链生成的独立数据的同构模型。将复杂性研究为一个随机过程，该过程由给定字母表上的无限字符串集合索引。导出了复杂度的均值和方差的阶数，并在归一化后，导出了以中心高斯过程为极限的极限定理。这意味着对排名的两个标准模型进行分析：均匀选择排名，也称为大平均排名，以及最坏情况下的排名复杂性，这是计算机科学感兴趣的。对于均匀数据和非对称伯努利模型（即无记忆源），我们还发现当以秩为索引时，复杂性的归一化过程具有弱收敛性，而对于更一般的马尔可夫源，这些过程在标准归一化下并不紧密。
A fundamental algorithm for selecting ranks from a finite subset of an ordered set is Radix Selection. This algorithm requires the data to be given as strings of symbols over an ordered alphabet, e.g., binary expansions of real numbers. Its complexity is measured by the number of symbols that have to be read. In this paper the model of independent data identically generated from a Markov chain is considered.The complexity is studied as a stochastic process indexed by the set of infinite strings over the given alphabet. The orders of mean and variance of the complexity and, after normalization, a limit theorem with a centered Gaussian process as limit are derived. This implies an analysis for two standard models for the ranks: uniformly chosen ranks, also called grand averages, and the worst case rank complexities which are of interest in computer science.For uniform data and the asymmetric Bernoulli model (i.e. memoryless sources), we also find weak convergence for the normalized process of complexities when indexed by the ranks while for more general Markov sources these processes are not tight under the standard normalizations.
登录
查看更多内容
对 QuickSelect 算法进行现实分析
影响因子：
0.5
作者：
J. Clément;J. A. Fill;T. N. Thi;B. Vallée
通讯作者：
B. Vallée
随机四叉树中部分匹配查询的限制过程
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
N. Broutin;Ralph Neininger;Henning Sulzbach
通讯作者：
Henning Sulzbach
快速排序过程
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
Mahmoud Ragab;U. Roesler
通讯作者：
U. Roesler
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Ralph Neininger;L. Rüschendorf
通讯作者：
L. Rüschendorf
凡尔赛大学
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
B. Overman
通讯作者：
B. Overman