A generic construction for high order approximation schemes of semigroups using random grids

Our aim is to construct high order approximation schemes for general semigroups of linear operators P_t, t≥ 0. In order to do it, we fix a time horizon T and the discretization steps hl=Tnl,l∈N and we suppose that we have at hand some short time approximation operators Q_l such that Phl=Ql+O(hl1+α) for some α> 0. Then, we consider random time grids Π (ω) = { t(ω) = 0 < t₁(ω) < ⋯ < t_m(ω) = T} such that for all 1 ≤ k≤ m, tk(ω)-tk-1(ω)=hlk for some l_k∈ N, and we associate the approximation discrete semigroup PTΠ(ω)=Qln…Ql1. Our main result is the following: for any approximation order ν, we can construct random grids Π _i(ω) and coefficients c_i, with i= 1 , … , r such that Ptf=∑i=1rciE(PtΠi(ω)f(x))+O(n-ν)with the expectation concerning the random grids Π _i(ω). Besides, Card(Π _i(ω)) = O(n) and the complexity of the algorithm is of order n, for any order of approximation ν. The standard example concerns diffusion processes, using the Euler approximation for Q_l. In this particular case and under suitable conditions, we are able to gather the terms in order to produce an estimator of P_tf with finite variance. However, an important feature of our approach is its universality in the sense that it works for every general semigroup P_t and approximations. Besides, approximation schemes sharing the same α lead to the same random grids Π _i and coefficients c_i. Numerical illustrations are given for ordinary differential equations, piecewise deterministic Markov processes and diffusions.