Solving Poisson's equation for birth-death chains: structure, instability, and accurate approximation Articles
- PERFORMANCE EVALUATION Journal
- January 2021
Digital Object Identifier (DOI)
International Standard Serial Number (ISSN)
Electronic International Standard Serial Number (EISSN)
- 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.
- poisson’s equation; birth–death process; relative cost function; numerical instability; linear recurrence; backward recurrence