Linear Programming in a Markov Chain

Abstract

An infinite Markov process with a finite number of states is studied in which the transition probabilities for each state range independently over sets that are either finite or are convex polyhedra. A finite computational procedure is given for choosing those transition probabilities that minimize appropriate functions of the resulting equilibrium probabilities, the procedure is a specialization of the authors' decomposition algorithm for linear programming problems of special structure.