Convergence to stationary state for a Markov move-to-front scheme
Convergence to stationary state for a Markov move-to-front scheme
复制标题
马尔可夫前移方案收敛到静止状态
DOI：
10.2307/3215128
复制
发表时间：
1995
影响因子：
1
通讯作者：
Eliane R. Rodrigues
中科院分区：
文献类型：
--
作者：
Eliane R. Rodrigues
这项工作考虑的项目（如书籍，文件）安排在一个数组（如货架，磁带）与N个位置，并假设项目的要求，根据马尔可夫链（可能是高阶）。使用后，请求的项将返回到数组的最左边位置。连续应用上述过程会产生一个关于排列的马尔可夫链。对于同样可能的项目，估计使该马尔可夫链接近其平稳状态的请求的数量。为了实现这一点，使用耦合变元和总变化距离。最后，对于非等可能的项目和所谓的p-相关的请求，耦合时间作为耦合时间的函数时，请求是独立的。
This work considers items (e.g. books, files) arranged in an array (e.g. shelf, tape) with N positions and assumes that items are requested according to a Markov chain (possibly, of higher order). After use, the requested item is returned to the leftmost position of the array. Successive applications of the procedure above give rise to a Markov chain on permutations. For equally likely items, the number of requests that makes this Markov chain close to its stationary state is estimated. To achieve that, a coupling argument and the total variation distance are used. Finally, for non-equally likely items and so-called p-correlated requests, the coupling time is presented as a function of the coupling time when requests are independent.