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 Factor Copulas; laurent.jeanpaul.free.fr/basket_cdo_factor_copula_2003.pdf [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

# numerical inverse Laplace-Stieltjes transform

Started by ●November 9, 2006

Reply by ●November 10, 20062006-11-10

"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

Reply by ●November 10, 20062006-11-10

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)

Reply by ●November 11, 20062006-11-11

"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

Reply by ●November 11, 20062006-11-11

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 elseI 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). > /0Martin -- Quidquid latine scriptum sit, altum viditur.

Reply by ●November 11, 20062006-11-11

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

Reply by ●November 13, 20062006-11-13

>> 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