Markov chain approximations to scale functions of Lévy processes

We introduce a general algorithm for the computation of the scale functions of a spectrally negative Lévy process XX, based on a natural weak approximation of XX via upwards skip-free continuous-time Markov chains with stationary independent increments. The algorithm consists of evaluating a finite linear recursion with its (nonnegative) coefficients given explicitly in terms of the Lévy triplet of XX. Thus it is easy to implement and numerically stable. Our main result establishes sharp rates of convergence of this algorithm providing an explicit link between the semimartingale characteristics of XX and its scale functions, not unlike the one-dimensional Itô diffusion setting, where scale functions are expressed in terms of certain integrals of the coefficients of the governing SDE.