questions is too complicated to yield closed-form
solutions. For example, in a system where the
time between successive customer arrivals has a
particular pdf and the service time of any particu-
lar customer has another pdf, simulation can pro-
vide information about the probability that the
system is empty when a customer arrives, the
expected number of customers in the system, and
the expected waiting time in queue. Such studies
depend on being able to generate observations
from a specified probability distribution.
The rejection method gives a way of generating an
observation from a pdf f(·) when we have a way of
generating an observation from g(·) and the ratio
f(x)/g(x) is bounded, that is, c for some finite c.
The steps are as follows:
1. Use a software package’s random number
generator to obtain a value u from a uniform
distribution on the interval from 0 to 1.
2. Generate a value y from the distribution with
pdf g(y).
3. If u f(y)/cg( y), set x ¼ y (“accept” x); other-
wise return to step 1. That is, the procedure is
repeated until at some stage u f (y)/cg(y).
a. Argue that c 1. [Hint:Ifc < 1, then f( y) <
g(y) for all y; why is this bad?]
b. Show that this procedure does result in
an observation from the pdf f
(·); that is,
P(accepted value x) ¼ F(x). [Hint:
This probability is PðfU f ðyÞ=cgðyÞg \
fY xgÞ; to calculate, first integrate with
respect to u for fixed y and then integrate
with respect to y.]
c. Show that the probability of “accepting” at
any particular stage is 1/c. What does this
imply about the expected number of stages
necessary to obtain an acceptable value?
What kind of value of c is desirable?
d. Let f(x) ¼ 20x(1 x)
3
for 0 < x < 1,
a particular beta distribution. Show that
taking g(y) to be a uniform pdf on (0, 1)
works. What is the best value of c in this
situation?
86. You are driving on a highway at speed X
1
. Cars
entering this highway after you travel at speeds
X
2
, X
3
, ... . Suppose these X
i
’s are independent
and identically distributed with pdf f(x) and cdf
F(x). Unfortunately there is no way for a faster car
to pass a slower one – it will catch up to the slower
one and then travel at the same speed. For exam-
ple, if X
1
¼ 52.3, X
2
¼ 37.5, and X
3
¼ 42.8, then
no car will catch up to yours, but the third car will
catch up to the second. Let N ¼ the number of cars
that ultimately travel at your speed (in your
“cohort”), including your own car. Possible values
of N are 1, 2, 3, ... . Show that the pmf of N is
p(n) ¼ 1/[n(n + 1)], and then determine the
expected number of cars in your cohort. [Hint: N
¼ 3 requires that X
1
< X
2
, X
1
< X
3
, X
4
< X
1
.]
87. Suppose the number of children born to an indi-
vidual has pmf p(x). A Galton–Watson branching
process unfolds as follows: At time t ¼ 0, the
population consists of a single individual. Just
prior to time t ¼ 1, this individual gives birth to
X
1
individuals according to the pmf p(x), so there
are X
1
individuals in the first generation. Just prior
to time t ¼ 2, each of these X
1
individuals gives
birth independently of the others according to the
pmf p(x), resulting in X
2
individuals in the second
generation (e.g., if X
1
¼ 3, then X
2
¼ Y
1
+ Y
2
+ Y
3
,
where Y
i
is the number of progeny of the ith
individual in the first generation). This process
then continues to yield a third generation of size
X
3
, and so on.
a. If X
1
¼ 3, Y
1
¼ 4, Y
2
¼ 0, Y
3
¼ 1, draw a tree
diagram with two generations of branches to
represent this situation.
b. Let A be the event that the process ultimately
becomes extinct (one way for A to occur would
be to have X
1
¼ 3 with none of these three
second-generation individuals having any
progeny) and let p* ¼ P(A). Argue that p*
satisfies the equation
p¼
X
ðpÞ
x
pðxÞ
That is, p* ¼ h(p*) where h(s) is the probability
generating function introduced in Exercise 138
from Chapter 3. Hint: A ¼[
x
(A \ {X
1
¼ x}),
so the law of total probability can be applied.
Now given that X
1
¼3, A will occur if and only
if each of the three separate branching pro-
cesses starting from the first generation ulti-
mately becomes extinct; what is the
probability of this happening?
c. Verify that one solution to the equation in (b)
is p* ¼ 1. It can be shown that this equation
has just one other solution, and that the proba-
bility of ultimate extinction is in fact the smal-
ler of the two roots. If p(0) ¼ .3, p(1) ¼ .5, and
p(2) ¼ .2, what is p*? Is this consistent with the
value of m, the expected number of progeny
from a single individual? What happens if
p(0) ¼ .2, p(1) ¼ .5, and p(2) ¼ .3?
88. Let f(x) and g(y) be pdf’s with corresponding cdf’s
F(x) and G(y), respectively. With c denoting a
numerical constant satisfying |c| 1, consider
f ðx; yÞ¼f ðxÞgðyÞf1 þ c½2FðxÞ1½2Gð
yÞ1g
Supplementary Exercises 281