THE MOVE-TO-FRONT RULE FOR SELF-ORGANIZING LISTS WITH MARKOV DEPENDENT REQUESTS·
THE MOVE-TO-FRONT RULE FOR SELF-ORGANIZING LISTS WITH MARKOV DEPENDENT REQUESTS·
复制标题
具有马尔可夫相关请求的自组织列表的前移规则·
DOI：
10.1007/978-1-4612-0801-3_5
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
J. A. Fill
中科院分区：
文献类型：
--
作者：
R. Dobrow;J. A. Fill
我们考虑前移自组织线性搜索启发式，其中记录请求序列是马尔可夫链。推导了排列链的转移概率和平稳分布的公式。链的光谱结构被明确地呈现。排列链的平稳性差异的界限是根据请求链的相应差异（对于分离距离和总变化距离）来计算的。
We consider the move-to-front self-organizing linear search heuristic where the sequence of record requests is a Markov chain. Formulas are derived for the transition probabilities and stationary distribution of the permutation chain. The spectral structure of the chain is presented explicitly. Bounds on the discrepancy from stationarity for the permutation chain are computed in terms of the corresponding discrepancy for the request chain, both for separation and for total variation distance.