# numerical inverse Laplace-Stieltjes transform

Started by November 9, 2006
Hello,

I am working on a CDO pricing problem as outlined in a paper [1]. For
the computation of the tranch margins one needs several steps of
numerical integration, but before that also has to compute the
distribution function of a discrete or mixed random variable from it's
characteristic or moment generating  function, that is, from the
Fourier-Stieltjes or Laplace-Stieltjes transform of it's distribution
(cdf). For I am bound to a certain platform and language, which does not
like (acutally cannot handle at all) complex number, I have opted for
working via the Laplace transform.

I have found several numerical inverse Laplace transform algorithms,
most notably the Stehfeld algorithm [2] (an implementation of which can
be seen in [3]) wich works basically fine, but it is, as written above,
an _inverse_Laplace_ transformation. That is, it won't give me the
desired result for discrete random variables, which do not have a
density, but only a cdf.

Applying the above inverse Laplace transform will (naturally, for
discrete RV's) give sinusoidal waves into the function and making it
negative near zero, such rendering it unapplyable for further calculations.

Of course, the solution for me would be an inverse Laplace-Stieltjes
transform, for which I have failed to find any numerical algorithms,
which provides F(x) from LF(u)=\Int_0^oo exp(-ut)dF(t).

I wanted to ask you, wheather any of you can help me there, if you could
give me a tip, literature, or, :-), an algorithm.

Thank you very much in advance!

(I'm posting this not only to news://sci.math.num-analysis, but also to
news://comp.dsp for I know about their competency in the field of
integral transforms; I hope, this is not considered bad practice).

Notes:
------
(Using one-sided transforms)
Laplace transform of f(x):
Lf(u)=\Int_0^oo exp(-ut)f(t)dt
Laplace-Stieltjes transform of F(x):
LF(u)=\Int_0^oo exp(-ut)dF(t)

References:
-----------
[1] JP Laurent, J Gregory, (2003): Basket Default Swaps, CDO's and
[2] H Stehfeld (1970): Algorithm 368 Numerical Inversion of Laplace
Transforms, CACM 13, Issue 1; Errata in 13 Issue 10
[3] A Sepp, I Skachkov: Option Pricing with Jumps, Wilmott Magazine,
November 2003, 50-58; http://www.wilmott.com/pdfs/060103_sepp.pdf

"A Sz Szelp" <a.sz.szelp@gmx.net> wrote in message
news:4553c5aa$0$12384\$3b214f66@tunews.univie.ac.at...
> Hello,
>
> I am working on a CDO pricing problem as outlined in a paper [1]. For the
> computation of the tranch margins one needs several steps of numerical
> integration, but before that also has to compute the distribution function
> of a discrete or mixed random variable from it's characteristic or moment
> generating  function, that is, from the Fourier-Stieltjes or
> Laplace-Stieltjes transform of it's distribution (cdf). For I am bound to
> a certain platform and language, which does not like (acutally cannot
> handle at all) complex number, I have opted for working via the Laplace
> transform.
>
> I have found several numerical inverse Laplace transform algorithms, most
> notably the Stehfeld algorithm [2] (an implementation of which can be seen
> in [3]) wich works basically fine, but it is, as written above, an
> _inverse_Laplace_ transformation. That is, it won't give me the desired
> result for discrete random variables, which do not have a density, but
> only a cdf.
>

I think you are looking for a regularly spaced point function which has a
given spectrum.  You could try the inverse z-transform.  If it comes out
non-causal, ie. exists on the negative side of the axis which a probability
distribution can't, there is a problem, but it can always be decomposed into
the convolution of two causal z-transforms.

john2


Hi, John2,
thank you, you have led me to the right path.

PS (Prae-Script):
I have figured, that the inverse z-transform should be calculable by
DFT, notably maybe by Bluestein's FFT?

I would be very grateful, if someone could point me to a working
algorithm, maybe with some basic explanations.

Main post:

>> I am working on a CDO pricing problem as outlined in a paper [1]. For the
>> computation of the tranch margins one needs several steps of numerical
>> integration, but before that also has to compute the distribution function
>> of a discrete or mixed random variable from it's characteristic or moment
>> generating  function, that is, from the Fourier-Stieltjes or
>> Laplace-Stieltjes transform of it's distribution (cdf). For I am bound to
>> a certain platform and language, which does not like (acutally cannot
>> handle at all) complex number, I have opted for working via the Laplace
>> transform.
>
> I think you are looking for a regularly spaced point function which has a
> given spectrum.  You could try the inverse z-transform.  If it comes out
> non-causal, ie. exists on the negative side of the axis which a probability
> distribution can't, there is a problem, but it can always be decomposed into
> the convolution of two causal z-transforms.
>

Wow, thank you John2, it took me a hours to work it out, but yes, your
tip has proven right! I ought to be able do it with inverse z-transform!
It's funny, but how much nomenclature counts: I'd search for inverse
Laplace-Stieltjes transform (as the primary transformation was L-S), and
wouldn't find _anything_ (also browsing links from the little info I
found would not lead to the z-trafo), as it's "called" inverse
z-transform (using "-s as it's not exactly the inverse, but you need a
little detour). And indeed, it should be doable with the inverse
z-transform.
I'll describe how, for those sake who come across this thread later in
archives at the end of this post.

It took me quite a while to figure it all out, as I am not proficient in
numerical analysis or digital signal processing (it was hard work to
"translate" everything from the electrical engineer's
DSP-language/vocabulary, in which most articles concerning these are
written), I come from the financial mathematical field.

--
How to calculate the distribution of a discrete random variable (cdf)
from the Laplace-Stieltjes transform of it:

Let dF_X(t)=\Sum_0^n a_i*1_{c_i}(x) with 1_{c}(x):=1 for x>=c, 0 else
You've got the Laplace-Stieltjes transform of the cdf F_X(x)=P[X<=x] a
discrete random variable:
/oo
| exp(-st)dF_X(t) =LS[F_X(t)](s).
/0
Let n\in\R s.t. N*k_i=c_i for some k_i\in\N for all c_i
We want to get into the z from the Laplace domain, i.e. want z=e^sN. You
can either apply this to LS[F_X(t)](s) or the first
order approximation of s=(ln z)/T: s\approx 2/T*(z-1)/(z+1)
(If I got it right)
So let X(z)=LS[F_X(t)](ln z/T). Using inverse z-transform you get from
X(z) a series x_k k\in {0...n}. Then for c_i=N*k the corresponding x_k
is the a_i you have been looking for (you might get some x_k=0 for
N*k!=c_i for any i).

I think, that should it be, I might have done some mistakes, as I have
not implemented it actually so far (should do it tomorrow).

(It should work quite the same with calculating it from the
characteristic function of the distribution, but by taking z=exp(isT) or
exp(-isT) ("or" not as in "arbitrarily", but as in "I don't know and
don't care to think about it right now, in the middle of the night")
instead of the abovementioned z=exp(sT), but I won't put my hand into
fire for this)

"A Sz Szelp" <a.sz.szelp@gmx.net> wrote in message
news:45550155.4030105@gmx.net...
> Hi, John2,
> thank you, you have led me to the right path.
>
> PS (Prae-Script):
> I have figured, that the inverse z-transform should be calculable by DFT,
> notably maybe by Bluestein's FFT?
>

Glad it was of some help.  I was (mostly) an electrical engineer for years
so I did all the z-transforms in control theory and signal processing.
However the spectrum is usually defined on the unit circle for these
applications so I wasn't confident it would correspond to your problem.

john2


A Sz Szelp wrote:

> How to calculate the distribution of a discrete random variable
> (cdf) from the Laplace-Stieltjes transform of it:
>
> Let dF_X(t)=\Sum_0^n a_i*1_{c_i}(x) with 1_{c}(x):=1 for x>=c,
> 0 else

I may well misunderstand, but shouldn't the above have Dirac deltas
in place of the step functions 1_c?

> You've got the Laplace-Stieltjes transform of the cdf
> F_X(x)=P[X<=x] a discrete random variable:
> /oo
> | exp(-st)dF_X(t) =LS[F_X(t)](s).
> /0

Martin

--
Quidquid latine scriptum sit, altum viditur.

Hi, Martin!

>> Let dF_X(t)=\Sum_0^n a_i*1_{c_i}(x) with 1_{c}(x):=1 for x>=c,
>> 0 else
>
> I may well misunderstand, but shouldn't the above have Dirac deltas
> in place of the step functions 1_c?

You do not misunderstand :-) Wow, somewone actually read that appendum!
I made a mistake, a "d" to much correctly the line should read:
Let F_X(t)=\Sum_0^n a_i*1_{c_i}(x)... which actually translates to Dirac
deltas for dF_X(t). I wanted to give the cdf, as this is what I am
thinking of. Thank you for pointing out this mistake. One more
clarification:
"So let X(z)=LS[F_X(t)](ln z/T)": the last argument should read ln(z)/T,
which is what I have meant, but as the priority of the "apply function"
and the "division" operator might not be clear...

I am working on inverting the z Transform now, which again promises to
become a good deal of work (as I said, I am neither familiar with
numerical analysis nor DSP). The z transform itself works on any complex
sequence {a_n}, n={0,...,\infty}, for complex a_i. I have found a z
transform inversion algorithm in [1], which is pretty straightforward,
and could _basically_ work for me. However, it includes intensive
complex number arithmetics, which I'd like to avoid if possible (due to
limitations of the platform I have to implement this in).

As my coefficients are real for sure, I was wondering, wheather there
might be an algorithm which works with real arithmetics only under the
assumption of real a_i's. I highly appreciate any help and hints.

Acutally, the algorithm in [1] was the _only_ I have found during hours
of search (but then again, I might have looked for it in the wrong places).

/Sz

[1] Schiff, Surendonk, Walker 1992: An Algorithm for Computing the
Inverse Z Transform;
http://ieeexplore.ieee.org/iel4/78/4075/00157219.pdf?tp=&arnumber=157219&isnumber=4075


>> I am working on a CDO pricing problem as outlined in a paper [1]. For the
>> computation of the tranch margins one needs several steps of numerical
>> integration, but before that also has to compute the distribution function
>> of a discrete or mixed random variable from it's characteristic or moment
>> generating  function, that is, from the Fourier-Stieltjes or
>> Laplace-Stieltjes transform of it's distribution (cdf). For I am bound to
>> a certain platform and language, which does not like (acutally cannot
>> handle at all) complex number, I have opted for working via the Laplace
>> transform.
>
> I think you are looking for a regularly spaced point function which has a
> given spectrum.  You could try the inverse z-transform.  If it comes out
> non-causal, ie. exists on the negative side of the axis which a probability
> distribution can't, there is a problem, but it can always be decomposed into
> the convolution of two causal z-transforms.

Well, actually, just to share wisdom :-), it has, finally, proven easier
and more viable to go the IDFT way.

Yours,
/Sz