Computational Algorithms for Moments of Accumulated Markov and Semi-Markov Rewards

Abstract

Power moments for accumulated rewards defined on Markov and semi-Markov chains are studied. A model with mixed time-space termination of reward accumulation is considered for inhomogeneous in time rewards and Markov chains. Characterization of power moments as minimal solutions of recurrence system of linear equations, sufficient conditions for finiteness of these moments and upper bounds for them, expressed in terms of so-called test functions, are given. Backward recurrence algorithms for funding of power moments of accumulated rewards and various time-space truncation approximations reducing dimension of the corresponding recurrence relations are described.

Keywords:

• Accumulated reward
• High-order moment
• Markov chain
• Recurrence backward algorithm
• Semi-Markov chain
• Time-space truncation approximation