An Iterative Algorithm to Optimize the Average Performance of Markov Chains with Finite States
Ryusei Fujita, Ken‐ichi Iwata, H. Yamamoto · 2019
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.