# How to calculate $P(\sum_{i=1}^{m}(A_i+S_i)\le L)$ with $A_i,L\sim\text{exp}(\lambda),S_i\sim\text{exp}(\mu)$ and positive integers $\lambda\neq\mu$?

Recently I was stumped by the calculation of the probability $$\mathbb{P} \big(\sum_{i=1}^{m} (A_i + S_i) \le L < \sum_{i=1}^{m+1} (A_i + S_i) \big)$$ where $A_i \sim \text{exp}(\lambda), S_i \sim \text{exp}(\mu), L \sim \text{exp}(\lambda)$ are mutually independent, $\lambda \neq \mu$ are two positive integers, and $m$ is an integer parameter.

My attempt:

I failed at the very start while calculating the density function of $\sum_{i=1}^{m} (A_i + S_i)$: $$\sum_{i=1}^{m} (A_i + S_i) = \sum_{i=1}^{m}{A_i} + \sum_{i=1}^{m}{S_i} = \big( A \sim \Gamma(m, \lambda) \big) + \big( S \sim \Gamma(m, \mu) \big)$$ Considering the two Gamma random variable $A$ and $S$, their convolution is: $$p_{A+S}(a) = p_{A} \ast p_{S} (a) = \int_{0}^{a} f_{A}(a-y) f_{S}(y) dy \\ = \int_{0}^{a} \frac{\lambda e^{-\lambda (a-y)} (\lambda (a-y))^{m-1}}{\Gamma(m)} \frac{\mu e^{-\mu y} (\mu y)^{m-1}}{\Gamma(m)} dy \\ = e^{-\lambda a} \frac{\lambda^m \mu^m}{\Gamma(m) \Gamma(m)} \int_{0}^{a} e^{(\lambda - \mu) y} \large((a-y)y \large)^{m-1} dy$$

And my failure:

I was not able to go any further with the integral. And you can image what a messy calculation we will run into when we are going to take the second step involving $\sum_{i=1}^{m} (A_i + S_i) \le L$.

My questions:

Generally, my question is how to make the calculation tractable.

Specifically,

1. Has the probability been studied in research papers?
People interested in its background in "alternating renewal process" are referred to the following part of the post.

2. What is the density function of $\big( A \sim \Gamma(m, \lambda) \big) + \big( S \sim \Gamma(m, \mu) \big)$ given that $m$ is an integer and $\lambda \neq \mu$ are positive integers?
If there is no nice closed form, can we make some good approximation?
Related post: at Math.SE (without proper answers yet).

3. For the whole calculation, is it feasible to obtain numerical solution using mathematical softwares?
Are there any off-the-shelf libraries for this purpose?

For people who want to know the background of the probability in "alternating renewal process":

Background: Consider an alternating renewal process, in which a system can be in one of two states: on or off. Whenever it is off, it takes a time $A_i \sim \text{exp}(\lambda)$ before turning on. Whenever it becomes on, it remains on for a time $S_i \sim \text{exp}(\mu)$. Initially the system is off. A cycle $c_i$ consists of the $i$th off-state and the $i$th on-state. All $A_i$ and $S_i$ are mutually independent and $\lambda \neq \mu$ are two positive integers.

Problem: Given a time period $L \sim \text{exp}(\lambda)$, what is the probability that exactly $m$ cycles occur in $L$?
Related post: at MO: its origin; many thanks to @user137846.

-

Call the left resp. right hand sum $R_m$ resp. $R_{m+1}$. As $L$ is $\exp(\lambda)$ and independent of $(R_m,R_{m+1})$ , taking expection with resp. to $L$ first gives $$\mathbb{P}(R_m\leq L < R_{m+1})=\mathbb{E}(e^{-\lambda R_m}-e^{-\lambda R_{m+1}})= \left(\dfrac{1}{2}\dfrac{\mu}{\mu+\lambda}\right)^m\left(1-\dfrac{1}{2}\dfrac{\mu}{\mu+\lambda}\right)$$ where we have used that the individual summands of $R_m$ resp. $R_{m+1}$ have Laplace-transform $$\mathbf{E}(e^{-p(S_i+A_i)})=\dfrac{\lambda}{\lambda+p}\dfrac{\mu}{\mu+p}$$

-
Thanks for your neat answer avoiding the messy calculation of $\Gamma(m, \lambda) + \Gamma(m, \mu)$. Basically it is beyond my current knowledge. Could you please offer me more details or references to the techniques you used such as "Laplace-transform" and "taking expectation w.r.t. $L$"? – hengxin May 27 '14 at 3:34
(1) For the first step I've only used Fubini's theorem. (2) The Laplace-transform of a (nonnegative) rv $X$ is just the function $p\mapsto \mathbb{E}e^{-pX}$. (3) You can find both e.g. in W.Feller, An Intro. to Prob. Theory 2, (1970) – esg May 27 '14 at 18:16
I have borrowed the book by W.Feller from our library. It is hard for me to find where the Fubini theorem is (in the Chinese translation version). The Laplace-transform can be found easily in the table of contents. Are you referring to [Fubini's theorem [wiki]](en.wikipedia.org/wiki/Fubini's_theorem)? In addition, is your approach general enough to handle with another similar probability: $$\mathbb{P} \big(\sum_{i=1}^{m} S_i + \sum_{i=1}^{m-1} A_i \le L < \sum_{i=1}^{m+1} S_i + \sum_{i=1}^{m} A_i \big)$$ where the numbers of $S_i$ and $A_i$ differ by one? Thanks. – hengxin Jun 5 '14 at 12:54
1) Yes, I am referring to Fubini's theorem (as it is formulated in the link you give. It allows (under appropriate conditions) to compute a multiple integral as an iterate integral) (2) if $L$ is independent of $(R_m,R_{m+1})$ and $0\leq R_m \leq R_{m+1}$ the first step above is valid (3) thus you only have to compute $\mathbb{E}e^{-\lambda R_m}$ resp.$\mathbb{E}e^{-\lambda R_{m+1}}$ (4) for your case (independent summands) it's easy: just use the product rule for the expectation of a product independent rvs – esg Jun 6 '14 at 13:52
By Fubini's theorem you proceed as follows: (1) in the first step consider the values $0\leq r_m < r_{m+1}$ of $R_m$ resp. $R_{m+1}$ as fixed and integrate with resp. to $L$, you get $\mathbb{P}(r_m\leq L < r_{m+1})=\exp(-\lambda r_m)- \exp(-\lambda r_{m+1})=:f(r_m,r_{m+1})$ (2) in the second step you integrate $f$ with resp. to $(R_m,R_{m+1}$ – esg Nov 17 '14 at 19:55

You are looking at summation of independent gamma random variables $\sum_i X_i$, in the hard case where the $X_i$ have different scale parameters. It was studied in:

P. G. Moschopoulos (1985) The distribution of the sum of independent gamma random variables, Annals of the Institute of Statistical Mathematics, 37, 541-544

A. M. Mathai (1982) Storage capacity of a dam with gamma type inputs, Annals of the Institute of Statistical Mathematics, 34, 591-597

-
Thanks. I need time to read and understand them. – hengxin May 25 '14 at 7:18