1
$\begingroup$

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

  • 0
    I have revised $m$y question. Consider this comment a shameless bum$p$.2011-05-10

1 Answers 1

2

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 hence $ \mathrm P(T\geqslant t,N_t=n|\mathfrak{R})=\mathrm{e}^{-\mu t}\cdot[R_n\leqslant t 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$.