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

publication date

  • January 2021


  • 145

International Standard Serial Number (ISSN)

  • 1872-745X

Electronic International Standard Serial Number (EISSN)

  • 0166-5316


  • 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