MATH 130C HW5 Name: Selected Solutions

May 15, 2007

7. Individuals join a club in accordance wtih a Poisson process at rate . Each
new member must pass through k consecutive stages to become a full mem-
ber of the club. The time it takes to pass through each stage is exponen-
tially distributed with rate . Let N
i
(t) denote the number of club members
at time t who have passed through exactly i stages, i = 1, . . . , k 1. Also, let

N(t) = (N
1
(t), N
2
(t), . . . , N
k1
(t)).
(a) Is
_

N(t), t 0
_
a continuous-time Markov chain?
Solution: Yes: At any xed time, the state of the system is a random
variable, i.e., the process is stochastic. Also, for any t 0, the state of the
system at a future time u > t depends only upon the state of the system at
time t.
(b) If so, give the innitesimal transition rates. That is, for any state

n =
(n
1
, . . . , n
k1
) give the possible next states along with their innitesimal
rates.
Solution: Let

n = (n
1
, , n
k1
) be the current state of the system.
Because we are considering an innitesimal amount of time, we can assume
that only one event happens. Either a new customer is signed on, or a
customer moves from one stage to the next, or a customer becomes a full
member (leaves the k 1 stage). So, our states are:
S
0
= (n
1
+ 1, n
2
, , n
k1
)
S
1
= (n
1
1, n
2
+ 1, , n
k1
)
.
.
.
S
i
= (n
1
, n
2
, , n
i
1, n
i+1
+ 1, n
i+2
, , n
i1
)
.
.
.
S
k1
= (n
1
, n
2
, , n
k2
, n
k1
1).
Next, we calculate the transition rates q

n,S
i
:
q

n,S
0
= (the arrival rate)
q

n,S
1
= n
1
(rate of progression for one person times number of people)
.
.
.
q

n,S
i
= n
i
for 1 i k 1.
8. Consider two machines, both of which have an exponential lifetime with mean
1/. There is a single repairman that can service machines at an exponential
rate . Set up the Kolmogorov backward equations; you need not solve them.
Solution: Lets set this up as a three-state system:
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 1 of 6
state status
0 all machines work
1 1 machine broken
2 both machines are broken
Lets think about the instantaneous transition rates between these states: If
there are 0 broken machines, they break down at a rate 2. The probability of
two simultaneous break-downs is nearly zero.
q
0,1
= 2, q
0,2
= 0.
If we start with one broken machine, they break down at a rate and are repaired
at a rate :
q
1,0
= , q
1,2
= .
If both machines are broken, they are repaired at a rate of , and at any instant,
no more than one can be repaired. Thus,
q
2,0
= 0, q
2,1
= .
Lastly, lets look at the rates v
i
:
v
0
= q
0,1
+ q
0,2
= 2,
v
1
= q
1,0
+ q
1,2
= + ,
v
2
= q
2,0
+ q
2,1
= .
So, we now set up the equations:
P

i,j
=

k=i
q
i,k
P
k,j
v
i
P
i,j
,
and so
P

0,j
= 2P
1,j
2P
0,j
, j {0, 1, 2}
P

1,j
= P
0,j
+ P
2,j
( + )P
1,j
, j {0, 1, 2}
P

2,j
= P
1,j
P
2,j
, j {0, 1, 2} .
11. Consider a Yule process starting with a single individualthat is, suppose X(0) =
1. Let T
i
denote the time it takes the process to go from a population of size i
to one of size i + 1.
(a) Argue that T
i
, i = 1, . . . , j, are independent exponentials with respective
rates i.
Solution: The Yule birth process is one in which each member gives birth
independently at an exponential rate .
Suppose the population is i, and consider T
i
. For each 1 j i, denote T
j
i
to the time at which the j
th
member of the population gives birth. Then T
j
i
is exponentially distributed and has rate . Also, T
i
is the time of the rst
such birth, so T
i
= min
_
T
j
i
_
i
j=1
. We know that for a bunch of independent
exponential processes with equal rates , this is i, and is also exponentially
distributed.
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 2 of 6
(b) Let X
1
, . . . , X
j
denote independent exponential random variables each hav-
ing rate , and interpret X
i
as the lifetime of component i. Argue that
max(X
1
, . . . , X
j
) =
1
+
2
+ +
j
where
1
,
2
, . . . ,
j
are independent exponentials with respective rates j, (j
1), . . . , .
Hint: Interpret
i
as the time between the i 1 and the ith failure.
Solution: Let
j
denote the time between the (i1)
st
and i
th
failures. Then
the total time for all j components to fail is
1
+ +
j
. Note intuitively
that this time must occur at the time of the last failure, i.e,
max(X
1
, . . . , X
j
) =
1
+ +
j
.
Lastly, consider
1
. Until , none of the j individuals have failed. Each fails
at a rate , and we need the time of the rst failure, i.e., the minimum of j
independent exponentials. Therefore,
1
occurs at rate j. Similarly, for
2
,
we need one of the j 1 remaining items to fail, so
2
(j 1). etc.
(c) Using (a) and (b) argue that
P {T
1
+ + T
j
t} =
_
1 e
t
_
j
.
Solution: First, note that T
1
+ + T
j
is the time at which j com-
ponents have failed, which also equals the max of all the failure times
max(X
1
, . . . , X
j
). Thus,
P {T
1
+ T
j
t} = P {max(X
1
, . . . X
j
) t}
= P {X
1
t and and X
j
t}
=
j

i=1
P {X
i
t} =
_
1 e
t
_
j
.
(d) Use (c) to obtain that
P
1j
(t) =
_
1 e
t
_
j1

_
1 e
t
_
j
= e
t
_
1 e
t
_
j1
and hence, given X(0) = 1, X(t) has a geometric distribution with param-
eter p = e
t
.
Solution: To transition from 1 to j, we need exactly j 1 failures. This is
equal to:
P
1,j
(t) = P ( have exactly j 1 failures )
= P ( have at least j 1 failures ) P ( have at least j failures )
=
_
1 e
t
_
j1

_
1 e
t
_
j
=
_
1 e
t
_
j1
_
1
_
1 e
t
__
=
_
1 e
t
_
e
t
.
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 3 of 6
(e) Now conclude that
P
ij
(t) =
_
j 1
i 1
_
e
ti
_
1 e
t
_
ji
.
Blah blah blah. Read the texts bionomial argument on P. 727.
14. Potential customers arrive at a full-service, one-pump gas station at a Poisson
rate of 20 cars per hour. However, customers will only enter the station for gas if
there are no more than two cars (including the one currently being attended to) at
the pump. Suppose the amount of time required to servicea car is exponentially
distributed with a mean of ve minutes.
(a) What fraction of the attendants time will be spent servicing cars?
(b) What fraction of potential customers are lost?
Solution: First, let X(t) denote the number of cars in the queue, including the
car being serviced, and note that 0 X 2. Let = 20 cars hour
1
denote
the rate of arrivals, and = 12 cars hour
1
denote the service rate. Then note
that X is a birth-death process with birth and death rates

0
=
0
= 0

1
=
1
=

2
= 0
2
= .
In this problem, we shall see the steady-state probabilities P
0
, P
1
, and P
2
of the
states X = 0, X = 1, and X = 2. By the text discussion on P. 370,
P
0
=
0
P
0
=
1
P
1
= P
1
P
1
=
1
P
1
=
2
P
2
= P
2
0 =
2
P
2
=
3
P
3
.
.
.
Furthermore, we know that the limiting probabilities must sum to 1. (i.e., 100%
of all cases are in one state or another at steady state.) Thus,
P
0
+ P
1
+ P
2
= 1
(a) The service person is working i X = 1 or X = 2, so the answer is given by
P
1
+ P
2
P
0
+ P
1
+ P
2
=
1 P
0
1
= 1 P
0
.
Now, we can solve for P
0
:
P
0
+ P
1
+ P
2
= 1.
By the fact that P
2
=

P
1
and P
1
=

P
0
,
1 = P
0
+
_
1 +

_
P
1
= P
0
+
_
1 +

P
0
=
_
1 +

+
_

_
2
_
P
0
.
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 4 of 6
Therefore,
P
0
=
1
1 +

+
_

_
2
,
and our nal answer is
1 P
0
=

+
_

_
2
1 +

+
_

_
2
81.63%.
(b) A customer is lost if and only if they arrive when X = 2. Assuming a
uniform distribution of arrivals (in time), which is true in the long term for
exponential processes, our answer is equal to P
2
, the percentage of the time
in which the system is in state 2. We can also calculate this as above, using
the facts
P
0
=

P
1
and
P
1
=

P
2
,
we can solve for P
2
:
P
2
=
1
1 +

+
_

_
2
18.37%
Notice that as

0 (so cars arrive much more quickly than they are

serviced), P
2
1, and 100% of customers are lost. Likewise, as

(so
cars are serviced much more quickly than they arrive), P
2
0, so 0% of
customers are lost.
17. Each time a machine is repaired it remains up for an exponentially distributed
time with rate . It then fails, and its failure is either of two types. If it is a
type 1 failure, then the time to repair the machine is exponential with rate
1
;
if it is a type 2 failure, then the repair time is exponential with rate
2
. Each
failure is, independently of the time it took the machine to fail, a type 1 failure
with probability p and a type 2 failure with probability 1 p. What propor-
tion of time is the machine down due to a type 1 failure? What proportion of
the time is it down due to a type 2 failure? What proportion of the time is it up?
Solution: For any given machine, it can have one of three states:
state condition
0 machine works
1 machine suered failure type 1 and is being repaired
2 machine suered failure type 2 and is being repaired
For long-term percentages, we need to balance the inow and outow rates for
each state. For state 0, the inow rate is the sum of the repair rates, and the
outow rate is the failure rate. For state 1, the inow rate is the failure rate,
and the outow rate is the repair rate. In mathese:
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 5 of 6
state inow rate outow rate
0
1
P
1
+
2
P
2
pP
0
+ (1 p)P
0
= P
0
1 pP
0

1
P
1
2 (1 p)P
0

2
P
2
The system is in steady-state if all these rates balance. Of course, we have the
additional condition
P
0
+ P
1
+ P
2
= 1.
Lets solve this thing:
1 = P
0
+ P
1
+ P
2
= P
0
+
_
p

1
P
0
_
+
_
(1 p)

2
P
0
_
=
_
1 +
_
p

1
+
(1 p)

2
__
P
0
,
and so
P
0
=
1
1 +
_
p

1
+
(1p)

2
_.
By the other relationships,
P
1
=
p

1
P
0
=
p

1
+
_
p + (1 p)

2
_
and
P
1
=
(1 p)

2
P
0
=
(1 p)

2
+
_
p

1
+ (1 p)
_.
As a way of quickly checking if this is reasonable, suppose that
1
=
2
= , so
both failure types are identical. Then
P
0
=
1
1 +
_
p

+
1p

_ =

+
,
i.e., its equal to a sort of relative repair rate. Likewise, since P
1
and P
2
are
identical states in this case, we can compute
P
1
+ P
2
= =
p
+
+
(1 p)
+
,
which is like the relative failure rate.
Similarly, if p 1, then this should reduce to a system with two states P
0
and
P
1
, and indeed, we see that in this case,
P
0
=

1

1
+
, P
1
=

1
+
, P
2
= 0.
Lastly, the answer to the three questions asked are P
1
, P
2
, and P
0
, respectively.
:-)
Document URL: http://math.uci.edu/~pmacklin/Math130Cspring2007.html
Date: June 7, 2007
Page 6 of 6