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\geq 0$. In order to do it, we fix a time horizon $T $ and the discretization steps $h_{l}=\frac{T}{n^{l}},l\in \mathbb{N}$ and we suppose that we have at hand some short time approximation operators $Q_{l}$ such that $P_{h_{l}}=Q_{l}+O(h_{l}^{1+α})$ for some $α>0$. Then, we consider random time grids $Π(ω)=\{t_0(ω)=0<t_{1}(ω)<...<t_{m}(ω)=T\}$ such that for all $1\le k\le m$, $t_{k}(ω)-t_{k-1}(ω)=h_{l_{k}}$ for some $l_{k}\in \mathbb{N}$, and we associate the approximation discrete semigroup $P_{T}^{Π(ω)}=Q_{l_{n}}...Q_{l_{1}}.$ 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 \[ P_{t}f=\sum_{i=1}^{r}c_{i}\mathbb{E}(P_{t}^{Π_{i}(ω)}f(x))+O(n^{-ν}) \]% with the expectation concerning the random grids $Π_{i}(ω).$ Besides, $\text{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.