Solving Poisson's equation for birth-death chains: structure, instability, and accurate approximation

Poisson's equation plays a fundamental role as a tool for performance evaluation and optimization of Markov chains. For continuous-time birth-death chains with possibly unbounded transition and cost rates as addressed herein, when analytical solutions are unavailable its numerical solution can in theory be obtained by a simple forward recurrence. Yet, this may suffer from numerical instability, which can hide the structure of exact solutions. This paper presents three main contributions: (1) it establishes a structural result (convexity of the relative cost function) under mild conditions on transition and cost rates, which is relevant for proving structural properties of optimal policies in Markov decision models; (2) it elucidates the root cause, extent and prevalence of instability in numerical solutions by standard forward recurrence; and (3) it presents a novel forward;-backward recurrence scheme to compute accurate numerical solutions. The results are applied to the accurate evaluation of the bias and the asymptotic variance, and are illustrated in an example.

Solving Poisson's equation for birth-death chains: structure, instability, and accurate approximation Articles