3
$\begingroup$

I'm working on the following problem:

A single server works on an infinite supply of jobs. The amount of time it takes the server to work on a single job is exponential with rate $\mu$, successive processing times being iid. If the service of a job takes less than $b$ units of time, the server immediately starts on a new job. Otherwise, it takes a break for $a > 0$ units of time and then starts a new job immediately afterwards. Suppose that at time zero, the server starts a new job. Let $A(t)$ denote the state of the server at time t. If the server is working at time t, we let $A(t) = 1$, otherwise we let $A(t) = 0$.

The instructions are to derive a renewal equation for $\mathbb P(A(t)=1)$ (where $t>b$) and use the key renewal theorem to compute $\lim_{t\to\infty}\mathbb P(A(t)=1)$. However, it seems like there's a simpler solution:

Let $X_n\stackrel{\mathrm{i.i.d.}}\sim\mathsf {Exp}(\mu)$ and $$\tau = \inf\{n>0: X_n>b\}. $$ Then $\mathbb P(X_1>b)=e^{-\mu b}$, so as $$\{\tau = n\} = \{X_n > b\}\cap\bigcap_{k=1}^{n-1}\{X_n\leqslant b\}, $$ it follows that $$\mathbb P(\tau = n) = \left(1-e^{-\mu b}\right)^{n-1}e^{-\mu b}, n=1,2,\ldots $$ Let $S_n=\sum_{k=1}^n X_k$, then the time until the server takes a break is $S_\tau$. A geometric sum of i.i.d. exponential random variables is again exponential, so $S_\tau\sim\mathsf{Exp}(e^{-\mu b}\mu)$. Letting $U_n\stackrel{\mathrm{i.i.d.}}\sim\mathsf{Exp}(e^{-\mu b}\mu)$ and $D_n\equiv a$ we see that $A(t)$ is the state process corresponding to the alternating renewal process $\{(U_n,D_n):n\geqslant 1\}$. It follows then from the key renewal theorem that $$\lim_{t\to\infty} \mathbb P(A(t)=1) = \frac{\mathbb E[U_1]}{\mathbb E[U_1]+\mathbb E[D_1]} = \frac{e^{\mu b}/\mu}{e^{\mu b}/\mu + a}=\frac{e^{\mu b}}{e^{\mu b}+a\mu}. $$

My questions here are, naturally:

  1. Is my argument correct?
  2. What would the renewal equation look like?
$\endgroup$
  • 1
    $\begingroup$ This looks good to me. Such a process is called an alternating renewal process. The renewal equation and some more information regarding these processes can be found here. $\endgroup$ – Ritz Jun 3 '16 at 8:54
  • $\begingroup$ Quite familiar with alternating renewal processes and with math.uah.edu/stat but thanks :) $\endgroup$ – Math1000 Jun 3 '16 at 10:46
  • 1
    $\begingroup$ Ah, did not know that. Point 2 on the website I linked does answer your second question though. $\endgroup$ – Ritz Jun 3 '16 at 11:14
  • $\begingroup$ For context, this is problem 2 in the Stochastic 642 comprehensive exam at stat-or-old.oasis.unc.edu/resources/ope-res/past%20cwe $\endgroup$ – Math1000 Jan 11 '17 at 15:02
  • $\begingroup$ It also appears in the text, Modeling and Analysis of Stochastic Systems by Kulkarni (3rd Edition) as problem 8.57 but instead asks: $$ \text{Show that } \{A(t), t\ge 0\} \text{ is an ARP.}$$ $$\text{Compute } \lim_{t\to\infty} \mathbb P(A(t)=1). $$ The answer given by the text is indeed the same as I computed. $\endgroup$ – Math1000 Jan 11 '17 at 15:07

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.