An Iterative Algorithm to Optimize the Average Performance of Markov Chains with Finite States

We consider Markov chains with finite states, which have unique stationary distributions and satisfy the following conditions I)-III). I) Each state s i has its own discrete parameter t i . II) Each state s i has a local performance function f(t i ). III) Each state s i has a transition probability...

Full description

Saved in:
Bibliographic Details
Main Authors: Fujita, Ryusei, Iwata, Ken-ichi, Yamamoto, Hirosuke
Format: Conference Proceeding
Language:English
Subjects:
Closed-form solutions
Dynamic programming
Heuristic algorithms
Iterative methods
Markov processes
Matrices
Optimization
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider Markov chains with finite states, which have unique stationary distributions and satisfy the following conditions I)-III). I) Each state s i has its own discrete parameter t i . II) Each state s i has a local performance function f(t i ). III) Each state s i has a transition probability function p i, j (t i ) from state s i to state s j . 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.
ISSN:2157-8117
DOI:10.1109/ISIT.2019.8849856