Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(This is a differently formulated version of the question. There were no answers, comments or votes on the first version so I thought I'd give it another shot.)

Suppose a server processes jobs that take a random amount of time to process. Denote by $B$ the random variable service time. Suppose that B is exponentially distributed with parameter $\mu$, so $f_{B}(t) = \mu e^{-\mu t}$ and $P(B < t) = 1 - e^{-\mu t}$.

Now we want to consider the possibility that the server fails to process a job and has to start over. In particular, we consider the cases

(1) the breakdown occurs after a fixed amount of time;
(2) the breakdown occurs after a random amount of time, according to some probability density function.

Let $B'$ denote the time passed until the processing fails. Let $p$ be the probability that a job fails to be processed and thus causes the server to start over again. I want to know the distribution, in both cases, of the time it takes for a job to be processed.

I have made attempts at both cases but I'm not sure I'm going about it the right way.

For the first case, suppose the server restarts $N$ times (a random amount). Then I'm interested in $P(NB' + B \leq t)$, which I could compute using the law of total probability, ie $$\begin{eqnarray*}P(NB' + B \leq t) &=& \sum_{k=1}^{\infty} P(NB' + B \leq t|N=k)P(\text{the service fails k times}) \\&=& \sum_{N=1}^{\infty} P(NB' + B \leq t|N=k)p^k \\&=& \sum_{k=1}^{\infty} P(B\leq t - kB')p^k\end{eqnarray*}$$ is this correct or is this nonsense?

As for the second case, I'd suppose that we have iid random variables $B'_1,B'_2,\ldots,B'_N$ which denote the length of time it takes to break down, so then I'd guess that we would want to know $$P(B +\sum_{i=1}^{N} B'_i \leq t) = \sum_{k=1}^{\infty}P(B+\sum_{i=1}^{k}B'_i \leq t|N=k)P(\text{the service fails k times})$$

BI have the feeling that this isn't what the answer should be. Any comments on my interpretation of the question and my suggested way of solving this problem is most appreciated.

share|improve this question
    
I have revised my question. Consider this comment a shameless bump. –  Stijn May 10 '11 at 13:23

1 Answer 1

up vote 2 down vote accepted

The whole processing time of a job is exponential with parameter $\mu$.

The result is a (thinly disguised) version of the waiting time paradox. Here is a proof. Let $T$ denote the whole processing time of a job and $N_t$ the number of breakdowns/restarts that occurred before a given nonnegative time $t$.

For each nonnegative $n$, the event $[T\geqslant t,N_t=n]$ is realized if the first $n$ tries failed and led to a breakdown, and if nothing occurred between the time of the $n$th breakdown/restart and time $t$.

The time of the $n$th restart is $R_n=B'_1+\cdots+B'_n$, hence $$ [T\geqslant t,N_t=n]=[B_1>B'_1,\ldots,B_n>B'_n,t\geqslant R_n,B'_{n+1}>t-R_n,B_{n+1}>t-R_n]. $$ Consider the sigma-algebra $\mathfrak{R}$ generated by the sequence $(B'_k)$, or, equivalently, by the sequence $(R_k)$. Using the fact that, for every $k\leqslant n$, $P(B_k>B'_k|\mathfrak{R})=\mathrm{e}^{-\mu B'_k}$, and the density of $B_{n+1}$, one gets $$ \mathrm P(T\geqslant t,N_t=n|\mathfrak{R})=\mathrm{e}^{-\mu B'_1}\cdots\mathrm{e}^{-\mu B'_n}\cdot\mathrm{e}^{-\mu(t-R_n)}\cdot[R_n\leqslant t<R_n+B'_{n+1}], $$ hence $$ \mathrm P(T\geqslant t,N_t=n|\mathfrak{R})=\mathrm{e}^{-\mu t}\cdot[R_n\leqslant t<R_{n+1}]. $$ Summing over $n\geqslant0$, one gets $ \mathrm P(T\geqslant t|\mathfrak{R})=\mathrm{e}^{-\mu t} $. This proves that $T$ is independent of $\mathfrak{R}$ and exponentially distributed with parameter $\mu$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.