An Iterative Algorithm to Optimize the Average Performance of Markov Chains with Finite States
An Iterative Algorithm to Optimize the Average Performance of Markov Chains with Finite States
复制标题
优化有限状态马尔可夫链平均性能的迭代算法
DOI：
10.1109/isit.2019.8849856
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Hirosuke Yamamoto
中科院分区：
文献类型：
--
作者：
Ryusei Fujita; Ken-ichi Iwata;Hirosuke Yamamoto
我们考虑具有唯一平稳分布的有限状态马尔可夫链，它满足以下条件I)-III)。I)每个状态都有自己的离散参数ti。II)每个状态都有一个局部性能函数f（ti）。III)每个状态sij都有一个从状态sij到状态sj的转移概率函数pi， j（ti）。在本文中，我们给出了一种迭代方法来优化上述马尔可夫链的全局平均性能，这些马尔可夫链对所有参数集都具有唯一平稳分布。该方法是我们在上一篇文章中提出的构造最优AIFV-m码的迭代方法的推广。但本文在概括的基础上，进一步细化了以下两点。(i)澄清了迭代法虽然是一种拉斯维加斯算法，但总是终止并给出正确结果的条件。（ii）给出了求解各状态局部优化问题的系数的封闭表达式。
We consider Markov chains with finite states, which have unique stationary distributions and satisfy the following conditions I)-III). I) Each state sihas its own discrete parameter ti. II) Each state sihas a local performance function f(ti). III) Each state sihas a transition probability function pi, j(ti) from state sito state sj. In this paper, we give an iterative method to optimize the global average performance of the above Markov chains, which have unique stationary distributions for all sets of the parameters. This method is a generalization of the iterative method to construct the optimal AIFV-m code, which was proposed in our previous paper. But in this paper, the following two points are further refined besides the generalization. (i) We clarify the condition such that the iterative method always terminates and gives correct results although the iterative method is a kind of Las Vegas algorithm. (ii) We provide a closed-form expression of coefficients to solve the local optimization problem of each state.