



Introduction
============

Let $T>0$, and let $N(\cdot)$ be a Poisson random measure defined on the interval $[0,T]$, with the Borel $\sigma$-field, and control measure $n(ds)$, which we assume to have a density $n(ds) = n(s)ds$. For appropriate functions ${g}(s), \ s \in [0,T]$, the Poisson stochastic integral $$\label{e:firstpoisint}
I({g})  =  \int_0^T {g}(s) N(ds),$$ is a random variable defined as the limit in probability: $$P-\lim_{||\Delta_n|| 
\rightarrow 0} \sum_{i=1}^n {g}(s_i) N( [s_i,s_{i+1}) ), \quad \Delta_n
= \{ 0 < s_1 < s_2 < \dots <
s_n < T \}.$$ For this limit to exist, we require that kernel ${g}$ satisfies $$\label{e:poiscond}
\int_0^T \min({g}(s),1) n(ds) < \infty.$$ The characteristic function of $I({g})$ is expressible in terms of the control measure and kernel, and is given by $$\label{e:poischarfunc}
\phi_{g}(\theta) = \mathbb{E} e^{i \theta I({g}) } = \exp \left( \int_0^T (e^{i \theta {g}(s)}
  - 1) n(ds) \right).$$ For more details about Poisson integrals and some discussion of applications, see @kingman:1993, Chapter 3.

It is important to note that in the case where $n$ is a finite measure on $(0,T)$, the distribution of $I(g)$ is that of a compound Poisson distribution. This can be seen in the case where $g$ is strictly increasing and has inverse $g^{-1}$ by making a change of variable $u = g(s)$ in the integral in (\[e:poischarfunc\]): $$\exp \left( \int_0^T (e^{i \theta {g}(s)}
  - 1) n(ds) \right) = \exp\left( \int_{g^{-1}(0)}^{g^{-1}(T)} (e^{i
    \theta u} - 1) \bar{n}(u) du \right)$$ where $\bar{n}(u) =  (g^{-1})'(u) n(g^{-1}(u))$, which is the characteristic function of a compound Poisson distribution (see Proposition 1.2.11 in @Applebaum:2004). Thus, $I(g)$ in this case has a compound Poisson distribution with rate $r = \int_{g^{-1}(0)}^{g^{-1}(T)} \bar{n}(u) du = \int_0^T n(s) ds$ and jump distribution with density $r^{-1} \bar{n}(u)$, $g^{-1}(0) < u
< g^{-1}(T)$. A similar argument shows this for non-monotone $g$, except one must construct $\bar{n}$ carefully by breaking the integral (\[e:firstpoisint\]) into pieces on which $g$ is either flat or strictly monotone. Thus, by considering stochastic integrals of this type, we are covering a large class of interesting distributions.

The distribution of integrals such as (\[e:firstpoisint\]) would be easy to obtain if the measure $N$ was Gaussian. In this case $I({g})$ is also Gaussian: $I({g}) \sim N(0,\int_0^T {g}^2(s) n(s) ds )$. Since $N$ is Poisson, however, the integral $I({g})$ is not in general Poisson and its distribution is not easy to determine. Our goal here is to study the cumulative distribution function (CDF) of $I({g})$, which we denote by ${F}(x) = \mathrm{Prob}(I({g}) \leq x)$ and develop a convenient numerical scheme to evaluate it. In particular, we focus on the following:

-   A Kolmogorov-Feller type evolution equation associated to ${F}$.

-   Smoothness properties of ${F}$. More specifically, we show that under certain assumptions on ${g}$ and $n$, ${F}$ lives in the Hölder space $C^{0,\gamma}(({g}(0),{g}(T))$, for some $0<\gamma \leq 1$ depending on ${g}$.

-   A numerical method for computing ${F}$.

At first glance, one might attempt to compute the CDF ${F}$ using the characteristic function (\[e:poischarfunc\]) and the integration-based inversion methods of Abate and Whitt @abate:1992. For continuous ${F}$, their approach boils down to computing the following integral numerically: $$\label{e:abatesmet}
{F}(x) = \frac{ 2 }{ \pi } \int_0^\infty \mathrm{Re}(\phi_{g})(u) \frac{\sin x u}{u} du.$$ However, this method is not always efficient in this setting for multiple reasons. First, evaluating the characteristic function $\phi_{g}$ is not always easy, since $\int_0^T (e^{i \omega
    {g}(s)} - 1)n(ds)$ is unlikely to have a closed form, and numerically computing this integral might be difficult. This adds another source of error on top of the "truncation" and "discretization" errors associated with the integration of (\[e:abatesmet\]). Moreover, these errors are difficult to bound exactly. Secondly, we will see in the following that ${F}$ is not differentiable in general, which translates to a slow rate of decay of $\phi_{g}$. This makes numerical integration difficult.

We propose an alternative method for computing ${F}$ which does not involve (directly) the characteristic function (\[e:poischarfunc\]). Our method has several advantages over brute-force integration of (\[e:abatesmet\]). First, our method only requires knowing ${g}$ and the density of the control measure $n$, and thus is much faster than integration methods which must evaluate the characteristic function (\[e:poischarfunc\]). Second, we provide here error bounds given general assumptions on ${g}$ and $n$. Third, our method generates the CDF ${F}$ on an entire interval instead of a single point. Fourth, we obtain the more general cumulative distribution functions ${F}(x,t)$, $t \geq 0$, of the following <span>*stochastic process*</span>: $$\label{e:xzeroplusint}
X(t) = X_0 + \int_0^t {g}(s) N(ds), \quad 0 \leq t \leq T,$$ where $X_0$ is an independent random variable with given CDF ${F}_0(x)$. In the sequel, we illustrate some of these advantages on an example.

Our method involves solving an evolution equation satisfied by the CDF of $X(t)$ with initial condition ${F}_0$. A nice way to view such an evolution equation is to consider the characteristic function $\phi_{g}(\omega,t)$ of (\[e:xzeroplusint\]) (we will from hereon drop the "${g}$" subscript from $\phi$). Using (\[e:poischarfunc\]), we have at time $0 \leq t
\leq T$, $$\phi(\theta,t) = \phi_0(\theta)  \exp \left( \int_0^t (e^{i \theta {g}(s)}
  - 1) n(ds) \right),$$ where $\phi_0$ is the characteristic function of $X_0$. Differentiating with respect to $t$ gives $$\label{e:poisftODE}
{\frac{\partial}{\partial t}}\phi(\theta,t) = \left( (e^{i \theta {g}(t)}
  - 1) n(t)  \right) \phi(\theta,t).$$ Thus, the characteristic function $\phi(\omega,t)$ can be viewed as the solution at time $t$ of the simple ordinary differential equation (\[e:poisftODE\]) with initial condition $\phi(\theta,0) =
\phi_0(\theta)$. With this ODE perspective, the naive approach of brute-force integration can be thought of as a two step process: (i) evolving $\phi_0$ under the trivial dynamics of (\[e:poisftODE\]) to obtain $\phi(\theta,t)$, and then (ii) computing (\[e:abatesmet\]) to get ${F}$.

An alternative approach of obtaining an evolution equation for ${F}$ is to notice that the process $X$ in (\[e:xzeroplusint\]) is a continuous time Markov process, hence it satisfies the <span>*Kolmogorov-Feller forward equation*</span> (@kannan:1979, Section 5.1). In the infinitesimal time interval $[t,t+dt)$, $X$ may take a jump of size ${g}(t)$ with probability $n(t) dt + o(dt)$, thus, the Kolmogorov-Feller equation for the single-time density $p(x,t)$ of the process $X$ takes the form $$\label{e:genKol}
\frac{\partial}{\partial t} p(x,t)  = - n(t) (p(x,t) - p(x - {g}(t) ,t)), \quad t \geq 0, \ x \in \mathbb{R}.$$ Integrating this equation suggests that a similar equation should hold for ${F}$, however some technicalities arise because $p$ can contain "atoms". We show directly that a similar equation holds for the CDF, with the exception of points where the CDF is discontinuous. We then solve this evolution equation numerically using a finite-difference scheme.

This paper is outlined as follows. In Section \[s:mainthm\], we state a theorem which gives an evolution equation of the function ${F}$. We then study the smoothness of the function ${F}(\cdot,t)$ in Section \[s:holder\]. We then describe in Section \[s:methods\] a numerical method for calculating ${F}$ using a finite-difference scheme, and provide a rate of convergence for our method. In Section \[s:examples\], we apply our methods to a collection of examples and in Section \[s:approx\], we establish lemmas related to the quality of the approximation. Finally, in Section \[s:software\] we provide a guide to the software, written in MATLAB, which allows the user to obtain the cumulative distribution function and density function of the integral $\int_0^T
{g}(s) N(ds)$ for general ${g}$.

Kolmogorov-Feller equation for ${F}$ {#s:mainthm}
====================================

In this section we show that the CDFs ${F}(x,t)$, $ t \geq 0$ of $X(t)$ satisfy a Kolmogorov-Feller-type equation. As mentioned in the introduction, the form of this equation is easy to guess based on the Kolmogorov-Feller equation (\[e:genKol\]) satisfied by the density of the process $X(t)$.

Since we will be dealing with distribution functions, we must be mindful of discontinuities which may arise. Given a CDF ${F}$, we will let $C({F})$ denote the points of continuity of ${F}$. Also, we define the *right*-time derivative as $$\frac{\partial}{\partial t^+} {F}(x,t) = \lim_{h \rightarrow 0+}
\frac{{F}(x,t+h) - {F}(x,t)}{h}.$$

The following theorem specifies the equation for ${F}$ which will be used the sequel.

\[t:mainthm\] Let ${g}(s), \ s \geq 0$ be a right-continuous function satisfying (\[e:poiscond\]), and consider the process $$X(t) = X_0 + \int_0^t {g}(s) N(ds), \quad 0 \leq t \leq T,$$ where $N$ is a Poisson random measure with control measure $n(ds) =
n(s)ds$ and $X_0$ is a given random variable. Let ${F}(x,t)$ be the CDF of $X$ at time $t$. Then, for all $(x,t)$ such that $x-{g}(t) \in C({F}(\cdot,t))$, ${F}$ satisfies the following equation: $$\label{e:mainde}
\frac{\partial}{\partial t^+} {F}(x,t)  = -n(t)({F}(x,t) - {F}(x-{g}(t),t)).$$

Let $x,t \geq 0$ such that $x - {g}(t) \in C({F})$ and let $h>0$. Consider the difference $${F}(x,t+h) - {F}(x,t) = \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x]}(X(t+h)) -  {\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t))].$$ By conditioning on the number $N$ of Poisson arrivals in the interval $[t,t+h)$, the expectation on the right-hand side becomes $$\mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x]}(X(t+h)) -  {\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t))]
= \sum_{n=0}^\infty  \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x]}(X(t+h)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t)) | N=n]\ {\mathrm{Prob}}[N=n]$$ $$\label{e:cond}
=  \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x)}(X(t+h)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t)) | N=1]  \left( \int_t^{t+h} n(\tau)d\tau \right)
e^{-\int_t^{t+h} n(\tau)d\tau} + O(h^2).$$ Here we have used that facts that if $N=0$, $X(t)  = X(t+h)$, and the probability of seeing two or more Poisson arrivals in the interval $[t,t+h)$ is $O(h^2)$ since we've assumed $n$ is continuous. In the event of one arrival in $[t,t+h)$, namely $N=1$, we have $X(t+h) = X(t) + {g}(S)$, where $S \in [t,t+h)$ is a random time with density $$S \sim f_S(s) =  \begin{cases} \displaystyle \frac{n(s)}{\int_t^{t+h} n(\tau) d\tau}, \quad s
  \in [t,t+h) \\ 0, \qquad \qquad \qquad \mathrm{else} \end{cases}.$$ Conditioning on $S$, (\[e:cond\]) now becomes $$\left( \int_t^{t+h} \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x]}(X(t)+{g}(s)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t)) \ | \ S = s]  f_S(s) ds \right) \left( \int_t^{t+h} n(\tau)d\tau \right)
e^{-\int_t^{t+h} n(\tau)d\tau} + O(h^2)$$ $$= \left( \int_t^{t+h} \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x]}(X(t)+{g}(s)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t))] n(s) ds \right)
e^{-\int_t^{t+h} n(\tau)d\tau} + O(h^2)$$ $$=\left( \int_t^{t+h} \mathbb{E}[ {\mbox{\boldmath$1$}}_{(-\infty, x-{g}(s)]}(X(t)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t))] n(s) ds \right)
e^{-\int_t^{t+h} n(\tau)d\tau} + O(h^2)$$ $$= \left( \int_t^{t+h} ({F}(x-{g}(s),t) - {F}(x,t) )n(s) ds \right)
e^{-\int_t^{t+h} n(\tau)d\tau} + O(h^2).$$ Now, since ${F}(\cdot,t)$ is continuous at $x-{g}(t)$, ${g}$ is right continuous, and $n$ is continuous, let $h \rightarrow 0^{+}$ and get $$\begin{aligned}
\lim_{h\rightarrow 0^+} \frac{{F}(x,t+h) - {F}(x,t)}{h} &=& \lim_{h
  \rightarrow 0^+}  \left( h^{-1} \int_t^{t+h} ({F}(x-{g}(s),t) - {F}(x,t) )n(s) ds \right)
e^{-\int_t^{t+h} n(\tau)d\tau}   \label{e:takelim} \\
&=& n(t) ({F}(x - {g}(t),t) - {F}(x,t)),\end{aligned}$$ which completes the proof.

<span>**Remarks.**</span>

-   If ${F}$ and ${g}$ are continuous, then the right and left time derivatives of ${F}$ coincide and the left hand side of (\[e:mainde\]) can be replaced with ${\frac{\partial}{\partial t}}{F}(x,t)$.

-   If $ x - g(t) \notin C({F})$ and ${g}\geq 0$ is continuous and monotone increasing, then $ x- {g}(s) \nearrow x - {g}(t)$ as $s \searrow t$ and the limit in (\[e:takelim\]) still exists, except we have instead $$\label{e:leftversion}
    \frac{\partial {F}}{\partial t^{+}} = n(t) ( {F}^{-}(x-g(t),t) - {F}(x,t)),$$ where ${F}^{-}$ is the left-continuous version of ${F}$, i.e. ${F}^{-}(x,t) = \lim_{y \rightarrow x^- }{F}(y,t)$. This fact will be used in the sequel.

-   The continuity set $C({F})$ can be identified from ${g}$ and $n$ as follows. We can write $$I({g}) = X_0 +  \int_0^t {g}(s) N(ds) = X_0 + \sum_{i=1}^N {g}(S_i),$$ where $N$ is a Poisson random variable with mean $\int_0^t n(s) ds$. Then, the atoms of $I({g})$ correspond to the atoms of the random sums $ X_0 + \sum_{i=1}^n {g}(S_i)$, with $n=0,1,2,\dots$ and $S_i$ are the "Poisson events", which are i.i.d. with density $$\frac{n(s)}{\int_0^t n(\tau) d \tau}, \quad 0 < s < t.$$ The continuity set $C({F})$ is the complement of this set of atoms.

    For example, if $X_0 = 0$, ${g}\equiv \eta$ is a constant function, and $n(s) \equiv 1$, then the atoms of the random sums $\sum_{i=1}^N g(S_i)$, which is the set $\{n\eta,n=0,1,2,\dots \}$.

-   To arrive at Theorem \[t:mainthm\], we used properties of the Poisson integral to derive the evolution equation (\[e:mainde\]). This reasoning can also be turned on its head – this theorem can give a probabilistic interpretation to initial value problems for a class of differential-difference equations of the form $$\label{e:PoisIVP}
    \begin{cases}  \displaystyle\frac{\partial u}{\partial t^{+}}  = - n(s) ( u(x,t) - u(x - {g}(t) , t ) ) , \quad x \in \mathbb{R}, t \geq 0 \\
    u(x,0) = u_0(x) \end{cases},$$ where $n$, ${g}$ and $u_0$ are given functions and $u$ is an unknown function of $x$ and $t$. By computing the CDF of the Poisson stochastic integral (\[e:firstpoisint\]), we are essentially computing the <span>*fundamental solution*</span> of this differential-difference equation, since the solution to (\[e:PoisIVP\]) can be written as the convolution of $u_0$ with the CDF ${F}(x,t)$ of the integral (\[e:firstpoisint\]) up to time $t$: $$\label{e:ddtruesol}
     u(x,t) = \int_{-\infty}^\infty u_0(x - u) d{F}(u,t).$$

    To illustrate this point, consider the following example: Let $b(t), \ t \geq 0$ be a given smooth function with derivative $b'(t)$, and recall the classical transport PDE: $$\label{e:transport}
    \begin{cases}  \displaystyle \frac{\partial u}{\partial t} = -b'(t) \frac{\partial u}{\partial x}, \quad x \in \mathbb{R}, t \geq 0 \\
    u(x,0) = u_0(x)  \end{cases},$$ where, for simplicity, the initial condition $u_0$ is some smooth and bounded function. The solution to this equation is given by $$\label{e:soldrift}
    u(x,t) = u_0( x - b(t) ), \quad t \geq 0.$$ Now, let $h > 0$, and say we want to interpret the solution to the following variation of (\[e:transport\]) where we replace $\partial u/\partial x$ with a finite-difference approximation: $$\label{e:transport1}
    \begin{cases}  \displaystyle \frac{\partial u}{\partial t} = -b'(t) \frac{ u(x,t) - u(x - h,t)  }{ h }, \quad x \in \mathbb{R}, t \geq 0 \\
    u(x,0) = u_0(x)  \end{cases}.$$ Notice that (\[e:transport1\]) is of the form (\[e:mainde\]) with ${g}(t) \equiv h$, and $n(t) = b'(t)/h$. This corresponds to the trivial Poisson random integral $$\int_0^t h N(ds), \quad n(s) = \frac{b'(s)}{h},$$ which has the distribution of the random variable $h N([0,t])$, where $N([0,t])$ has a Poisson distribution with mean $ b(t) h^{-1} $.

    Observe that in this case, (\[e:ddtruesol\]) can be expressed as $u(x,t) = \mathbb{E}u_0(x - hN([0,t]))$ which is the convolution of $u_0$ with the CDF of $h N([0,1])$. Compare this to the solution of the classical transport equation (\[e:soldrift\]).

Smoothness of ${F}(\cdot,t)$ {#s:holder}
============================

Our goal is to develop a numerical scheme for approximating the CDF ${F}$ which is based on the differential-difference equation (\[e:mainde\]). In order to estimate the error in our approximation to the true CDF, we must have some smoothness properties for ${F}$, and thus make some assumptions on ${g}$. We will assume that ${g}$ has a continuous inverse. While this seems like a restrictive assumption, we discuss ways of generalizing our method to non-invertible ${g}$ in section (\[s:extend\]).

In the following, we assume that ${g}$ is a non-negative, strictly monotone continuous function on $[0,t]$ with inverse ${g}^{-1}$. We will also suppose that $n(s)$ is a bounded function. Since ${g}\geq 0$, the integral $\int_0^t {g}(s)N(ds)$ is zero if there are no Poisson events in $[0,t)$, i.e. if $N[0,t) =0$ which happens with probability $e^{-\int_0^t n(s) ds}$. Also, $\int_0^t {g}(s)N(ds) \geq {g}(0)$ if $N[0,t) \geq 1$. Therefore, ${F}(x,t) = 0$ for $x < 0$, ${F}$ has a jump of size $e^{-\int_0^t n(s)ds }$ at $x = 0$, and ${F}\equiv e^{-\int_0^t n(s)ds }$ on the interval $[0,{g}(0))$ (see Figure \[f:pcartoon\]). Having identified the discontinuity at $x=0$ in the CDF of ${F}$, we now focus on the following question: How smooth is ${F}$ for $x>0$? This will depend on ${g}$.

![ This shows the behavior of ${F}(x,t)$ near $x = 0$ with $t$ fixed. We see a jump of size $\exp(-\int_0^t n(s) ds )$ at $x=0$ which equals the probability of zero Poisson events in time $(0,t)$. Also, ${F}(x,t)$ is constant in the interval $[0,{g}(0))$ since with one or more Poisson event in $(0,t)$, ${g}(0)$ is the minimum value the integral can take. <span data-label="f:pcartoon"></span>](Pcartoon.eps){width="100.00000%"}

Let $U \subset \mathbb{R}$. For functions $u$ defined on $ U$ and for $0 < \gamma \leq 1$, recall the definition of the Hölder seminorm $[ \cdot ]_{C^{0,\gamma}(U) }$ and the Hölder space $C^{0,\gamma}( U )$ defined as $$\begin{aligned}
[u]_{C^{0,\gamma} (U) } &=& \sup_{ \underset{x\neq y } { x,y \in U  }}  \frac{ |u(x) - u(y)| }{ |x - y|^\gamma } \\
C^{0,\gamma}(U) &=& \{ u\ : \ [u]_{C^{0,\gamma}(U) } < \infty \}.\end{aligned}$$ The exponent $\gamma$ is called the Hölder exponent of $u$. For more on these spaces, see @evans:1998 section 5.1.

The next theorem shows that ${F}(x,t)$ for $x>0$ and $t>0$ lies in the same Hölder space as ${g}^{-1}$.

\[t:holder\] Let ${g}$ be a non-negative, strictly increasing continuous function on $[0,T]$ with inverse ${g}^{-1}$. For $0<t < T$ fixed, let ${F}(x,t) = \mathrm{Prob}[X(t) \leq x]$, where $X(t)$ is defined by $$X(t) =  \int_0^t {g}(s) N(ds),$$ where $N$ is a Poisson random measure with control measure $n(s)ds$ with $n$ a bounded function. Let $$n^{\star}_t = \sup_{0 \leq s \leq t} n(s).$$ Then, if ${g}^{-1} \in C^{0,\gamma}( ( {g}(0),{g}(t) ) ) $ with $0 < \gamma \leq 1$, then ${F}(\cdot,t) \in C^{0,\gamma}( (0,\infty) )$ and $$[ {F}(\cdot,t) ]_{C^{0,\gamma} (0,\infty)} \leq C_{n,t} \ [{g}^{-1}]_{C^{0,\gamma} ({g}(0),{g}(t))} ,$$ where the constant $C_{n,t}$ is given by $$C_{n,t} =  \frac{ (1 - e^{\int_0^t n(s)ds})}{\int_0^t n(s) ds} n^{\star}_t$$

Fix $t>0$ and let $S,S_1,S_2\dots$ be i.i.d. random variables with density $$\label{e:defofnbar}
n_t(s) = \frac{n(s)}{\int_0^t n(\tau) d \tau}, \quad 0 < s < t.$$ Let $\bar{n}_t(x) = \int_0^x n_t(s) ds $ be the CDF of $S$ and let $$\begin{aligned}
G(x) = \mathrm{Prob}[{g}(S) \leq x] &=& \begin{cases}  0 \quad x < {g}(0)  \\
\mathrm{Prob}[S < {g}^{-1}(x)] \quad {g}(0) \leq x \leq {g}(t) \\
1 \quad  x > {g}(t) \end{cases} \nonumber  \\ 
&=& \begin{cases} 0 \quad x < {g}(0)  \\
\bar{n}_t({g}^{-1}(x)) \quad {g}(0) \leq x \leq {g}(t) \\
1 \quad  x > {g}(t) \end{cases}.  \label{e:defofGnbar}\end{aligned}$$ By conditioning on the number of arrivals $N$ in the interval $[0,t]$, we have for $ x,y > 0 $, $$|{F}(x,t) - {F}(y,t)| = \left| \sum_{n=1}^\infty \left( \mathrm{Prob}[\sum_{i=1}^n {g}(S_i) \leq x] - \mathrm{Prob}[\sum_{i=1}^n {g}(S_i) \leq y] \right) P_n\right|$$ where $P_n = \mathrm{Prob}[N=n]$. Let $G^{\star n}$ denote the n-fold convolution of $G$ with itself. Now we have $$\begin{aligned}
|{F}(x,t) - {F}(y,t)| &\leq& | G(x) - G(y) | P_1 + \sum_{n=2}^\infty | G^{\star n}(x) - G^{\star n}(y) | P_n \nonumber \\
&=&  | G(x) - G(y) | P_1 + \sum_{n=2}^\infty \left| \int_0^x G(x-u) G^{\star (n-1)}(du) - \int_0^y G(y-u) G^{\star (n-1)}(du) \right| P_n \nonumber \\
&\leq&  | G(x) - G(y) | P_1 + \sum_{n=2}^\infty \int_0^{\max(x,y)} |G(x-u) -G(y-u)| G^{\star (n-1)}(du) P_n \end{aligned}$$ Thus, for $0 < \gamma \leq 1$, $$\begin{aligned}
\frac{|{F}(x,t) - {F}(y,t)| }{ |x - y|^\gamma } &\leq& \frac{| G(x) - G(y) | }{ |x - y|^\gamma } P_1 + \sum_{n=2}^\infty \int_0^{\max(x,y)} \frac{| G(x-u) - G(y-u) | }{ |x - y|^\gamma } G^{\star (n-1)}(du) P_n  \\
&\leq&  [G]_{ C^{0,\gamma} ((0,\infty)) } \sum_{n=1}^\infty P_n \\
&=&  ( 1 - e^{-\int_0^t n(s) ds })  [G]_{ C^{0,\gamma} ((0,\infty)) } \label{e:bound1}\end{aligned}$$

What remains is to show that $ [G]_{ C^{0,\gamma} ((0,\infty)) } $ is bounded by a constant multiple of $[{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) }$. Observe that $\bar{n}'_t(x) = n_t(x)$ where $n_t$ is defined in (\[e:defofnbar\]) and thus $|\bar{n}_t'(x)| \leq n^{\star}_t \cdot  (\int_0^t n(s) ds)^{-1}$, where $n_t^{\star} = \sup_{0 \leq s \leq t} n(s)$. In view of (\[e:defofGnbar\]), the mean value theorem implies that for ${g}(0) \leq x,y \leq {g}(t)$, $$\frac{|G(x) - G(y)|}{|x-y|^\gamma} =\frac{ |\bar{n}_t({g}^{-1}(x)) -  \bar{n}_t({g}^{-1}(y))| }{|x-y|^\gamma}  \leq \frac{n^{\star}_t}{\int_0^t n(s) ds} \frac{ |{g}^{-1}(x) -  {g}^{-1}(y)| }{|x-y|^\gamma} \leq \frac{n^{\star}_t}{\int_0^t n(s) ds}  [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) } .$$ If $0 < x < {g}(t) \leq y$, then $G(y) = 1 = \bar{n}_t(t) = \bar{n}_t( {g}^{-1}({g}(t)))$ and $$\frac{|G(x) - G(y)|}{|x-y|^\gamma} \leq \frac{|\bar{n}_t({g}^{-1}(x)) - \bar{n}_t({g}^{-1}({g}(t)))   |}{|x-{g}(t)|^\gamma} \leq   \frac{n^{\star}_t}{\int_0^t n(s) ds}   [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) }.$$ A similar argument shows this also holds for $x < {g}(0) < y$. Finally, if $x,y \geq {g}(t)$ or $x,y \leq {g}(0)$, then $$G(x) - G(y)  = 0 \leq  \frac{n^{\star}_t}{\int_0^t n(s) ds}  [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) }.$$ Thus, in all cases, $$\label{e:bound2}
\frac{|G(x) - G(y)|}{|x-y|^\gamma}  \leq   \frac{n^{\star}_t}{\int_0^t n(s) ds}   [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) }.$$ Hence, (\[e:bound1\]) and (\[e:bound2\]) imply $$[{F}(\cdot,t)]_{C^{0,\gamma}((0,\infty))}  \frac{ n^{\star}_t ( 1 - e^{-\int_0^t n(s) ds })}{\int_0^t n(s) ds}  [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) } = C_{n,t} \ [{g}^{-1}]_{ C^{0,\gamma}({g}(0),{g}(t)) }  .$$ which finishes the proof.

In the preceding Theorem, we assumed $g$ is monotone. What happens if ${g}$ is piecewise monotone, i.e. ${g}(t)$ is monotone on the intervals $[t_i,t_{i+1})$, for $i=0,1,\dots,M$? Then, the integral of ${g}$ over $[t_0,t_M)$ can be "constructed" inductively by considering the sums $$\label{e:poissummands}
I_i = I_{i-1} + \int_{t_{i-1}}^{t_i} {g}(s) N(ds), \quad i=1,2,\dots,M$$ with $I_0 = 0$. Since $N$ is a Poisson measure, the summands in (\[e:poissummands\]) are independent random variables. Hence, the full CDF of $\int_{t_0}^{t_M}{g}(s)N(ds)$ can be seen as the successive convolution of the CDFs of the $I_i$'s above with the CDFs of the integrals $\int_{t_{i-1}}^{t_i}{g}(s) N(ds)$. We know the smoothness of the CDF of each integral, but what about the smoothness of a convolution of two such CDFs? The following corollary shows that the Hölder exponent associated to the convolution of any two of these CDFs will, at worst, be the lesser of the two Hölder exponents associated to the individual CDFs.

\[c:sumIs\] Let ${g}$, $n$ and $X(t)$ and ${F}$ be as in Theorem (\[t:holder\]), and suppose $X_0$ is a non-negative random variable independent of $X(t)$ with CDF ${F}_0 \in C^{0,\gamma_0}(0,\infty)$. Then, the CDF $\bar{{F}}$ of the sum $X_0+ X(t)$ lies in the Hölder space $C^{0,\bar{\gamma}}(0,\infty)$, where $\bar{\gamma} = \min(\gamma,\gamma_0)$, and $$[\bar{{F}}]_{C^{0,\bar{\gamma}}(0,\infty)} \leq \begin{cases} [{F}]_{C^{0,\gamma}(0,\infty)} + \max(1,[{F}_0]_{C^{0,\gamma_0}(0,\infty)}), \qquad \gamma_0 > \gamma \\
[{F}]_{C^{0,\gamma}(0,\infty)}  + [{F}_0]_{C^{0,\gamma_0}(0,\infty)},  \qquad \qquad \gamma_0 = \gamma \\
[{F}_0]_{C^{0,\gamma_0}(0,\infty)} + \max(1,[{F}]_{C^{0,\gamma}(0,\infty)}), \qquad \gamma_0 < \gamma \end{cases}$$

Let $0 < y < x$. Observe first that if $\gamma > \bar{\gamma}$, then $$\begin{aligned}
[{F}]_{C^{0,\bar{\gamma}}} \leq \frac{\
{F}(x) - {F}(y)}{|x-y|^{\bar{\gamma}}} &\leq& \begin{cases} 1, \qquad |x - y| \geq 1 \\ \nonumber
\displaystyle \frac{{F}(x) - {F}(y)}{|x - y|^{\gamma}}, \quad |x-y| < 1 \end{cases} \\
 &\leq& \max(1, [{F}]_{C^{0,\gamma}(0,\infty)} ) . \label{e:holderinq1}\end{aligned}$$ Similarly, if $\gamma_0 > \bar{\gamma}$, we have $$[{F}_0]_{C^{0,\bar{\gamma}}} \leq \max(1, [{F}_0]_{C^{0,\gamma_0}(0,\infty)} ) . \label{e:holderinq2}$$

To compute the Hölder norm to $\bar{{F}}$, we write it as the convolution of $F$ and $F_0$: $$\label{e:fbar2p}
\bar{{F}}(x) - \bar{{F}}(y) = \int_0^\infty ({F}(x - u) - {F}(y-u)) dF_0(u).$$ Since ${F}= 0$ on the negative real axis, the above simplifies to $$\bar{{F}}(x) - \bar{{F}}(y) = \int_0^y ({F}(x - u) - {F}(y-u)) dF_0(u) + \int_y^x {F}(x - u) dF_0(u). \label{e:splitFbar}$$ Now, Theorem (\[t:holder\]) and (\[e:holderinq1\]) imply that $$\begin{aligned}
\frac{|\int_0^y ({F}(x - u) - {F}(y-u)) d{F}_0(u) |}{|x - y|^{\bar{\gamma}}} &\leq & \int_0^y \frac{|{F}(x - u) - {F}(y-u)|}{|x-y|^{\bar{\gamma}}} d{F}_0(u)   \nonumber\\ 
& \leq & \begin{cases} [{F}]_{C^{0,\gamma}(0,\infty)}, \qquad \gamma = \bar{\gamma} \\
\max(1, [{F}]_{C^{0,\gamma}(0,\infty)} )\qquad \gamma > \bar{\gamma} \end{cases}. \label{e:gamgamp}\end{aligned}$$ And, (\[e:holderinq2\]) implies $$\frac{\int_y^x {F}(x - u) d{F}_0(u)}{|x - y|^{\bar{\gamma}}} \leq \frac{{F}_0(x) - {F}_0(y)}{|x - y|^{\bar{\gamma}}} \leq \begin{cases}  [{F}_0]_{C^{0,\gamma_0}(0,\infty)}, \qquad \gamma_0 = \bar{\gamma} \\
\max(1, [{F}_0]_{C^{0,\gamma_0}(0,\infty)} )\qquad \gamma_0 > \bar{\gamma} \end{cases}. \label{e:gam0gamp}$$ Thus, (\[e:splitFbar\]), together with (\[e:gamgamp\]) and (\[e:gam0gamp\]) imply the result.

Corollary \[c:sumIs\] points to a possible "worst case" result about the smoothness of a convolution of two CDFs with different smoothness properties on $(0,\infty)$ by saying this convolution $\bar{F}$ on $\{x > 0\}$ will lie in the larger of two Hölder spaces ($C^{0,\gamma}(0,\infty)$ and $C^{0,\gamma_0}(0,\infty)$). This worst case occurs if ${F}$ and ${F}_0$ are both discontinuous at $x = 0$, as indicated in the following corollary.

\[c:worstcase\] Under the assumptions of Corollary \[c:sumIs\], suppose further that ${F}_0$ has a discontinuity at $x=0$ and that $C^{0,\gamma}(0,\infty)$ and $C^{0,\gamma_0}(0,\infty)$ are the smallest Hölder spaces to contain ${F}$ and ${F}_0$, respectively. Then, $C^{0,\bar{\gamma}}(0,\infty)$ is the smallest Hölder space to contain $\bar{F}$.

Notice that if ${F}_0$ and ${F}$ are discontinuous at $x=0$, the quotients (\[e:gamgamp\]) and (\[e:gam0gamp\]) can also be bounded below as $$\begin{aligned}
\frac{\int_0^y ({F}(x - u) - {F}(y-u)) d{F}_0(u) }{|x -
  y|^{\bar{\gamma}}} &\geq& \frac{ {F}(x) - {F}(y)  } {|x -
  y|^{\bar{\gamma}}} ({F}_0(0) - {F}_0(0^{-})) \\
\frac{\int_y^x {F}(x - u) d{F}_0(u)}{|x - y|^{\bar{\gamma}}} &\geq&
{F}(0)  \frac{{F}_0(x) - {F}_0(y)}{|x - y|^{\bar{\gamma}}} \end{aligned}$$ And thus it follows from (\[e:splitFbar\]) that if $C^{0,\gamma}$ and $C^{0,\gamma_0}$ are the smallest Hölder spaces to contain ${F}$ and ${F}_0$, respectively, then taking supremums over all $x$ and $y$ above will cause one of these two ratios to become infinite if $\bar{\gamma} > \min(\gamma,\gamma_0)$. Thus, (\[e:fbar2p\]) implies that $C^{0,\bar{\gamma}}$ is the smallest Hölder space to hold $\bar{F}$ on $\{x > 0\}$.

Notice that for sums like (\[e:poissummands\]), the corresponding CDFs will typically contain a jump at $x = 0$, thus the "worst case" is actually what occurs.

Obtaining ${F}(x,t)$ {#s:methods}
====================

There are standard finite-difference schemes for solving linear PDEs (see for instance @kincaid:1996, Chapter 9). In this section, we describe such a scheme which can be used to solve (\[e:mainde\]) iteratively on the interval $0 \leq t \leq T$. We also study its convergence properties.

To begin, we need to define various components of a discrete approximation of ${F}(x,t)$ which we will denote ${F}(j \delta, i h)$ and define as follows. Fix an interval $ [0,L] $ and subdivide it with a step size of $\delta$. That is, consider $$\begin{aligned}
\Delta_{\delta} &=& \{  j \delta \ : \  0 \leq j \leq L/\delta \} \nonumber \\
&=& \{ x_0 < x_1 < x_2 \dots < x_M \},\label{e:defofDelta}\end{aligned}$$ where $$\label{e:defofM}
M = |\Delta_\delta| = L/\delta +1$$ is the size of the mesh (assume $L/\delta$ is an integer). We will also use a time step $h >0$ and consider the time points $\{ i h, \ i = 0,1,\dots,N \}$, where $N = T/h$. Given a mesh $\Delta_\delta$, for each integer $ 0 \leq i \leq N $ define the column vector $\mathbf{{F}}^i \in \mathbb{R}^M$ as $$\label{e:colF}
\mathbf{{F}}^i = \left(  \begin{array}{c}  
{F}^i_0 \\
{F}^i_1 \\
{F}^i_2 \\
\vdots \\
{F}^i_M \end{array} \right),$$ with ${F}^i_j = {F}(  j \delta, i h)$. In order to measure "closeness" on this mesh, we will use the following discrete $L^1$ norm defined on $\Delta_\delta$: $$\label{e:epsnorm}
\| \mathbf{u} \| _{1} = \sum_{j=0}^M \delta |u_j|, \qquad \mathbf{u} \in \mathbb{R}^M.$$ Recall that for a $M \times M$ matrix $A = (a_{i,j})_{i,j=0}^M$, the $L^{1}$ norm of $A$ is given by its maximal absolute column sum (@kincaid:1996, problem 4.4.11): $$\label{e:Anorm}
\| A \|_{1} = \max_{j=0,1,\dots,M} \sum_{i=0}^M |a_{i,j}|.$$

Finite-Difference Scheme for computing ${F}(x,t)$
-------------------------------------------------

We begin by rewriting equation (\[e:mainde\]) as $$\label{e:defoff}
{\cal P }[{F}] \equiv \frac{\partial}{\partial t^+} {F}(x,t) + n(t)({F}(x,t) - {F}(x-{g}(t),t)) = 0,$$ where ${\cal P}$ is a linear operator defined on a suitable function space. We must first choose a discrete approximation of ${\cal P}$. For the time derivative, we use the usual forward difference approximation: $$\frac{\partial}{\partial t^+}{F}(x_j,t_i) \approx \frac{{F}^{i+1}_j- {F}^i_j}{h},$$ where the ${F}^{i}_j$ are defined in (\[e:colF\]). For the difference ${F}(x,t) - {F}(x-{g}(t),t)$, we use a linear interpolation $$\label{e:linearinterp}
{F}(x_j,t_i) - {F}(x_j-{g}(t_i),t_i) \approx {F}^i_j - (1 - \lambda_i) {F}^i_{j - k_i} + \lambda_i {F}^i_{j - k_i + 1},$$ where the integer $k_i$ satisfies $x_{j-k_i} < x_j - {g}(t_i) < x_{j-k_i+1} $, and $\lambda_i  =   
\delta^{-1}( x_j - {g}(t_i) -x_{j-k_i} )$. In terms of $\delta$ and $h$, these are given by $$\label{e:defofk}
k_i = \left\lfloor \frac{{g}(i h)}{\delta} \right\rfloor + 1,   \qquad \lambda_ i = \frac{|\delta k_i - {g}(ih)|}{\delta}.$$ See Figure \[f:FDcartoon\].

![ Relationship between $x_j$, ${g}(t_i)$, $k_i$, $\delta$ and $\lambda_i$. <span data-label="f:FDcartoon"></span>](FDcartoon.eps){width=".8\textwidth"}

Putting these approximations together, we define the *forward difference* operator ${\cal P}_{g}: \mathbb{R}^M \rightarrow \mathbb{R}^M$ as $$\label{e:def_of_Ff}
({\cal P}_{g}[\mathbf{{F}}^i])_j = \frac{ {F}^{i+1}_j - {F}^{i}_j}{h} + n(i h) ({F}^i_j - (1-\lambda_i) {F}^i_{j - k_i} + \lambda_i) {F}^i_{j - k_i + 1} )$$ where $k_i,\lambda_i$ are defined in (\[e:defofk\]). In view of (\[e:defoff\]), we require the sequence $\mathbf{{F}}^i$ satisfy $$\label{e:forwarditer}
{\cal P}_{g}[\mathbf{{F}}^i] = 0, \qquad i=1,2,\dots.$$ From (\[e:def\_of\_Ff\]), (\[e:forwarditer\]) can we written as $$\label{e:timestepup}
{F}^{i+1}_j = {F}^i_j - h n( i h ){F}^i_j +  h  (1 - \lambda_i) {F}^i_{j - k_i} + h \lambda_i  {F}^i_{j - k_i + 1},$$ We can write this in matrix form. Since $N$ is the size of time ($i$) mesh and $M$ is the size of the space ($j$) mesh, we can express (\[e:timestepup\]) as $$\mathbf{{F}}^{i+1} = A^{i} \mathbf{{F}}^{i}, \qquad i=1,2,\dots,N,$$ where $A^{i}$ is the $M\times M$ matrix[^4] defined as $$\label{e:defofAmatrix}
A^i = (1 - n(i h) h) \mathbf{I}_{M \times M} +  \left( \begin{array}{cc} 
\mathbf{0}_{(k-1) \times (M-k+1)}  & \mathbf{0}_{(k-1) \times (k-1)} \\
\tilde{A}^i & \mathbf{0}_{(M-k+1) \times (k-1)} \end{array} \right),$$ where $\mathbf{I}_{M \times M}$ denotes the $M \times M$ identity matrix, and $\mathbf{0}_{M \times N}$ is a $M \times N$ zero matrix, and the $(M-k_i+1) \times (M-k_i+1)$ matrix $\tilde{A}^i$ is $$(\tilde{A}^i)_{mn}  = \begin{cases}  h \lambda_i  n(i h), \quad m=n \\
h (1 - \lambda_i) n(i h) \quad m = n+1 \\
0 \quad \mathrm{else} \end{cases}.$$ With this, $\mathbf{{F}}^i$ is easily calculated as $$\mathbf{{F}}^i = A^{i} A^{i-1} \dots A^1 \mathbf{{F}}^0.$$ where the initial condition $\mathbf{{F}}^0$ is determined by the CDF of $X_0$ and is known exactly.

Error Analysis {#s:error}
--------------

In this section, we study the error associated with solving differential-difference equation (\[e:mainde\]) with the finite-difference method described in the previous section. We'll require the following assumptions on the kernel ${g}$ and control measure $n$: $$\begin{aligned}
&  \mbox{$\bullet$   ${g}$   is a monotone increasing function with H\"{o}lder
  continuous inverse ${g}^{-1}$ } \notag \\
& \mbox{$\bullet$  ${g}$ and $n$ are
  Lipschitz functions with} \label{e:gnassump} \\
&  \ \ \ |{g}(t) - {g}(s)| \leq L_{g}|s - t|,
  \quad |n(s) - n(t)| \leq L_{n} |s - t| \    \mbox{for constants $L_{g},L_n \geq 0$} \notag.\end{aligned}$$

We will see that our method gives accuracy of order $o( \delta^\gamma + h^{\gamma})$ in the discrete $L^1$ norm, where $\gamma$ is the Hölder exponent of ${g}^{-1}$. As above, $\delta$ is the size of the spacial mesh, and $h$ is the size of the temporal mesh.

We first consider the error associated with the approximations used in our discretization: $$\begin{aligned}
\frac{\partial {F}}{\partial t^{+}} (x_j,t_\ell) &\approx& \frac{{F}(x_j,t_\ell+h) - {F}(x_j,t_\ell)}{h} \\
{F}(x_j - {g}(t_\ell),t_\ell) &\approx&  (1 - \lambda_\ell) {F}(x_{j - k_\ell},t_\ell) + \lambda_\ell {F}(x_{j - k_\ell+1},t_\ell).\end{aligned}$$ Consider the meshes $0 = x_0 < x_1 < x_2 < \dots x_M$ and $0 = t_0 < t_1 < \dots < t_N$. For integers $0 \leq j \leq M$ and $0 \leq \ell \leq N$, define the absolute differences $$\begin{aligned}
S_{j,\ell}(h) &=& {F}(x_j,t_\ell + h) - {F}(x_j,t_\ell) - h \frac{\partial {F}}{\partial t^{+}}(x_j,t_\ell)   \label{e:defofS}  \\
R_{j,\ell}(\delta) &=&    ( (1 - \lambda_\ell) {F}(x_{j - k_\ell},t_\ell) + \lambda_\ell {F}(x_{j - k_\ell + 1} , t_\ell ))  - {F}(x_j - {g}(t_\ell),t_\ell)    . \label{e:defofR}\end{aligned}$$

In order to ensure convergence in our finite-difference scheme, these two errors must approach $0$ "fast enough" as $\delta,h \rightarrow 0$. Bounds for $S_{j,\ell}$ and $R_{j,\ell}$ are given in Lemmas \[l:Slem\] and \[l:Rlem\] in section \[s:approx\]. In short, these Lemmas imply the following: $$\begin{aligned}
|S_{j,\ell}(h)| &=& \begin{cases}  o(h^{1+\gamma}) \quad \mbox{if } x_j - g(t_{\ell+1}) \geq 0 \\
o(h) \quad \mbox{if } x_j - g(t_{\ell}) \geq 0 > x_j - g(t_{\ell + 1}) \\
o(h^2) \quad \mbox{if } x_j - g(t_\ell) < 0 \end{cases},  \\
|R_{j,\ell}(\delta)| &=& o(\delta^{\gamma}).\end{aligned}$$

For $\ell \geq 0$, let $\mathbf{{F}}_e^\ell \in \mathbb{R}^M$ be the vector of <span>*exact*</span> values of ${F}$ at time $t_\ell$, i.e. $$\label{e:Pexact}
 \mathbf{{F}}_e^\ell = \left( \begin{array}{c}
{F}(x_0,t_\ell) \\
{F}(x_1,t_\ell) \\
\vdots \\
{F}(x_M,t_\ell) \end{array} \right).$$ We will now state a theorem which shows that our method converges to the exact solution to (\[e:mainde\]) in the discrete $L^1$ norm with a convergence rate faster than a constant multiple of $(h^\gamma + \delta^\gamma)$, i.e. that $\| \mathbf{{F}}^\ell - \mathbf{{F}}^\ell_e\|_1 = o(h^\gamma +
\delta^\gamma)$ and $\delta, h \rightarrow 0$.

As the proof of the following theorem will show, we will require the following <span>*stability criterion*</span> on $h$ to guarantee convergence: $$\fbox{ $\mbox{Stability Criterion:      } \ \   h n^{\star}_T < 1.$ }$$ where $\displaystyle n^{\star}_T = \sup_{0 \leq s \leq T} n(s)$ and $h$ is the time step used in the finite-difference scheme. This can always be met easily if $n$ is bounded. This condition makes sense since the differential equation (\[e:mainde\]) holds because the probability of 2 or more Poisson arrivals in an infinitesimal time interval is negligible. Hence, when approximating (\[e:mainde\]) with a finite-difference method, we must ensure that the time step we consider is small enough relative to the control measure to make this probability small.

\[t:errorbound\] Let ${g}$ be a positive, continuous, and strictly increasing kernel with inverse ${g}^{-1} \in C^{0,\gamma}({g}(0),{g}(T))$ for some $0 < \gamma \leq 1$. Suppose the control measure $n(s)$ is a bounded function and set $n^{\star}_T = \sup_{0 \leq t \leq T} n(t)$. Let $\mathbf{{F}}_e^i$ be defined as in (\[e:Pexact\]) and let $\mathbf{{F}}^i$ $i=1,2,\dots,N$ be the approximations given by the forward difference scheme. Then, if $h n^{\star}_T < 1$, the forward difference scheme is convergent and satisfies $$\label{e:errorbound}
\| \mathbf{{F}}^N - \mathbf{{F}}_e^N \|_{1} = o(h^\gamma + \delta^\gamma)$$

At each step in the iteration, write $A^i \mathbf{{F}}^i_e = \mathbf{{F}}^{i+1}_e + \mathbf{\epsilon}_i$, where $\epsilon_i \in \mathbb{R}^n$ is the error introduced at step $i$. Then, since the initial condition $\mathbf{{F}}^0$ is known exactly, we have $$\begin{aligned}
\mathbf{{F}}^0 &=& \mathbf{{F}}^0_e  \nonumber \\
\mathbf{{F}}^1 &=& A^0 \mathbf{{F}}^0 = \mathbf{{F}}^1_e + \epsilon_0  \nonumber\\
\mathbf{{F}}^2 &=& A^1 \mathbf{{F}}^1 = \mathbf{{F}}^2_e + \epsilon_1+ A^1 \epsilon_0 \nonumber\\
&\vdots& \nonumber\\
\mathbf{{F}}^N &=& \mathbf{{F}}^N_e + \epsilon_{N-1} + A^{N-1} \epsilon_{N-2} + \dots + A^{N-1}A^{N-2}\dots A^{1} \epsilon_0 \label{e:errorseries}\end{aligned}$$ After subtracting $\mathbf{{F}}^e$ from both sides and taking norms, (\[e:errorseries\]) implies $$\begin{aligned}
\| \mathbf{{F}}^N - \mathbf{{F}}_e^N \|_{1} &\leq& \sum_{\ell=0}^{N-1} \left\| \prod_{i=\ell+1}^{N-1} A^{i}  \right\|_{1}  \| \epsilon_\ell \|_1  \nonumber\\
&\leq& \sum_{\ell=0}^{N-1} \left( \prod_{i=\ell+1}^{N-1} \left\|  A^{i}  \right\|_{1}  \right)\| \epsilon_\ell \|_1 \label{e:boundstep1}\end{aligned}$$ where $\| \epsilon_\ell \|_1$ and $\left\|  A^{i}  \right\|_{1}$ are defined respectively in (\[e:epsnorm\]) and (\[e:Anorm\]). From the definition of $A^i$ in (\[e:defofAmatrix\]) and the stability condition $n^{\star}_T h < 1$, the norm $\|A^i\|_{1}$ is given by the maximum absolute sum of the columns of $A^{i}$, which in our case is $$\|A^i\|_{1} = |1 - n(t_i) h| + |h n(t_i) \lambda_i | + |h n(t_i) (1- \lambda_i) | = 1.$$ Thus, (\[e:boundstep1\]) becomes $$\label{e:boundstep2}
\| \mathbf{{F}}^i - \mathbf{{F}}_e^i \|_{1}  \leq \sum_{\ell=0}^{N-1} \| \epsilon_\ell \|_1.$$

What remains is to bound $$\| \epsilon_\ell \|_1 = \| \mathbf{{F}}^{\ell+1}_e- A^{\ell} \mathbf{{F}}_e^\ell  \|_1 = \sum_{j=0}^M \delta |(\epsilon_\ell)_j|$$ Using the differential equation (\[e:mainde\]) and the definitions of the errors $S_{j,\ell}$ and $R_{j,\ell}$ in (\[e:defofS\]) and (\[e:defofR\]), we have $$\begin{aligned}
(\epsilon_\ell)_j &=& {F}(x_j,t_{\ell + 1}) - (A^\ell \mathbf{{F}}_e^\ell )_j \nonumber \\
&=&  {F}(x_j,t_{\ell + 1}) - \{ {F}( x_j , t_\ell ) ( 1 - h
n(t_\ell) ) +  h n(t_\ell) [ (1- \lambda_\ell) {F}(x_{j - k_\ell},t_\ell) + \lambda_\ell {F}(x_{j - k_\ell+1},t_\ell) ] \} \nonumber \\
& = &  {F}(x_j,t_\ell + h) - {F}(x_j,t_\ell)  - h [ n( t_\ell ) (
(1- \lambda_\ell) {F}(x_{j - k_\ell},t_\ell) + \lambda_\ell {F}(x_{j
  - k_\ell+1},t_\ell)  - {F}(x_j,t_\ell)) ] \nonumber \\
&=&  {F}(x_j,t_\ell + h) - {F}(x_j,t_\ell)  - h [ n( t_\ell ) (
 {F}(x_j- {g}(t_\ell),t_\ell) 
 - {F}(x_j,t_\ell) +R_{j,\ell}(\delta)  ) ] \nonumber \\
&=&   {F}(x_j,t_\ell + h) - {F}(x_j,t_\ell)  - h [ \frac{ \partial {F}}{\partial t^+}(x_j,t_\ell) + n(t_\ell) R_{j,\ell}(\delta) ]  \nonumber \\
&=& S_{j,\ell}(h) -  n(t_\ell) R_{j,\ell}(\delta) h .     \label{e:epsilonbound1}\end{aligned}$$

Now, for $\ell$ fixed, consider the following partition of the mesh $\Delta_\delta$ in (\[e:defofDelta\]): $$\begin{aligned}
I_1^{(\ell)} &=& \{ j  \ : \  x_j - {g}(t_\ell) \geq 0 > x_j - {g}(t_{\ell + 1})  \} \\
I_2^{(\ell)} &=& \{ j \ : \ x_j - {g}(t_\ell) < 0 \} \\
I_3^{(\ell)} &=& \{ j \ : \ x_j - {g}(t_{\ell+1}) \geq 0 \}\end{aligned}$$ Notice that $I_1^{(\ell)}$ contains at most one element. Using (\[e:epsilonbound1\]) combined with Lemmas \[l:Slem\] and \[l:Rlem\] and that $M \delta = L$, we have $$\begin{aligned}
\| \epsilon_\ell \|_1 = \sum_{j=0}^M\delta |(\epsilon_\ell)_j|  &\leq&  n(t_\ell) h \sum_{j=0}^M \delta |R_{j,\ell}(\delta) | + \sum_{j \in I_1^{(\ell)}} \delta |S_{j,\ell}(h)| + \sum_{j \in I_2^{(\ell)}} \delta |S_{j,\ell}(h)| +  \sum_{j \in I_3^{(\ell)}} \delta |S_{j,\ell}(h)| \nonumber \\
&\leq&   O( h \delta^{\gamma}) + | I_1^{(\ell)} | \cdot  O( \delta h ) + | I_2^{(\ell)} | \cdot O(\delta h^2) + | I_3^{(\ell)} | \cdot O(\delta h^{1+\gamma}) \nonumber  \\
&=& O(h \delta^\gamma) + O(\delta h) + O(h^2) + O(h^{1+\gamma}) \nonumber \\
&=& O(h \delta^\gamma ) + O(h^{1+\gamma}) . \label{e:bigOs}\end{aligned}$$ Finally, since $N h = T$, (\[e:boundstep2\]) and (\[e:bigOs\]) imply $$\begin{aligned}
\| \mathbf{{F}}^i - \mathbf{{F}}_e^i \|_{1}  &\leq& \sum_{\ell=0}^{N-1} \| \epsilon_\ell \|_1. \nonumber \\
&\leq & O(h^\gamma + \delta^\gamma),  \end{aligned}$$ which finishes the proof.

Extension to more general kernels {#s:extend}
---------------------------------

In order to guarantee the error bound (\[e:errorbound\]), we must assume that ${g}$ is a strictly increasing, continuous function whose inverse is Hölder continuous. This assumption is somewhat restrictive, as we would like to apply our method to a wider set of kernels. In this section, we indicate how to transform a problem with a general kernel into problem which satisfies the assumptions of Theorem \[t:errorbound\].

Recall that if $X,Y$ are independent non-negative random variables with respective CDFs ${F}_X, {F}_Y$, then the CDF of the sum $X+Y$ is given by the convolution $$\label{e:convolve}
{F}_{X+Y}( u ) = \int_0^\infty {F}_Y( u - x ) {F}_X(dx).$$ If ${F}_X$ and ${F}_Y$ are both defined on a mesh $ \Delta_{\delta} = \{x_j\}_{j=1}^M$, then the convolution (\[e:convolve\]) can be approximated by the discrete convolution $$\label{e:discreteconvolve}
{F}_{X+Y}(u) \approx \sum_{j= 0 }^M  {F}_Y( u - x_j ) [ {F}_X( x_{j+1} ) - {F}_X(x_j) ].$$

### Decreasing kernels {#decreasing-kernels .unnumbered}

If ${g}$ is a strictly <span>*decreasing*</span> kernel with Hölder continuous inverse, then a simple variable transform re-expresses the integral into one with a strictly increasing kernel: $$I({g}) = \int_0^T{g}(s)N(ds) \overset{d}{=} \int_0^T \widetilde{f}(s) \widetilde{N}(ds)$$ where $\widetilde{f}(s) = {g}(T-s)$ and $\widetilde{N}(ds)$ is a Poisson random measure with control $\widetilde{n}(s) = n(T-s)$.

### Flat kernels {#flat-kernels .unnumbered}

If ${g}\equiv \lambda$ is a constant function, then there is no need to approximate the CDF since its distribution is known exactly: $$I({g}) = \int_0^T {g}N(ds) \sim  \lambda  \mathrm{Pois}( \int_0^T n(s) ds  ).$$

### Negative kernels {#negative-kernels .unnumbered}

If ${g}$ is a negative strictly monotone increasing/decreasing kernel with Hölder continuous inverse, then the negative of the integral fits the proper assumptions: $$\label{e:convolveP}
I({g}) = \int_0^T {g}(s) N(ds) \overset{d}{=} - \left( \int_0^T (-{g}(s)) N(ds) \right).$$ Thus, ones computes the CDF of $-I({g})$ with the forward difference method, and then uses the relationship ${F}_{I({g})}(u) =1 -  {F}_{-I({g})}(-u)$.

### "Piecewise" kernels {#piecewise-kernels .unnumbered}

Combining the above three ideas, the convolution formula (\[e:discreteconvolve\]) and the independent increment property of the random measure $N$, we can approximate integrals with <span>*piecewise*</span> increasing/flat/decreasing, positive/negative kernels, whose inverse on each non-flat piece is Hölder continuous. Indeed, if ${g}$ is increasing/flat/decreasing and positive/negative between each of the points $0 = t_0 < t_1 < \dots < t_{n-1} < t_n = T$, then we have $$I({g})  = \int_0^T {g}(s) N(s) \overset{d}{=} \sum_{i=0}^{n-1} \int_{t_i}^{t_{i+1}} {g}(s) N(ds)$$ This sum on the right-hand side can be computed inductively by using the integral up to $t_{i-1}$ as an initial condition, and iterating until the CDF is computed up to $t_i$. That is, set $I_0 = 0$, and use our method to compute $$I_i = I_{i-1} + \int_{t_{i-1}}^{t_i} {g}(s) N(ds), \quad i=1,2,\dots,n.$$ Corollary \[c:sumIs\] and Theorem \[t:errorbound\] imply that the rate of convergence in this method in the $L^1$ norm will depend on, at worse, the minimum of the Hölder exponents of ${g}^{-1}$ over each of the intervals $[t_i,t_{i+1})$.

Examples {#s:examples}
========

We shall demonstrate our method on some examples. We start with $$\label{e:simpex}
\int_0^1 s N(ds),$$ where $N$ is a Poisson random measure with control Lebesgue: i.e.  $n(s) = 1$. This example is simple enough to compute exactly, so it serves as an useful test case. The second example is where the kernel ${g}$ is a parabola $$\int_0^2 (1 - (1 - s)^2) N(ds),$$ and the control measure is again Lebesgue. In this example, the kernel ${g}$ has an inverse which lies in the Hölder space $C^{0,1/2}(0,1)$, and thus we expect the CDF to share this property. For purposes of comparison, we also compute this CDF by approximating the integral (\[e:abatesmet\]).

Finally, we consider an integrand which is both positive and negative: $$\int_0^1 \sin(2 \pi s) N(ds)$$ with control measure Lebesgue. This will demonstrate some of the ideas in Section \[s:extend\].

Recall that in each example, we will see a jump at $x=0$ of size $\exp(-\int_0^T n(s) ds)$ in the CDF which is the probability of no Poisson arrivals.

### Example 1: $\displaystyle   \int_0^1 s N(ds), \quad n(s) = 1 $ {#example-1-displaystyle-int_01-s-nds-quad-ns-1 .unnumbered}

In this example, the kernel is the identity function ${g}(s) = s$, hence the integral is given by the sum of arrival times in $(0,1)$. The number of arrivals follows a Poisson distribution with rate $\int_0^1 n(s) ds = 1$ and in the event of $k \geq 0$ arrivals, the times of these arrivals are given by $k$ i.i.d. random variables $U_1,U_2,\dots,U_k$ which are uniform on $(0,1)$. Thus, the CDF ${F}$ of $\int_0^1 s N(ds)$ can be expressed by conditioning on the number of Poisson arrivals in the interval $(0,1)$: $$\label{e:exactform1}
{F}(x) = \sum_{k=0}^\infty \mathrm{Prob} \left. \left[ \sum_{i=1}^k U_i \leq
  x \right| \mbox{$k$ arrivals} \right] \mathrm{Prob}[ \mbox{$k$ arrivals}]=   \sum_{k=0}^\infty \frac{P_k(x) e^{-1}}{ k! },$$ where $P_k(x)$ is the CDF of a sum of $k$ i.i.d. $U(0,1)$ random variables. Each $P_k$ can written as a piecewise polynomial, and can be computed recursively as $$\begin{aligned}
P_0(x) &=& \begin{cases} 0 \quad x < 0 \\
1 \quad x \geq 0 \end{cases}  \\
P_k(x) &=& \int_0^1 P_{k-1}(x-u) du \quad k \geq 1.\end{aligned}$$ The first few $P_k$ are $$P_1(x) = \begin{cases} 0, \quad x < 0 \\
x, \quad 0 \leq x < 1 \\
1, \quad x \geq 1 \end{cases}, 
\quad P_2(x) = \begin{cases} 0, \quad x < 0 \\
\frac{x^2}{2}, \quad 0 \leq x < 1 \\
\frac{(-2 + 4 x - x^2)}{2}, \quad 1 \leq x < 2 \\
1, \quad x \geq 2
\end{cases}, \quad
P_3(x) = \begin{cases}
0, \quad x < 0 \\
\frac{x^3}{6}, \quad 0 \leq x < 1 \\
 \frac{ 3 - 9 x + 9 x^2 - 2 x^3}{6}, \quad  1 \leq x < 2 \\
 \frac{-21 + 27 x - 9 x^2 + x^3}{6}, \quad  2 \leq x < 3 \\
1, \quad x \geq 3 \end{cases}.$$ Notice that it suffices to take the first $11$ terms in the sum (\[e:exactform1\]), since $\sum_{i=11}^\infty e^{-1}/n! < 10^{-7}$, which is much more than the precision we seek.

We generated ${F}(x)$ on the interval $ x \in [0,3)$ with our method with $\delta = h =10^{-4}$. This is plotted in Figure \[f:intsNds\] along with a numerical approximation of the density[^5]. Notice the "kink" at $x=1$ in the CDF and the corresponding discontinuity in the density. This is consistent with Theorem \[t:holder\], since here the inverse of the kernel is simply ${g}^{-1}(s) = s$, which lies in the space $C^{0,1}(0,1)$, so here we take $\gamma = 1$. Thus, we expect that the ${F}$ is at worst Lipschitz continuous. This is indeed the case, since ${F}$ is a linear combination of the $P_n$'s, and $P_1$ is clearly in $C^{0,1}(0,\infty)$ and no smaller Hölder space.

Using the first $11$ terms in the sum (\[e:exactform1\]), we also computed this CDF on the interval $[0,3)$ and looked at the relative error between this and the result of our method. The relative error is plotted in Figure \[f:intsNdserr\]. We have excellent agreement over all $x$ with our method.

![CDF and density for the stochastic integral (\[e:simpex\]). The vertical line with a dot in the plot of the density represents a discrete atom in the distribution whose mass is the height of the vertical line. To compute this, we used the forward difference method with $h = \delta =  5 \times 10^{-4}$. On a 1.5 Ghz computer, this computation took less than 5 seconds using MATLAB. Notice the "kink" in the CDF and discontinuity in the density at $x=1$. This is not surprising, since here $\gamma = 1$ so expect the CDF to be at worst Lipschitz continuous. <span data-label="f:intsNds"></span>](intsNds.eps)

![ The relative error between the CDF of (\[e:simpex\]) computed using our method, and the true value of the CDF computed with (\[e:exactform1\]). We see that our method gives accuracy of $\ll .1 \%$ over all $x$ considered. <span data-label="f:intsNdserr"></span>](intsNdserr.eps)

### Example 2: $\displaystyle  \int_0^2 [1 - (1-s)^2] N(ds)$, $\quad n(s) = 1$ {#example-2-displaystyle-int_02-1---1-s2-nds-quad-ns-1 .unnumbered}

Here we consider the more complicated example where ${g}(s) = 1 -
(1-s)^2$ for $0 \leq s \leq 2$, which is a downward facing parabola with maximum value $1$ and roots at $0$ and $2$. This function is piecewise monotone on the intervals $(0,1)$, and $(1,2)$, so the finite difference scheme can be applied first to compute $F(x,t)$ for $0 \leq t \leq 1$, and then subsequently for $1 \leq t \leq 2$ by using $F(x,1)$ as an initial condition. The density can be obtained with numerical differentiation. This is shown in Figure \[f:intparNds\].

Notice the sharp corner in the CDF at $x = 1$ and the corresponding singularity in the density. This illustrates the results of Theorem \[t:holder\] and Corollary \[c:worstcase\], that is, the CDF lies in the smallest Hölder space $C^{0,\gamma}(0,\infty)$ which contains the inverse of $g$ restricted to $(0,1)$ and the inverse of $g$ restricted to $(1,2)$. In this case we have $$\begin{aligned}
g^{-1}(x) &=& 1 - \sqrt{1-x},  \quad   \mbox{for $g$ restricted to $(0,1)$}  \\
g^{-1}(x) &=& 1 + \sqrt{1-x},  \quad  \mbox{for $g$ restricted to $(1,2)$} \end{aligned}$$ In both of these cases, $g^{-1} \in C^{0,1/2}(0,1)$, and thus we expect the CDF $F(x,t) \in C^{0,1/2}(0,\infty)$ as well.

For comparison purposes, we also computed this CDF using the integration method of Abate and Whitt discussed briefly in the introduction. Since this integral is only applicable for continuous ${F}$, we first rewrite the characteristic function $\phi_g$ by "removing" the case where there are 0 arrivals, and considering this case separately, $$\begin{aligned}
\phi_g(\theta) &=& \mathbb{E} \exp\left( i \theta \int_0^2 {g}(s) N(ds)   \right) \\
&=& \mbox{Prob}[N=0] e^{0} + \left. \mathbb{E} \left[ \exp\left(  i \theta
    \int_0^2 {g}(s) N(ds)   \right) \right|  N \geq 1 \right] \\
&=& e^{-2}  + \left[ \exp\left( \int_0^2 (e^{i \theta {g}(s)}
  - 1) ds\right) - e^{-2} \right] \\
&\equiv& e^{-2} + \bar{\phi}_g(\theta).\end{aligned}$$ Then, using (\[e:abatesmet\]) the CDF ${F}$ is given by $$\label{e:phibar}
{F}(x) = e^{-2} + \int_0^\infty \mbox{Re}( \bar{\phi}_g )(u) \frac{
  \sin( x u) }{u} du.$$ To approximate the integral in (\[e:phibar\]), we truncate the infinite limit at $T_I >0$, choose a mesh size $\eta> 0$ and use a trapezoid approximation: $$\label{e:trap}
{F}(x) \approx e^{-2} + \frac{\eta}{2} \left( \mbox{Re}(\bar{\phi}_g )(0) +
\mbox{Re}(\bar{\phi}_g)(T_I) \frac{\sin(T_I x)}{T_I} \right)  + \eta
\sum_{j=1}^{K-1}   \mbox{Re}(\bar{\phi}_g)(j \eta) \frac{\sin(j \eta
  x)}{ j \eta } ,$$ Where $K = T_I/\eta$ is the size of the mesh. Notice that computing $
\mbox{Re}(\bar{\phi}_g)(j \eta)$ for every $j$ involves also computing the integral $\int_0^2 (e^{i \theta {g}(s)} - 1) ds $. To do so, we used the MATLAB function `quad`. The integrand is a highly oscillating function for large $\theta$, causing numerical approximation methods to converge slowly. This makes computing the sum in (\[e:trap\]) <span>*extremely*</span> time-consuming for large $K$.

In Figure \[f:FDintcompare\], we plotted the CDF around the kink at $x=1$ using these two methods. We used the finite-difference method with $\delta = h =
 5 \times 10^{-3}$ and $\delta = h =1 \times 10^{-3}$, and used the integration method with $T_I = 50$, $\eta = .1$ and $T_I = 100$ and $\eta = .01$. Notice that there is a small difference between the curves generated by the finite-difference method, which implies adequate convergence has been met. On the other hand, the results of the integration have "smoothed" out the kink, implying a larger $T_I$ is required. Moreover, the computation time for these methods varied drastically, to generate the curves in Figure \[f:FDintcompare\], the finite-difference method required less than 2 seconds, while integration requires about 8 minutes.

![ CDF and density the Poisson integral of $g$. In this case, the CDF is Hölder continuous for $x > 0$ with Hölder exponent $\gamma = 1/2$. As a result, we see a sharp "corner" in the CDF and a singularity in the density at $x = 1$. To generate the CDF, we used $\delta = h = 10^{-4}$. <span data-label="f:intparNds"></span>](intparNds.eps){width="100.00000%"}

![ A comparison between the CDF of Example 2 computed using the integration method (\[e:trap\]) and the finite-difference scheme of Section \[s:methods\], zoomed in on the kink in the CDF at $x=1$. The integration method takes over 200 times longer to implement, and it seems that even larger $T_I$ and smaller $\eta$ is required to obtain sufficient convergence. Also, important features of ${F}$ are missed with integration, such as the kink at $x=1$ which is "smoothed" here. The finite-difference method, on the other hand, converges quickly in $\delta$ and $h$, is much faster, and captures the kink in ${F}$<span data-label="f:FDintcompare"></span>](FDintcompare.eps){width="100.00000%"}

### Example 3: $\displaystyle  \int_0^1 \sin(2 \pi s) N(ds)$, $\quad n(s) = 1 $ {#example-3-displaystyle-int_01-sin2-pi-s-nds-quad-ns-1 .unnumbered}

![ CDF and density the Poisson integral of the sine wave ${g}(s) = \sin(2 \pi s)$ over the interval $0 \leq s \leq 1$. <span data-label="f:intsinsNds"></span>](intsinsNds.eps){width="100.00000%"}

We now consider the Poisson integral of one period of a sine wave which is a case where the kernel is both positive and negative. To compute the CDF $F$, we split up the integral as $$\label{e:breakitupP}
\int_0^1 \sin(2 \pi s) N(ds) = \int_0^{\frac{1}{2}}   \sin(2 \pi s) N(ds) + \int_{\frac{1}{2}}^1   \sin(2 \pi s) N(ds) =: I_1 + I_2$$ and note that the summands on the right are independent and satisfy $I_1 \overset{d}{=} -I_2$. Thus, if $F_1(x)$ is the CDF of $I_1$, then $F_2(x) = 1 - F_1(-x)$ gives the CDF of $I_2$. Taking the convolution of $F_1$ and $F_2$ we use the symmetry of $I_1$ and $I_2$ and see $$\begin{aligned}
F(u) &=& \int_{-\infty}^\infty F_1(u - x) dF_2(x) \nonumber \\
&=& e^{-1/2} F_1(u) + \int_{0}^\infty F_1(u + x) dF_1(x) \nonumber \\
& \approx& e^{-1/2} F_1(u) + \sum_{j=0}^M F_1(u + x_j)(F_1(x_j) - F_1(x_{j-1})). \label{e:convPP}\end{aligned}$$ The first term appears here since $F_2$ has a discontinuity at $x=0$ with size $$F_2(0^+) - F_2(0^-) = e^{-\int_0^{1/2} n(ds)} = e^{-1/2}.$$ This gives an approximation to the CDF of the sum in (\[e:breakitupP\]).

The CDF and density of $\int_0^1 \sin(2 \pi s) N(ds)$ is plotted in Figure \[f:intsinsNds\]. Similar to Example 2, we see at $x=\pm 1$ two sharp corners in the CDF. To understand this, notice that on the interval $(0,1/2)$ the inverses of the function ${g}(s) = \sin(2 \pi s)$ are given by $$\begin{aligned}
{g}^{-1}(x) &=& \frac{\sin^{-1}(x)}{2 \pi}, \quad \mbox{ for ${g}$ restricted to $(0,1/4)$}, \\
{g}^{-1}(x) &=& \frac{\sin^{-1}(1/2 - x)}{2 \pi}, \quad \mbox{ for ${g}$ restricted to $(1/4,1/2)$}.\end{aligned}$$ In both of these cases, ${g}^{-1} \in C^{0,1/2}(0,1)$ since the derivative at $x=1$ doesn't exist and $$\sin^{-1}(1) - \sin^{-1}(x) \sim \sqrt{1 - x}, \ \ \mbox{as} \ x
\rightarrow 1^{-}.$$ Thus, Theorem \[t:holder\] and Corollary \[c:worstcase\] imply that $F_1
\in C^{0,1/2}(0,\infty)$, and similar to Example 2, this is evident by a kink in in $F_1$ at $x=1$. Since $F_2(x) = 1 - F_1(-x)$, $F_2 \in
C^{0,1/2}(-\infty,0)$, and we expect a kink at $x = -1$. Because $F_1$ and $F_2$ both have a discontinuity at $x=0$, the convolution in (\[e:convPP\]) can be written in two ways:

$$\begin{aligned}
F(x) &=& \int_{-\infty}^\infty {F}_1(x - u) d{F}_2(u)  =  e^{-1/2} F_1(x) + \int_{-\infty}^0 F_1(x - u) dF_2(u)  \label{e:split1}\\
&=& \int_{-\infty}^\infty {F}_2(x - u) d{F}_1(u)  =  e^{-1/2} F_2(x) + \int_{0}^\infty F_2(x - u) dF_1(u). \label{e:split2}
    \end{aligned}$$

Since ${F}_1$ has a kink at $x = 1$ and $F_2$ has a kink at $x = -1$, (\[e:split1\]) and (\[e:split2\]) explain why you see kinks at $x =\pm1 $ in the convolution.

Approximation Lemmas {#s:approx}
====================

This section contains the bounds on the approximation errors $S_{j,\ell}(h)$ and $R_{j,\ell}(\delta)$ defined in Section \[s:error\]. Recall that $S_{j,\ell}(h)$ involves an approximation of the time derivative $\frac{\partial {F}}{\partial t^+}$ and $R_{j,\ell}(\delta)$ involves an approximation of ${F}(x - g(t),t)$. The first lemma below bounds $S_{j,\ell}(h)$ in terms of $h,h^{1+\gamma}$ and $h^2$. The second lemma bounds $R_{j,\ell}(\delta)$ in terms of $\delta^{1+\gamma}$. Here $\gamma$ is the Hölder exponent of ${g}^{-1}$.

\[l:Slem\] Let $S_{j,\ell}(h)$ be as in (\[e:defofS\]), and assume $g$ and $n$ satisfy the assumptions in (\[e:gnassump\]). Then $$\label{e:Slem}
|S_{j,\ell}(h) | \leq \begin{cases} \displaystyle n_T^{\star} (2 h + n^{\star}_T h^2
  ) \qquad x_j - {g}(t_{\ell}) \geq 0 > x_j - {g}(t_{\ell + 1}) \\ 
 \displaystyle  (\frac{L_n}{2}+2) n^{\star \ 2}_T h^2 + \frac{ n^{\star}_T C_{n,T} L_{g}^\gamma [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} }{1 + \gamma} h^{1 + \gamma}, \quad  x_j - {g}(t_{\ell + 1}) \geq 0 \\
(\frac{n_T^{\star} L_n}{2} + 2 n^{\star}_T ) h^2 \qquad x_j - {g}(t_\ell) < 0 \end{cases}$$ where $C_{n,T}$ is defined in Theorem \[t:holder\].

Let $ h >0$. As in the proof of Theorem \[t:mainthm\], we have $$\begin{aligned}
{F}(x_j,t_{\ell}+h) - {F}(x_j,t_{\ell}) &=& \mathbb{E} [
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_{\ell}+h)) - {\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_{\ell}))
]  \nonumber \\
&=&\sum_{n=0}^\infty \mathbb{E} [{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_\ell+h)) -
{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_\ell)) | N = n] P_n \nonumber \\
&=& \left(  \int_{t_\ell}^{t_\ell+h} ( {F}(x_j - {g}(s),t_\ell) - {F}(x_j,t_\ell)) n(s) ds  \right) e^{-\int_{t_\ell}^{t_\ell+h} n(s)ds} \nonumber   \\
&\ &  + \sum_{n=2}^\infty \mathbb{E} [{\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_\ell+h)) - {\mbox{\boldmath$1$}}_{(-\infty,x]}(X(t_\ell)) | N = n] P_n  \label{e:ALemstep1}\end{aligned}$$ Now, using (\[e:mainde\]), (\[e:ALemstep1\]), and the fact that $ 0  \leq {F}(x_j,t_\ell) \leq 1$, we have $$\begin{aligned}
|S_{j,\ell}(h) | &=&  | {F}(x_j,t_\ell+h) - {F}(x_j,t_\ell) - h
\frac{\partial {F}}{\partial t^+} | \nonumber \\
&=& | {F}(x_j,t_\ell+h) - {F}(x_j,t_\ell) - h({F}(x_j - {g}(t_\ell),t_\ell) - {F}(x_j,t_\ell))n(t_\ell) | \nonumber \\ 
&\leq& \left| \left(  \int_{t_\ell}^{t_\ell+h} ( {F}(x_j - {g}(s),t_\ell) - {F}(x_j,t_\ell)) n(s) ds  \right)  - h  ( {F}(x_j - {g}(t_\ell),t_\ell) - {F}(x_j,t_\ell)) n(t_\ell)  \right| \nonumber \\
&\ & + \left| \left(  \int_{t_\ell}^{t_\ell+h} ( {F}(x_j - {g}(s),t_\ell) - {F}(x_j,t_\ell)) n(s) ds  \right) (e^{-\int_{t_\ell}^{t_\ell+h} n(s)ds} - 1) \right|  + \sum_{n=2}^\infty P_n  \label{e:ALemstep2} \end{aligned}$$ To obtain (\[e:Slem\]), we consider the three cases separately. We will use the following elementary inequalities involving $e^{-x}$ for $x \in \mathbb{R}$:

$$\begin{aligned}
1 - e^{-x}  &\leq&  x \label{e:ebound1}\\ 
1 - e^{-x} - x e^{-x} & \leq&   x^2. \label{e:ebound2}\end{aligned}$$

**Case 1.** $x_j - {g}(t_{\ell}) \geq 0 > x_j - {g}(t_{\ell + 1}) $

This case contains the "troublesome" point, since $ 0 \notin
C({F})$ and Theorem \[t:mainthm\] does not necessarily apply. However, in view of (\[e:leftversion\]) in Remark 2 after the proof of Theorem \[t:mainthm\], we have in any case $$\left|h \frac{\partial {F}}{\partial t_\ell^{+}} \right| \leq h n^{\star}_T.$$ And, from (\[e:ALemstep1\]), $$\begin{aligned}
|{F}(x_j,t_\ell+h) - {F}(x_j,t_\ell)| &\leq& n^{\star}_T h +
\sum_{n=2}^\infty P_n.\end{aligned}$$ Using (\[e:ebound2\]), we have $$\begin{aligned}
\sum_{n=2}^\infty P_n &=& 1 - P_0 - P_1  = 1 -  e^{-\int_t^{t+h} n(s)
  ds} - \left( \int_t^{t+h} n(s) ds \right)e^{-\int_t^{t+h} n(s) ds}
\nonumber 
\\
 &\leq& \left( \int_t^{t+h} n(s) ds \right)^2 \leq  (h n^{\star}_T)^2. \label{e:lemp3}\end{aligned}$$ Thus, for this case, $$|S_{j,\ell}(h) | \leq |{F}(x_j,t_\ell+h) - {F}(x_j,t_\ell)| +  \left|h \frac{\partial {F}}{\partial t^{+}} \right| \leq 2 n^{\star}_T h + n^{\star \ 2}_T h^2,$$ which is consistent with (\[e:Slem\]).

**Case 2**: $x_j - {g}(t_{\ell + 1}) \geq 0$.

Since ${g}$ is monotone increasing, $x_j - {g}(t_\ell) > x_j -
{g}(t_{\ell + 1}) \geq 0$. From Theorem \[t:holder\] and the Lipschitz assumptions on $n$ and ${g}$ imply the first term in absolute values in (\[e:ALemstep2\]) can be rewritten and bounded as $$\left| \int_{t_\ell}^{t_\ell+h} ({F}(x_j - {g}(s),t_\ell) - {F}(x_j - {g}(t_\ell),t_\ell))n(s) ds  -  \int_{t_\ell}^{t_\ell+h} (n(t_\ell) - n(s))({F}(x_j - {g}(t_\ell),t_\ell) - {F}(x_j,t_\ell)) ds  \right|$$ $$\begin{aligned}
&\leq& n^{\star}_T \int_{t_\ell}^{t_\ell+h} |{F}(x_j -
{g}(s),t_\ell) - {F}(x_j - {g}(t_\ell),t_\ell))| ds +
\int_{t_\ell}^{t_\ell+h} |n(s) - n(t_\ell) | ds. \nonumber \\
&\leq&  n^{\star}_T  C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))}   \int_{t_\ell}^{t_\ell+h} |{g}(s) -
{g}(t)|^\gamma ds +
\int_{t_\ell}^{t_\ell+h} |n(s) - n(t_\ell) | ds. \nonumber \\
&\leq& n^{\star}_T C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} L_{{g}}^\gamma \int_{t_\ell}^{t_\ell+h} |s - t_\ell|^\gamma ds + L_n \int_{t_\ell}^{t_\ell+h} |s-t_\ell| ds \nonumber \\
&=& n^{\star}_T C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} L_{{g}}^\gamma \frac{h^{1+\gamma}}{1 + \gamma} + L_n \frac{h^2}{2} \label{e:lemp1}\end{aligned}$$ From (\[e:ebound1\]) and since $0 \leq |{F}| \leq 1$, the second term in (\[e:ALemstep2\]) is bounded by $$\begin{aligned}
\left| \left(  \int_{t_\ell}^{t_\ell+h} ( {F}(x_j - {g}(s),t_\ell) - {F}(x_j,t_\ell)) n(s) ds  \right) (e^{-\int_{t_\ell}^{t_\ell+h} n(s)ds} - 1) \right| &\leq& h n^{\star}_T  \int_{t_\ell}^{t_\ell+h} n(s) ds \nonumber  \\
& \leq & (h n^{\star}_T)^2, \label{e:lemp2}\end{aligned}$$ Finally, the third term in (\[e:ALemstep2\]) is bounded by (\[e:lemp3\]). Putting (\[e:lemp1\]), (\[e:lemp2\]) and (\[e:lemp3\]) together, gives $$|S_{j,\ell}(h)| \leq (\frac{L_n}{2} + 2) n^{\star \ 2}_T h^2 + \frac{ n^{\star}_T C_{n,T}  [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(t))} L_{{g}}^\gamma }{1 + \gamma} h^{1 + \gamma }$$ which agrees with (\[e:Slem\]) for this case.

**Case 3.** $x_j - {g}(t_\ell) < 0$

In this case, many of the terms in (\[e:ALemstep2\]) drop out since ${F}(x,t) = 0$ for $x < 0$ and ${g}$ is assumed to be non-negative. Breaking up (\[e:ALemstep2\]) in a similar way to case 2, we obtain $$\begin{aligned}
|S_{j,\ell}(h) | &\leq&  \int_{t_\ell}^{t_\ell+h} |n(s) - n(t_\ell)| {F}(x_j,t_\ell) ds + 2 n^{\star \ 2}_T h^2 \\
&\leq & (\frac{n^{\star}_T L_n}{2} + 2 n^{\star}_T )h^2\end{aligned}$$ This confirms (\[e:Slem\]) and finishes the proof.

\[l:Rlem\] Let $R_{j,\ell}(\delta)$ be as in (\[e:defofR\]), and assume ${g}$ satisfies the assumptions in (\[e:gnassump\]). Then $$|R_{j,\ell}(\delta)| \leq C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} \delta^{\gamma},$$ where $C_{n,T}$ is defined in Theorem \[t:holder\].

By the definitions of $\lambda_{\ell}$ and $k_\ell$, and since ${F}$ and ${g}$ are non-decreasing, we have $$\begin{aligned}
{F}(x_{j -k_\ell},t_\ell) \  &\leq \  {F}(x_j - {g}(t_\ell),t_\ell) \  \leq \  {F}(x_{j -k_\ell+1},t_\ell) \\
{F}(x_{j -k_\ell},t_\ell) \  &\leq \   (1- \lambda_\ell) {F}(x_{j - k_\ell},t_\ell) + \lambda_\ell   {F}(x_{j - k_\ell+1},t_\ell) \ \leq \  {F}(x_{j -k_\ell+1},t_\ell)  .\end{aligned}$$ These inequalities and Theorem \[t:holder\] now imply $$\begin{aligned}
|R_{j,\ell}(\delta)| &\leq& |  {F}(x_{j -k_\ell+1},t_\ell)   - {F}(x_{j -k_\ell},t_\ell) | \nonumber \\
&\leq& C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} |x_{j - k_\ell + 1} - x_{j - k_\ell}|^\gamma \nonumber \\
&=& C_{n,T} [{g}^{-1}]_{C^{0,\gamma}({g}(0),{g}(T))} \delta^\gamma.\end{aligned}$$ This finishes the proof.

Guide to Software {#s:software}
=================

Software written in MATLAB for computing the CDF of a Poisson integral of the form (\[e:firstpoisint\]) is freely available from the authors. This section will go over installation and use.

Once the file `Poisson_Integral_GUI.zip` is downloaded and decompressed, move the folder "`Poisson_Integral_GUI`" to your desired directory. Launch MATLAB, and enter `path(path,'your_path/Poisson_Integral_GUI')`, where `your_path` denotes the path to the folder `Poisson_Integral_GUI`. You should now be able to use the code included with the package.

To begin, type `Poisson_Integral_GUI` and press return. This will open a window similar to that shown in figure \[f:GUI\]. From here you may enter the parameters into the "Inputs" panel on the top left. These are: $$\begin{aligned}
&\delta \quad &\mbox{Step size in spatial mesh} \\
&h \quad &\mbox{Step size in temporal mesh} \\
&T \quad &\mbox{Upper limit of integration in (\ref{e:firstpoisint})} \\
&x_{\max} \quad &\mbox{Largest value for which CDF is computed} \\
&g(s) \quad &\mbox{Kernel function} \\
&n(s) \quad &\mbox{Density of the control measure}\end{aligned}$$ The kernel function and control measure should be entered as MATLAB expressions in terms of $s$. For example, the kernel $g(s) =\sin^2(2\pi
s)$ and Lebesgue control measure $n(s) = 1$ are entered as `sin(2 * pi * s)\wedge2` and `1`, respectively. Only non-negative kernels and control measures will be accepted.

![ A snapshot of the GUI. <span data-label="f:GUI"></span>](GUIfig.eps)

Once all the parameters are entered, clicking on `Compute F` will generate the CDF of the integral $\int_0^T g(s) N(ds)$ in the upper right plot, as well as a "quick and dirty" approximation of the continuous part of the density in the lower right plot[^6]. The density is approximated by fitting a smoothing spline to the CDF, then computing the derivative of this spline. The slider under the density plot allows you to adjust the smoothing parameter used in computation of the density.

Once a CDF is computed, you may compute specific values of the CDF using the "Outputs" panel on the left. Simply enter in a desired value in the $x$ slot, and press return. Alternatively, you may select an $x$-value using the slide bar at the bottom of the panel. You can also enter a value in the $F(x)$ slot to compute the inverse of the CDF.

The lower left panel allows you to save the CDF data to your MATLAB workspace. To do this, enter a variable name, and click `save`. This will create a variable on your workspace with your chosen name. This variable is an $M$ by 2 array whose first column contains the $x$ values $(0,\delta,2\delta,\dots,M\delta)'$ and second column contains the corresponding CDF values, i.e. $(F(0),F(\delta),\dots,F(M \delta))'$ (here, $M$ denotes the size of the spatial mesh).

Finally, if the user wants to avoid using the interface, the code `poissonCDF` will work in the command line. This function takes in the six parameters listed above and outputs a vector containing the values of the CDF on the mesh points generated. The functions $g$ and $n$ must be entered as function handles. For example, if $\delta = 0.01, h= 0.01, T=3, x_{\max} = 4, g(s) = s^2$ and $n(s) = 1$, the call to this function would look like

`F = poissonCDF(.01,.01,4,3,@(s) s \wedge 2,@(s) 1 );`

The "`@`" symbol is necessary because the input must be a so-called "function handle". The statement above will return the vector `F` which contains the values of the CDF of the integral $\int_0^3 s^2 N(ds)$ with Lebesgue control measure for the values $x =
.01,.02,\dots,3.99,4$. For more on this function, read the comments in the code.

<span>1</span>

Joseph Abate and Ward Whitt. The <span>F</span>ourier-series method for inverting transforms of probability distributions. , 10(1-2):5–87, 1992.

D. Applebaum. . Cambridge University Press, Cambridge, UK, 2004.

L. C. Evans. . American Mathematical Society, Rhode Island, 1998.

D. Kannan. . North-Holland, New York, 1979. North Holland Series in Probability and Applied Mathematics.

David Kincaid and Ward Cheney. . Brooks/Cole Publishing Co., Pacific Grove, CA, second edition, 1996. Mathematics of scientific computing.

J. F. C. Kingman. , volume 3 of <span>*Oxford Studies in Probability*</span>. The Clarendon Press Oxford University Press, New York, 1993. Oxford Science Publications.

Mark Veillette & Murad Taqqu\
Dept. of Mathematics\
Boston University\
111 Cummington St.\
Boston, MA 02215

[^1]: This research was partially supported by the NSF grants DMS-0706786, and DGE-0221680.

[^2]: <span>*AMS Subject classification*</span>. Primary 60-08, 60H05, 65L12 Secondary 60G55

[^3]: <span>*Keywords and phrases:*</span> Poisson integrals, CDFs, finite-difference scheme, Kolmogorov-Feller equations.

[^4]: When implementing this method, $A^i$ should be treated as a sparse matrix to avoid running out of memory

[^5]: This is obtained using the central difference ${F}'(x) \approx
      (2 \delta_1)^{-1} ( F(x + \delta_1) - F(x-\delta_1))$. We must choose $\delta_1 > \delta$ to account for the error made in computing the CDF with step size $\delta$.

[^6]: This requires the Spline Toolbox.

{'source': 'arXiv_out/1004'}