HW Math 504. Spring 2008. CSUF

Problems 10.5 and 10.6

by Nasser Abbasi

Problem 10.5


10_5.png
Solution
10_5_diagram.png
Illustrating model diagram for problem 10.5

In the above, $i$ is the number of broken machines in the queue. $m$ is maximum capacity of the operating room. The goal is to keep this room filled to its capacity. In other words, to keep $m$ machines in operations. $n$ is the capacity of the spare room.

Calculating arrival rates:

Need to determine MATH This can happen when one machine fails, but no server completes its service meanwhile. Hence we do not need to consider the servers part in this analysis. There are 2 cases to consider:

  1. $i\leq n$ (there are $m$ machines in operations)MATH In the above, the last term $o\left( h\right) $ accounts for other possible conditions under which $i$ can increase by one but which is considered to be less likely, such as 2 machines break down and one server completes its service.
    In the above, MATH simplifies to zero when $h$ is very small, hence the above equation becomes MATH Comparing the above with the Hence we see MATH we see thatMATH or in other words, MATH

  2. $n<i\leq n+m$ (there are less than $m$ machines in operations)MATH Hence we see that MATH or in other words, MATH

Calculating departure rates:

Need to determine $p_{i,i-1}$, this can happen when a server completes its job but no machine fails meanwhile, Hence we only need to consider the servers. There are 2 cases to consider:

  1. $1\leq i<s$ (Queue is empty and not all servers at working on fixing machines at hand)MATH

    Hence $q_{i,i-1}=i\mu$, or since this is a birth/death process, we write MATH

  2. $s\leq i$ (All servers at busy)MATH

    Hence $q_{i,i-1}=s\mu$, Hence MATH

Therefore, we summarize all the above as follows

Arrival rate MATH for $i\leq n$ and MATH for $\ \ n<i\leq n+m$
$.$

Departure rate $\mu_{i}=i\mu$ for $\ 1\leq i<s$ and $\mu_{i}=s\mu$ for $s\leq i$

Notice that

arrival rate does not depend on the number of servers $s$
.

The following state transition diagram illustrates the above result, with arrows leaving/entering states show the rate of arrival and departure on them per the above result. To make the diagram easier to make, I assume the following values: $s=3,m=5,n=2$

Notice that $\mu_{0}=0$ and $\lambda_{n+m}=0$ as expected.
flow_10_5.png
Now compute the steady state distribution $\pi$ (This is not asked for in this problem, but need to do this to solve problem 12.3 later on and implement it)

Starting with the balance equation, where to balance the rate out of a state, with the rate into a state. We have

MATH

Hence for state $i=0$ we have

MATH

But $v_{0}=\lambda_{0}$ and $q_{1,0}=\mu_{1}$ hence

MATH

For state $i=1$ we have

MATH

but MATH, MATHhence the above becomes

MATH

But from (1) we have MATH, hence the above becomes

MATH

Continue this way, we obtain that

MATH

From the above, if we solve in terms of $\pi_{0}$ we obtain that

MATH

and with the equation MATH we can now solve for all $\pi_{i}$ as follows

MATH

Hence

MATH

Now that $\pi_{0}$ is found, we can find the remaining $\pi_{i}$ using (3)

Problem 10.6


10_6.png
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 followingMATH In this problem $X\left( t\right) $ is the number of burned out bulbs in the queue at any time $t$. When MATH 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 Note_1 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 Note_2 if its state transition MATH 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

MATH For any $c,s\geq0.$ So, letting $c=0$, the system is stationary ifMATH This process is clearly stationary, since it is a counting process (when MATH). 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 processMATH 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

MATH and MATH as $h\rightarrow0^{+}$

In this problem MATH 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 MATH

Applying Binomial expansion MATH, to the above, and taking MATH we obtainMATH Hence we can write MATH where

MATH

Now MATH 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 MATHit 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.MATH

Therefore from MATH we see that MATH i.e.

MATH

Hence the $Q$ matrix (The rate matrix) isMATH

Part (d)


balance_equation_10_6_one.png
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 MATH as illustrated below for the above problem


balance_equation_10_6_two.png

Hence we write

MATH

and for state $i=0$ we have

MATH

Therefore we obtain

MATH

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

MATH

Therefore we have

MATH

back substitute, we obtain

MATH

Hence

MATH

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 MATH

Therefore, the general expression for $\pi_{i}$ is

MATH

Now since MATH, then we write

MATH

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

MATH

But MATH

Which is the difference between 2 partial sums of harmonic numbers. Let MATH, then MATH hence (3) becomes

MATH

Hence

MATH

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


code_10_6.png