Operations Research seminar

Operations Research seminar

Error bounds for stationary performance of random walks in the quarter plane based on inhomogeneous perturbations

Xinwei Bai, UT-EWI-SOR


Random walks in the quarter plane with homogeneous transition probabilities are considered in this work. Given a non-negative reward function on the state space, we are interested in the expected stationary performance. Due to the difficulty of direct derivation of this performance for general random walks, upper and lower bounds are constructed based on the performance of a perturbed random walk for which the stationary probability distribution is a sum of geometric terms.

We consider inhomogeneous transition probabilities for the perturbed random walks, which means that the transition probabilities are different at every state. The bounds are constructed using the Markov reward approach. In the end, an explicit expression for the error bound is given. The error bound result does not depend on the values of the inhomogeneous transition probabilities. Therefore, only the existence of those probabilities is needed.

Numerical experiments indicate that inhomogeneous perturbed random walks can give better error bounds than perturbations based on homogeneous random walks. The reason is that by allowing for inhomogeneous transition probabilities, we don’t require the pairwise structure between geometric terms that is necessary for homogeneous random walks.