  Tau-leaping is a popular discretization method for generating approximate
paths of continuous time, discrete space, Markov chains, notably for
biochemical reaction systems. To compute expected values in this context, an
appropriate multilevel Monte Carlo form of tau-leaping has been shown to
improve efficiency dramatically. In this work we derive new analytic results
concerning the computational complexity of multilevel Monte Carlo tau-leaping
that are significantly sharper than previous ones. We avoid taking asymptotic
limits, and focus on a practical setting where the system size is large enough
for many events to take place along a path, so that exact simulation of paths
is expensive, making tau-leaping an attractive option. We use a general scaling
of the system components that allows for the reaction rate constants and the
abundances of species to vary over several orders of magnitude, and we exploit
the random time change representation developed by Kurtz. The key feature of
the analysis that allows for the sharper bounds is that when comparing relevant
pairs of processes we analyze the variance of their difference directly rather
than bounding via the second moment. Use of the second moment is natural in the
setting of a diffusion equation, where multilevel was first developed and where
strong convergence results for numerical methods are readily available, but is
not optimal for the Poisson-driven jump systems that we consider here. We also
present computational results that illustrate the new analysis.
