4.13.2 Problem 10.6

Review of the problem setup: Imagine there is a queue of length \(r\). Burned out bulbs enter the queue (with inter-arrival time which is a random variable distributed as an exponential with rate \(\lambda \)). Bulbs continue to enter the queue until the queue is full, then at that moment we imagine a single server processing the bulbs in the queue all at once and immediately all \(r\) bulbs become operational again and the queue is now empty. This process repeats again and again.

Part A

A stochastic process \(X\left ( t\right ) \) is defined to have the Markov property if its transition to the next state depends only on the current state and not on any earlier states. In other words it satisfies the following

\[ \Pr \left \{ X\left ( s+t\right ) =j|X\left ( s\right ) =i,X\left ( u\right ) \ \text {for\ any }u<i\right \} =\Pr \left \{ X\left ( s+t\right ) =j|X\left ( s\right ) =i\right \} \]

In this problem \(X\left ( t\right ) \) is the number of burned out bulbs in the queue at any time \(t\). When \(X\left ( t\right ) <r\) then \(X\left ( t\right ) \) can be viewed as a counting process (or pure birth process) or a Poisson process (until the queue become full).

Therefore, The time between each successive events (where an event causes the count to increase by one) is a random variable with exponential distribution (we are also given this fact in the problem). But the exponential distribution is memoryless⁶ by definition. Therefore it does not depend on clock time but only on the length of the time interval. Hence the process satisfies the Markov property.

part B

A stochastic process \(X\left ( s\right ) \) is defined to be stationary⁷ if its state transition \(p_{ij}\left ( t\right ) \) do not depend on when the transitions happen but only on the time interval \(t\). In other words, random process \(X\left ( s\right ) \) is stationary if

\[ \Pr \left \{ X\left ( s+t\right ) =j|X\left ( s\right ) =i\right \} =\Pr \left \{ X\left ( c+t\right ) =j|X\left ( c\right ) =i\right \} \]

For any \(c,s\geq 0.\) So, letting \(c=0\), the system is stationary if

\[ \Pr \left \{ X\left ( s+t\right ) =j|X\left ( s\right ) =i\right \} =\Pr \left \{ X\left ( t\right ) =j|X\left ( 0\right ) =i\right \} \]

This process is clearly stationary, since it is a counting process (when \(X\left ( t\right ) \leq r-1\)). A counting Poisson process is stationary since it does not depend on clock time as was argued in part (A). To show this more clearly, since this is a counting process, then by definition of the Poisson process

\[ \Pr \left ( X\left ( s+t\right ) -X\left ( s\right ) =n\right ) =e^{-\lambda t}\frac {\left ( \lambda t\right ) ^{n}}{n!}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n=0,1,\cdots ,r-1 \]

We see that the probability of \(X=n\) does not depend on \(s\) and depends only on the time interval \(t\). If this was a non-stationary process, then \(s\) would appear in the RHS above. I.e. the probability of the random variable would depend on clock time, but we see from the above definition that it does not.

Part(c)

A stochastic process is a pure jump process if the transition probabilities can be written as

\(p_{ii}\left ( h\right ) =1-v_{i}h+o\left ( h\right ) \) and \(p_{ij}\left ( h\right ) =q_{ij}h+o\left ( h\right ) \) as \(h\rightarrow 0^{+}\)

In this problem \(p_{ii}\left ( h\right ) \) is the probability than no bulb burns out during an interval \(h\). This is given by the probability than no bulb burns out from the current number of functional bulbs which is \(N-i\). Due to independence, we obtain

\[ p_{ii}\left ( h\right ) =\left ( 1-\lambda h+o\left ( h\right ) \right ) ^{\left ( N-i\right ) }\]

Applying Binomial expansion \(\left ( a+b\right ) ^{n}={\displaystyle \sum \limits _{k=0}^{n}} \begin {pmatrix} n\\ k \end {pmatrix} a^{n-k}b^{k}\), to the above, and taking \(a=1,b=-\lambda h+o\left ( h\right ) ,n=N-i\) we obtain

\begin{align*} p_{ii}\left ( h\right ) & =1+\left ( N-i\right ) \left ( -\lambda h+o\left ( h\right ) \right ) +\text {higher order terms in }o\left ( h\right ) \text { which can be ignored when }h\rightarrow 0^{+}\\ & =1-N\lambda h+i\lambda h+o\left ( h\right ) \\ & =1-h\lambda \left ( N-i\right ) +o\left ( h\right ) \end{align*}

Hence we can write \(p_{ii}\left ( h\right ) =1-v_{i}h+o\left ( h\right ) \) where \(v_{i}=\lambda \left ( N-i\right ) \)

Now \(p_{ij}\left ( h\right ) \) is the probability that there will be \(j\) failed bulbs after \(h\) units of time given that there is already \(i\) failed bulbs. For this to occur, then we need to have \(j-i\) bulbs fail in \(h\) units of time. We can solve for the general case when \(j-i>1,\,\ \)but since we will let \(h\rightarrow 0^{+}\,\ \)it is most likely that there will be only one event occur (one bulb fail) during this time, and we can collect all other less likely probabilities in the \(o\left ( h\right ) \) term. Hence we will only consider \(p_{i,i+1\text { }}\)in the following.

\begin{align*} p_{i,i+1}\left ( h\right ) & =\begin {pmatrix} N-i\\ 1 \end {pmatrix} \left ( \lambda h+o\left ( h\right ) \right ) \left ( 1-\lambda h+o\left ( h\right ) \right ) ^{N-i-1}+o\left ( h\right ) \\ & =\left ( N-i\right ) \lambda h+o\left ( h\right ) \end{align*}

Therefore from \(p_{ij}\left ( h\right ) =q_{ij}h+o\left ( h\right ) \) we see that \(q_{i,i+1}=\left ( N-i\right ) \lambda \) i.e. \(\lambda _{i}=\left ( N-i\right ) \lambda \ \ \ \ \ \ \ \ i=0,1,\cdots r-1\)

Hence the \(Q\) matrix (The rate matrix) is

\[ Q=\begin {bmatrix} & \text {{\LARGE 0}} & \text {{\LARGE 1}} & \text {{\LARGE 2}} & {\LARGE \cdots } & \text {{\LARGE r-1}}\\ \text {{\LARGE 0}} & -\lambda N & \lambda N & 0 & 0 & 0\\ \text {{\LARGE 1}} & 0 & -\lambda \left ( N-1\right ) & \lambda \left ( N-1\right ) & 0 & 0\\ \text {{\LARGE 2}} & 0 & 0 & -\lambda \left ( N-2\right ) & \lambda \left ( N-1\right ) & 0\\ {\LARGE \vdots } & \mathbf {\vdots } & \mathbf {\vdots } & \mathbf {\vdots } & \mathbf {\vdots } & \mathbf {\vdots }\\ \text {{\LARGE r-1}} & \lambda \left ( N-r+1\right ) & & & & -\lambda \left ( N-r+1\right ) \end {bmatrix} \]

Part (d)

Figure 4.4: rate flow diagram for problem 10.6

The balance equation can be obtained from balancing the flow out rate of a state \(i\) (which is given by \(v_{i}\)) by all the flow in rate into the state which is given by \({\displaystyle \sum \limits _{v\neq i}} q_{v,i}\) as illustrated below for the above problem

Hence we write

\[ v_{i}\pi _{i}=q_{i-1,i}\pi _{i-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots r-1 \]

and for state \(i=0\) we have

\[ v_{0}\pi _{0}=q_{r-1,0}\pi _{r-1}\]

Therefore we obtain

\begin{align*} \lambda \left ( N-i\right ) \pi _{i} & =\left ( N-i+1\right ) \lambda \pi _{i-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots r-1\\ \lambda N\pi _{0} & =\left ( N-r+1\right ) \lambda \ \pi _{r-1}\ \ \ \ \ \ \ \ \ \ \ \ \ i=0\ \ \end{align*}

Hence we have for \(\ i=1,2,\cdots r-1\)

\begin{align*} \lambda \left ( N-1\right ) \pi _{1} & =N\lambda \pi _{0}\\ \lambda \left ( N-2\right ) \pi _{2} & =\lambda \left ( N-1\right ) \pi _{1}\\ \lambda \left ( N-3\right ) \pi _{3} & =\lambda \left ( N-2\right ) \pi _{2}\\ & \vdots \\ \lambda \left ( N-r+1\right ) \pi _{r-1} & =\lambda \left ( N-r\right ) \pi _{r-2}\end{align*}

Therefore we have

\begin{align*} \pi _{1} & =\frac {N}{N-1}\pi _{0}\\ \pi _{2} & =\frac {N-1}{N-2}\pi _{1}\\ \pi _{3} & =\frac {N-2}{N-3}\pi _{2}\\ & \vdots \\ \pi _{r-1} & =\frac {N-r}{N-r+1}\pi _{r-2}\end{align*}

back substitute, we obtain

\begin{align*} \pi _{1} & =\frac {N}{N-1}\pi _{0}\\ \pi _{2} & =\frac {N-1}{N-2}\frac {N}{N-1}\pi _{0}\\ \pi _{3} & =\frac {N-2}{N-3}\frac {N-1}{N-2}\frac {N}{N-1}\pi _{0}\\ & \vdots \\ \pi _{r-1} & =\frac {N-r}{N-r+1}\frac {N-r-1}{N-r}\cdots \frac {N}{N-1}\pi _{0}\end{align*}

Hence

\begin{align*} \pi _{1} & =\frac {N}{N-1}\pi _{0}\\ \pi _{2} & =\frac {N}{N-2}\pi _{0}\\ \pi _{3} & =\frac {N}{N-3}\pi _{0}\\ & \vdots \\ \pi _{r-1} & =\frac {N}{N-r+1}\pi _{0}\end{align*}

We notice that the last equation above, is the same as for the case \(i=0\). Hence we have one of the \(r\) equations duplicated. Hence we need one more equation to solve for the unknowns \(\pi _{i}\) and for that we use \({\displaystyle \sum \limits _{i=0}^{r}} \pi _{i}=1\)

Therefore, the general expression for \(\pi _{i}\) is

\begin{equation} \pi _{i}=\frac {N}{N-i}\pi _{0}\ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,r-1 \tag {1}\end{equation}

Now since \(\pi _{0}+\pi _{1}+\cdots +\pi _{r-1}=1\), then we write

\begin{align} \pi _{0}+{\displaystyle \sum \limits _{i=1}^{r}} \frac {N}{N-i}\pi _{0} & =1\nonumber \\ \pi _{0}\left ( 1+N{\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}\right ) & =1\nonumber \\ \pi _{0} & =\frac {1}{1+N{\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}} \tag {2}\end{align}

So now that we know \(\pi _{0}\) from (2), we substitute it into (1) and solve for the remaining \(\pi _{i}\)

\begin{align} \pi _{i} & =\frac {N}{N-i}\frac {1}{\left ( 1+N{\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}\right ) }\nonumber \\ & =\frac {N}{\left ( N-i\right ) +\left ( N-i\right ) N{\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}} \tag {3}\end{align}

But

\[{\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}=\frac {1}{N-1}+\frac {1}{N-2}+\cdots +\frac {1}{N-r}={\displaystyle \sum \limits _{k=1}^{N-1}} \frac {1}{k}-{\displaystyle \sum \limits _{k=1}^{N-r-1}} \frac {1}{k}\]

Which is the difference between 2 partial sums of harmonic numbers. Let \(H_{n}={\displaystyle \sum \limits _{k=1}^{n}} \frac {1}{k}\), then \({\displaystyle \sum \limits _{i=1}^{r}} \frac {1}{N-i}=H_{N-1}-H_{N-r-1}\) hence (3) becomes

\begin{align*} \pi _{i} & =\frac {N}{\left ( N-i\right ) \left ( 1+N\left ( H_{N-1}-H_{N-r-1}\right ) \right ) }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,r-1\ \\ & =\frac {1}{\left ( N-i\right ) \left ( \frac {1}{N}+H_{N-1}-H_{N-r-1}\right ) }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,r-1 \end{align*}

Hence

\[ \pi _{i}=\frac {1}{\left ( N-i\right ) \left ( H_{N}-H_{N-r-1}\right ) }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,r-1 \]

This is a small program which show the long term \(\pi \) for \(N=100,r=10\) using the above equation

l.609 — TeX4ht warning — \SaveEverypar’s: 3 at \begindocument and 4 \enddocument —

⁶A memorless random variable \(X\) is one in which \(\Pr \left ( X>t+h|X>t\right ) =\Pr \left ( X>h\right ) \)

⁷In Linear system theory, the term time-invariant is used.