CONVOLUTION AND FOURIER TRANSFORM OF SUM OF n RANDOM VARIABLES

      Today´s post will be more on applied math. We will discuss about sum of Random variables and convolution.

First we will find the expression of the density function of a sum of two Random Variables and then apply it to find the density of the sum of two exponential R.V.´s and then to the sum of n exponential R.V.´s which ends up by being a Gamma R.V. which is important for the Poisson process and Renewal theory.

We then recall the fourier transform and use it to find the density function of the sum of n Gaussian R.V.´s and n Cauchy R.V.´s. Interesting fact is that the sum of n Gaussians has a gaussian distribution and the sum of n Cauchy´s has a cauchy distribution, due to an propertie called stability.

Convolution of two independent random variables


Let Z=X+Y, where X and Y are two independent and identical distributed continuous R.V. Given f_{X,Y}(x,y), what is f_Z(z)?


We know that f_Z(z)=\frac{d}{dz}\operatorname{F}_Z(z), so if we know \operatorname{F}_Z(z) we can find f_Z(z).



\begin{aligned} \operatorname{F}_Z(z)&=\operatorname{P}\left(Z\leq z \right)\\ &=\operatorname{P}\left(X+Y\leq z \right)\\ &=\int \int_{x+y \leq z} f_{X,Y}(x,y)\,dx\,dy\\ &=\int_{-\infty}^\infty \int_{-\infty}^{z-y} f_{X,Y}(x,y)\,dx\,dy\\ &=\int_{-\infty}^\infty \int_{-\infty}^{z-x} f_{X,Y}(x,y)\,dy\,dx\\ \end{aligned}

Then

\begin{aligned} f_Z(z)&=\frac{d}{dz}\operatorname{F}_Z(z)\\ &=\frac{\partial }{\partial z} \int_{-\infty}^\infty \int_{-\infty}^{z-y} f_{X,Y}(x,y)\,dx\,dy\\ &=\int_{-\infty}^\infty \left(\frac{\partial }{\partial z} \int_{-\infty}^{z-y} f_{X,Y}(x,y)\,dx \right)\,dy\\ &=\int_{-\infty}^\infty f_{X,Y}(z-y,y)\,dy\\ &=\int_{-\infty}^\infty f_X(z-y)f_Y(y)\,dy & (\text{by independency})\\ \end{aligned}

or

\begin{aligned} f_Z(z)&=\frac{d}{dz}\operatorname{F}_Z(z)\\ &=\frac{\partial }{\partial z} \int_{-\infty}^\infty \int_{-\infty}^{z-x} f_{X,Y}(x,y)\,dy\,dx\\ &=\int_{-\infty}^\infty \left(\frac{\partial }{\partial z} \int_{-\infty}^{z-x} f_{X,Y}(x,y)\,dy \right)\,dx\\ &=\int_{-\infty}^\infty f_{X,Y}(x,z-x)\,dx\\ &=\int_{-\infty}^\infty f_X(x)f_Y(z-x)\,dx \\ \end{aligned}

We can then conclude that


f_Z(z)=f_{X+Y}(z)=\int_{-\infty}^\infty f_X(z-y)f_Y(y)\,dy=\int_{-\infty}^\infty f_X(x)f_Y(z-x)\,dx(1)

    Another beautiful method to derive the density function of a sum o R.V´s is by conditioning. The assumptions regarding X and Y remain the same.


\begin{aligned} \operatorname{F}_Z(z)&=\operatorname{P}\left(Z\leq z \right)\\ &=\operatorname{P}\left(X+Y\leq z \right)\\ &=\int_{-\infty}^\infty\operatorname{P}\left(X+Y \leq z| Y=y \right)f_Y(y)\,dy\\ &=\int_{-\infty}^\infty\operatorname{P}\left(X+y \leq z| Y=y \right)f_Y(y)\,dy\\ &=\int_{-\infty}^\infty\operatorname{F}\left(z-y \right)f_Y(y)\,dy\\ \end{aligned}

\begin{aligned} f_{X+Y}\left(z)&=\frac{\partial }{\partial z} \int_{-\infty}^\infty\operatorname{F}\left(z-y \right)f_Y(y)\,dy\\ &=\frac{\partial }{\partial z} \int_{-\infty}^\infty \int_{-\infty}^{z-y} f_X(x)f_Y(y)\,dx\,dy\\ &=\int_{-\infty}^\infty f_X(z-y)f_Y(y)\,dy\\ \end{aligned}


Sum of i.i.d. exponential Random Variables


Let´s make a first application of this formula. Let´s consider X and Y to be exponential random variables with idenpendent identical distributions.

Exponential R.V.´s have the following density function:


\\ f_X(x)=\begin{cases} \lambda e^{-\lambda x} & x\geq 0\\ 0 & x<0 \end{cases}

Define S_n=\sum_{k=1}^n X_k.


Then, for the sum of two exponential R.V´s we have


\begin{aligned} f_{S_2}&=f_{X_1+X_2}(t)\\ &=\int_{-\infty}^\infty f_X(t-s)f_Y(s)\,ds &(\text{by eq.(1)})\\ &=\int_{0}^\infty f_X(t-s)f_Y(s)\,ds & (\text{X is positive})\\ &=\int_0^t f_X(t-s)f_Y(s)\,ds & (\text{for } s>t, \text{the values of s become negative})\\ &=\int_0^t \lambda e^{-\lambda(t-s)}\lambda e^{-\lambda s} \,ds\\ &=\lambda^2 e^{-\lambda t}\int_0^t \,ds\\ &=\lambda^2 t e^{-\lambda t} \qquad \blacksquare \end{aligned}

 

For the sum of three R.V´s


\begin{aligned} f_{X_1+X_2+X_3}(t)&=f_{S_2+X_3}(t)\\ &=\int_{-\infty}^\infty f_{S_2}(t-s)f_{X_3}(s)\,ds \\ &=\int_{-\infty}^\infty f_{X_3}(t-s)f_{S_2}(s)\,ds \\ &=\int_0^t \lambda e^{-\lambda(t-s)}\lambda^2 s\, e^{-\lambda s} \,ds\\ &=\lambda^3 e^{-\lambda t}\int_0^t s \,ds\\ &=\frac{\lambda^3 t^2 e^{-\lambda t}}{2!} \qquad \blacksquare \end{aligned}


Where we used the result for f_{S_2}=\lambda^2 t e^{-\lambda t} and that F_1*F_2=F_2*F_1 by quation () above.

For the sum of four R.V´s we have:


\begin{aligned} f_{X_1+X_2+X_3+X_4}(t)&=f_{S_3+X_4}(t)\\ &=\int_{-\infty}^\infty f_{S_3}(t-s)f_{X_4}(s)\,ds \\ &=\int_{-\infty}^\infty f_{X_4}(t-s)f_{S_3}(s)\,ds \\ &=\int_0^t \lambda e^{-\lambda(t-s)} \frac{\lambda^3 s^2\, e^{-\lambda s} }{2!}\,ds\\ &=\frac{\lambda^4 e^{-\lambda t}}{2!}\int_0^t s^2 \,ds\\ &=\frac{\lambda^4 t^3 e^{-\lambda t}}{3!} \qquad \blacksquare \end{aligned}

Can you see a pattern emerging?


Claim:

f_{S_n}(t)=f_{X_1+\cdots+X_n}(t)=\frac{\lambda^n t^{n-1}\,e^{-\lambda t}}{(n-1)!}(2)

Proof:

Assume that


f_{S_{n-1}}(t)=f_{X_1+\cdots+X_{n-1}}(t)=\frac{\lambda^{n-1} t^{n-2}\,e^{-\lambda t}}{(n-2)!}

Than


\begin{aligned} f_{S_{n}}(t)&=f_{X_1+\cdots+X_n}(t)\\ &=f_{S_{n-1}+X_n}(t)\\ &=\int_{-\infty}^\infty f_{S_{n-1}}(t-s)f_{X_n}(s)\,ds \\ &=\int_{-\infty}^\infty f_{X_n}(t-s)f_{S_{n-1}}(s)\,ds \\ &=\int_0^t \lambda e^{-\lambda(t-s)} \frac{\lambda^{n-1} s^{n-2}\, e^{-\lambda s} }{(n-2)!}\,ds\\ &=\frac{\lambda^n e^{-\lambda t}}{(n-2)!}\int_0^t s^{n-2} \,ds\\ &=\frac{\lambda^n t^{n-1} e^{-\lambda t}}{(n-1)!} \\ &=\frac{\lambda^n t^{n-1} e^{-\lambda t}}{\Gamma(n)} \qquad \blacksquare \end{aligned}


(2) is the density function of a Gamma Random Variable.


Convolution and Fourier Transform

Recall the fourier transform of f(x) and it´s inverse


\phi(k)=\int_{-\infty}^\infty e^{i k x}f(x)\,dx(3)

f(x)=\int_{-\infty}^\infty e^{-i k x}\phi(k)\,\frac{dk}{2 \pi}(4)

We have from (1) that


f_{X_1+X_2}(t)=\int_{-\infty}^\infty f_{X_1}(t-x_2)f_{X_2}(x_2)\,dx_2(5)


Let´s take the fourier transform of (5)


\begin{aligned} \int_{-\infty}^\infty e^{i k t }f_{X_1+X_2}(t)\,dt&= \int_{-\infty}^\infty e^{i k t }\int_{-\infty}^\infty f_{X_1}(t-x_2)f_{X_2}(x_2)\,dx_2 \, dt \\ &=\int_{-\infty}^\infty \int_{-\infty}^\infty e^{i k t } f_{X_1}(t-x_2)f_{X_2}(x_2)\,dx_2 \, dt \\ &=\int_{-\infty}^\infty f_{X_2}(x_2)\int_{-\infty}^\infty e^{i k t } f_{X_1}(t-x_2)\, dt\,dx_2 \\ &=\int_{-\infty}^\infty f_{X_2}(x_2)\int_{-\infty}^\infty e^{i k (w+x_2) } f_{X_1}(t-x_2)\, dw\,dx_2 & (t=w+x_2) \\ &=\int_{-\infty}^\infty e^{i k x_2 } f_{X_2}(x_2) \,dx_2\int_{-\infty}^\infty e^{i k w } f_{X_1}(t-x_2)\, dw\\ &=\phi(k)\phi(k)\\ &=\phi^2(k) \qquad \blacksquare \end{aligned}


Therefore , by the inverse transform we obtain:


\begin{aligned} f_{X_1+X_2}(t)&=\int_{-\infty}^\infty e^{-i k t}\phi^2(k)\,\frac{dk}{2 \pi} \\ \end{aligned}


We can now try to extend this idea to the sum of more than two R.V.´s. Lets try to find the density of the sum of three i.i.d. R.V.´s S_3=X_1+X_2+X_3


\begin{aligned} f_{S_3}(t)&=f_{X_1+X_2+X_3}(t)\\ &=f_{S_2+X_3}\\ &=\int_{-\infty}^\infty f_{S_2}(t-x_3)f_{X_3}(x_3)\,dx_3 \\ &=\int_{-\infty}^\infty \left(\int_{-\infty}^\infty f_X_1(t-x_3-x_2)f_{X_2}(x_2)\,dx_2 \right)f_{X_3}(x_3)\,dx_3 \\ &=\int_{-\infty}^\infty \int_{-\infty}^\infty f_X_1(t-x_3-x_2)f_{X_2}(x_2)f_{X_3}(x_3)\,dx_2\,dx_3 \qquad \blacksquare \\ \end{aligned}


It´s fourier transoform is


\begin{aligned} \int_{-\infty}^\infty e^{i k t }f_{S_3}(t)\,dt&=\int_{-\infty}^\infty e^{i k t }\left(\int_{-\infty}^\infty \int_{-\infty}^\infty f_X_1(t-x_3-x_2)f_{X_2}(x_2)f_{X_3}(x_3)\,dx_2\,dx_3\right)\,dt\\ &=\int_{-\infty}^\infty \int_{-\infty}^\infty \int_{-\infty}^\infty e^{i k t } f_X_1(t-x_3-x_2)f_{X_2}(x_2)f_{X_3}(x_3)\,dx_2\,dx_3\,dt\\ &=\int_{-\infty}^\infty \int_{-\infty}^\infty \left(\int_{-\infty}^\infty e^{i k t } f_X_1(t-x_3-x_2)\,dt\right)f_{X_2}(x_2)f_{X_3}(x_3)\,dx_2\,dx_3\\ &=\int_{-\infty}^\infty \int_{-\infty}^\infty \left(\int_{-\infty}^\infty e^{i k (w+x_3+x_2) } f_X_1(w)\,dw\right)f_{X_2}(x_2)f_{X_3}(x_3)\,dx_2\,dx_3\\ &=\int_{-\infty}^\infty e^{i k x_2 }f_{X_2}(x_2)\,dx_2 \int_{-\infty}^\infty e^{i k x_3 }f_{X_3}(x_3)\,dx_3\int_{-\infty}^\infty e^{i k w } f_X_1(w)\,dw\\ &=\phi^3(k)\qquad \blacksquare \\ \end{aligned}


If we keep follwing this reasoning we may obtain


f_{S_n}(t)=\underbrace{\int_{-\infty}^\infty \cdots \int_{-\infty}^\infty}_{(n-1)\,\, \text{times}} f_X_1\left(t-\sum_{k=2}^nx_k\right)f_{X_2}(x_2)\cdotsf_{X_n}(x_n)\,dx_2 \cdots\,dx_n(6)


And it´s fourier transform


\int_{-\infty}^\infty e^{i k t }f_{S_n}(t)\,dt=\phi^n(k)(7)

Giving us

f_{S_n}(t)=\int_{-\infty}^\infty e^{-i k t}\phi^n(k)\,\frac{dk}{2 \pi}(8)

We have previously showed in this post that


\int_{-\infty}^\infty e^{i k x }e^{-a x^2}\,dx=\sqrt{\frac{\pi}{a}}e^{-\frac{k^2}{4a}(9)


If we Consider a normalized standard gaussian with density


f(x)=\frac{1}{\sqrt{2 \pi \sigma^2}}e^{-\frac{x^2}{2\sigma^2}}(10)

By (9) the fourier transform becomes(multiplying by \frac{1}{\sqrt{2 \pi \sigma^2}} and assuming that a=\frac{1}{2 \sigma^2} )


\frac{1}{\sqrt{2 \pi \sigma^2}}\int_{-\infty}^\infty e^{i k x }e^{-\frac{x^2}{2\sigma^2}}\,dx=e^{-\frac{\sigma^2k^2}{2}(11)


Hence, by equation (7) we have that the fourier transform of the density of the sum of n gaussian random variables is given by


\int_{-\infty}^\infty e^{i k t }f_{S_n}(t)\,dt=\phi^n(k)=e^{-\frac{n\sigma^2k^2}{2}(12)


By the inverse transform we have


\begin{aligned} f_{S_n}(t)&=\frac{1}{2\pi}\int_{-\infty}^\infty e^{-ikt}\left(e^{-\frac{n\sigma^2k^2}{2}\right)\,dk\\ &=\frac{1}{2\pi}\int_0^\infty e^{-ikt}\e^{-b k^2}\,dk & \left(b=\frac{n \sigma^2}{2} \right)\\ &\frac{1}{2\pi}\sqrt{\frac{\pi}{b}}e^{-\frac{t^2}{4b}\\ &=\frac{1}{\sqrt{2 \pi n \sigma^2}}e^{-\frac{t^2}{2 n \sigma^2} \qquad \blacksquare \end{aligned}

Which is also a Gaussian!

For our last example lets consider a Cauchy Random Variable. A Cauchy R.V. has the following density:


f(x)=\frac{a}{\pi} \cdot \frac{1}{a^2+x^2}(13)

It was shown in this post that


\int_{-\infty}^\infty \frac{e^{ikx}}{a^2+x^2}\,dx=\frac{\pi e^{-a|k|}}{a}(14)

Hence

\frac{a}{\pi}\int_{-\infty}^\infty \frac{e^{ikx}}{a^2+x^2}\,dx=e^{-a|k|}(15)

We than have

\int_{-\infty}^\infty e^{i k x }f_{S_n}(x)\,dx=\phi^n(k)=e^{-a n|k|}(16)


In order to obtain the density of the sum of n Cauchy R.V.´s we have to evaluate the inverse fourier transform of (16), hence by equation (8) We have


\begin{aligned} f_{S_n}(x)&=\frac{1}{2\pi}\int_{-\infty}^\infty e^{-ikx}\left(e^{-a n|k|}\right)\,dk\\ &=\frac{1}{2\pi}\int_{-\infty}^0 e^{-ikx+ank} \,dk+\frac{1}{2\pi}\int_0^\infty e^{-ikx-ank} \,dk\\ &=\frac{1}{2\pi} \left(-\frac{e^{-(ix-an)k}}{ix-an} \Bigg|_{-\infty}^0\right)+\frac{1}{2\pi} \left(-\frac{e^{-(ix+an)k}}{ix+an} \Bigg|_0^\infty\right)\\ &=\frac{1}{2 \pi}\left(\frac{1}{an+ix}+\frac{1}{an-ix}\right) \\ &=\frac{1}{2 \pi}\frac{an+ix+an-ix}{a^2n^2+x^2} \\ &=\frac{an}{ \pi}\frac{1}{a^2n^2+x^2} \qquad \blacksquare \\ \end{aligned}


Which is also a Cauchy density function!!

Comments

Post a Comment

Popular posts from this blog