Stationary Distributions of Discrete-Time Markov Chains in Random Environment: Exact Computations and Bounds

Abstract

A general model for the description of a discrete-time Markov chain in random environment is introduced. We study the stationary distribution of this model and its relationship with the Palm (embedded) distributions at certain environmental transition epochs. We also study the Events See Time Averages (ESTA) property for this model and we show that it is related to certain partial balance equations and a product-form stationary distribution. Next, we study certain forms of interaction between the environmental process and the process of interest that lead to tractable stationary distributions. More specifically, the stationary distributions of a large class of Markov chains in random environment can be computed efficiently using α-potentials of smaller Markov chains. This decomposability result is also the basis for developing approximations for the stationary distributions of intractable models that evolve in a slowly changing random environment. Moreover, explicit error bounds for these approximations are given. The model can be used for the performance evaluation of discrete time queueing systems in random environment.

Key Words:

• Discrete time Markov chain
• Random environment
• Stationary distribution
• Embedded chain
• Queueing
• Product form distribution
• Partial balance
• Potential
• ESTA property

Acknowledgment

The author thanks the support received from the University of Athens (ELKE) grant 70/4/6415.