Following Szpankowski - Average Case Analysis of Algorithms on Sequences the exponential generating function of $g(n)$ which is thought to be analytic in $n$ is defined as $$ G(z)=\sum_{n=0}^{\infty} g(n) \, \frac{z^n}{n!} $$ and can be written as a Laplace Inversion Integral $$ G(z)=\frac{1}{2\pi i} \int_{\delta-i\infty}^{\delta+i\infty} g^{*}(s) \, \exp\left(ze^{s}\right) \, {\rm d}s $$ where $\delta >0$ and $g^{*}(s)$ is the Laplace transform of $g(n)$.

Szpankowski now claims that the line of integration can be replaced by some contour ${\cal L}_\epsilon$ which is defined by $$ y={\rm sgn}(y)\tan\left(\frac{\pi}{2}+\theta\right)(x-\epsilon) \tag{1} $$ where $\theta,\epsilon$ I think (he is using $\theta$ in the context of a linear cone opening around the x-axis with angle $\theta<\pi/2$) are just parameters here and $z=x+iy$.

He also supplies a plotLaplace Contour Deformation of the image of ${\cal L}_{\epsilon}$ for the specific case $\epsilon=0.1$ and says that its parametrization reads $$ e^{-|t|/2+\epsilon} \begin{pmatrix} \cos(t) \\ \sin(t) \end{pmatrix} \qquad t\in (-\infty,\infty) \, . $$ Even though I can not relate this plot or parametrization to (1) in any way, I am also confused about how this contour arises from the original one.

Hoping for input.

  • $\begingroup$ How is the complex integral you wrote an Inverse Laplace Transform? $\endgroup$ – Ron Gordon Oct 17 '18 at 14:31
  • $\begingroup$ Are you talking about the fact the there is a factor $e^{ze^{s}}$ in the integrand and not $e^{zs}$ ? $\endgroup$ – Diger Oct 17 '18 at 16:55
  • $\begingroup$ yes ${}{}{}{}{}{}$ $\endgroup$ – Ron Gordon Oct 17 '18 at 17:23
  • $\begingroup$ Write $g(n)$ as an inverse Laplace transform, interchange integral and summation order and carry out the sum. $\endgroup$ – Diger Oct 17 '18 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.