MATH 452/STAT 552
Assignment 3
Due: October 30th, 2020 at the beginning of class.
Submission: Upload your solutions of Exercises 3.1–3.5 to Crowdmark as one PDF
file. (Do not hand in any solution to the Supplementary Exercises.)
Exercise 3.1. Let P be the transition probability matrix of an irreducible discrete-
time Markov chain where the state space is E and every state is positive recurrent.
Let A be a nonempty, proper subset of E and pi be the stationary distribution of P .
Given a /∈ E, define E∗ = A ∪ {a} and a new matrix P ∗ = (P ∗ij)i,j∈E∗ by
P ∗ij = Pij, i, j ∈ A;
P ∗ia =
∑
j∈A{
Pij, i ∈ A;
P ∗ak =
1
pi(A{)
∑
j∈A{
pijPjk, k ∈ A;
P ∗aa =
1
pi(A{)
∑
j∈A{
∑
k∈A{
pijPjk,
where pi(A{) =
∑
j∈A{ pij. We also set
pi∗i = pii, i ∈ A; pi∗a = pi(A{).
See [2, Section 2.7.3] for these definitions and the motivation.
(1) Show that P ∗ is a transition probability matrix.
(2) Show that pi∗ is a stationary distribution of P ∗.
Exercise 3.2. Let (Xn;n ≥ 0) be a discrete-time Markov chain with a stationary
distribution pi. Suppose that (Xn) is reversible with respect to pi. Show that for all
integers n ≥ 1 and states i0, i1, · · · , in, it holds that
Ppi(X0 = i0, X1 = i1, · · · , Xn = in) = Ppi(X0 = in, X1 = in−1, · · · , Xn = i0).
Here under Ppi, the PMF of X0 is given by pi.
Exercise 3.3. Given a branching process (Zn;n ≥ 0) with Z0 = 1, denote the
generating function of Zn by fn(a) = E[aZn ] for a ∈ (−1, 1). Show that fn+1(a) =
fn(f1(a)) for all integers n ≥ 1.
1
The following problem from [1, Example 5.8 on p.306] was discussed in the lecture
for the exponential distribution: There are two clerks in a post office. The service
time of clerk i is exponential with parameter λi. When I enter the post office, the
two clerks are busy and there are no others in line. If T denotes my time spent in the
post office, then the problem is to find E[T ].
To get the solution, first, write ei for the service time of the existing customer of
clerk i and let S denote my service time, where e1 and e2 are independent. If e1 < e2,
then I will be served by clerk 1 and so my service time will have the same distribution
as e1. Otherwise, I will be served by clerk 2, and my service time will have the same
distribution as e2.
The beginning equation for the solution is as follows:
E[T ] = E[e1 + S|e1 < e2]P(e1 < e2) + E[e2 + S|e2 ≤ e1]P(e2 ≤ e1). (3.1)
The computations of the terms on the right-hand side of (3.1) apply results of com-
peting exponentials. First,
P(e1 < e2) =
λ1
λ1 + λ2
& P(e2 ≤ e1) = λ2
λ1 + λ2
. (3.2)
Second, write
E[e1 + S|e1 < e2] = E[e1|e1 < e2] + E[S|e1 < e2].
Notice that on {e1 < e2}, (1) e1 = e1∧e2, whereas e1∧e2 is exponentially distributed
with parameter λ1+λ2 and is independent of {e1 < e2}, and (2) S is a random variable
identically distributed as e1 and is independent of (e1, e2). It follows from the last
equality that
E[e1 + S|e1 < e2] = 1
λ1 + λ2
+
1
λ1
.
The same formula holds for E[e2 + S|e2 ≤ e1] by replacing 1/λ1 with 1/λ2. These
two formulas together with (3.1) and (3.2) then yield the explicit solution of E[T ]:
E[T ] =
(
1
λ1 + λ2
+
1
λ1
)(
λ1
λ1 + λ2
)
+
(
1
λ1 + λ2
+
1
λ2
)(
λ2
λ1 + λ2
)
.
(Note that the independence between random variables used above is implicitly as-
sumed in such a service time problem.) The next exercise considers a variation.
Exercise 3.4. There are two jobs to be processed, with the processing time of job i
being exponential with parameter µi. There are also two processors available, one for
each job. The lifetime of processor j is exponential with λj. As before, we assume
independence of all the exponential random variables.
The success of an assignment of the jobs to the processors is defined to be the com-
pletion of the two jobs within the lifetimes of the processors. Now, we assign job i to
processor i for all i = 1, 2.
(1) Find the probability of success of this assignment.
(2) Find the conditional expectation of the total amount of processing times, given
the success of the assignment.
2
Exercise 3.5. A compound Poisson processX is a continuous-time stochastic process
which can be represented as
X(t) =
N(t)∑
n=1
Yn, t ≥ 0,
where (N(t); t ≥ 0) is a Poisson process with rate λ and Y1, Y2, · · · are i.i.d. random
variables [1, p.346]. Write φ for the moment generating function of Y1. Show that the
moment generating function of X(t) has a solution explicit in (λ, t, φ), for any fixed
t ≥ 0.
Supplementary Exercises: 41, 44, 64 [1, Chapter 4] and 7, 12 (a) and (b), 36, 46
[1, Chapter 5].
References
[1] Ross, S. (2019). Introduction to Probability Models. 12th edition. Academic Press.
[2] Aldous, D. J. and Fill, J. A. (2002). Reversible Markov
Chains and Random Walks on Graphs. Available at
https://www.stat.berkeley.edu/users/aldous/RWG/book.html
3

欢迎咨询51作业君