Below is a list of practice questions for the nal exam. Any question similar to a quiz, homework,
or example problem has a chance of being on the exam. I suggest going over previous exams and
practice exams as well.
1. Let X and Y be jointly continuous random variables. Each of the parts below has an un nished
equality which can be completed with one of the following options: E[X], E[Y], X, or Y. Some
of these options might be used more than once, and others might not be used at all. After
each equal sign, please indicate the appropriate option. For example, if the un nished equality
(c) If X is a function of Y, i.e., X = f(Y), then
2. Let (Xt)1t=0 be a stationary discrete time Markov chain with jump diagram
(a) Find the transition matrix P for this process. (Please order the matrix respecting the
order on the state space S =f0;1;2;3g). No justi cation is needed.
(b) Give the system of equations or matrix equation you would use to solve the following:
Starting from state 0, nd the expected time (expected number of jumps) it takes the
process to hit either state 2 or 3. That is, if A = f2;3g, nd the expected rst hitting
time of A. You do not need to solve the system, but it should be clearly written out and
at the point where simple linear algebraic means can solve it.
Solution: Let A = f2;3g and A he the rst hitting time of A. We want to nd
E0[ A], the expected number of ips until we hit A given we start at state 0. Note that
E2[ A] = E3[ A] = 0. We have the following system of equations:
E0[ A] = p0;0(1 + E0[ A]) +p0;1(1 + E1[ A] +p0;2(1 + E2[ A]) +p0;3(1 + E3[ A])
E1[ A] = p1;0(1 + E0[ A]) +p1;1(1 + E1[ A] +p1;2(1 + E2[ A]) +p1;3(1 + E3[ A])
Filling in the probabilities, we have
E0[ A] = 13E1[ A] + 13E2[ A] + 13E3[ A] + 1
E1[ A] = 12E0[ A] + 12E3[ A] + 1
Plugging in values that we know:
E0[ A] = 13E1[ A] + 1
E1[ A] = 12E0[ A] + 1
Page 3
(Stopping here is ne for the nal, but we will solve the problem for completeness.)
Solving for E0[ A], we have
E0[ A] = 13E1[ A] + 1 = 13
1
2E0[ A] + 1
+ 1 = 16E0[ A] + 43
=) 56E0[ A] = 43 =) E0[ A] = 85
(c) Give the system of equations or matrix equation you would use to solve the following:
Starting from state 0, nd the probability that the process will hit state 3 before hitting
state 2. You do not need to solve the system, but it should be clearly written out and at
the point where simple linear algebraic means can solve it.
Solution: Let E be the event that the process hits state 3 before hitting state 2. We
want to nd P0(E). Note that
P2(E) = P1(EjX1 = 2) = P0(EjX1 = 2) = 0;P3(E) = 1
and for all other i;j2S, Pi(EjX1 = j) = Pj(E).
P0(E) = p0;0P0(EjX1 = 0) +p0;1P0(EjX1 = 1) +p0;2P0(EjX1 = 2) +p0;3P0(EjX1 = 3)
P1(E) = p1;0P1(EjX1 = 0) +p1;1P1(EjX1 = 1) +p1;2P1(EjX1 = 2) +p1;3P1(EjX1 = 3)
Plugging in the probabilities,
P0(E) = 13P1(E) + 13P3(E)
P1(E) = 12P0(E) + 12P3(E)
Let x = P0(E); y = P1(E). We will solve the system:
(
3x y = 1
x+ 2y = 1 =)
(
3x y = 1
3x+ 6y = 3 =) 5y = 4
We have
x = P0(E) = 3=5; y = P1(E) = 4=5
and the probability that starting from state 0 the process will hit state 3 before hitting
state 2 is 3/5.
(d) Give the system of equations or matrix equation you would use to solve the following:
Starting from state 0, nd the probability that the process will land in state 3 before
landing in state 2. You do not need to solve the system, but it should be clearly written
out and at the point where simple linear algebraic means can solve it.
Solution: Let E be the event that the process lands in state 3 before landing in state
Page 4
2. We want to nd P0(E). Note that
P2(E) = P1(EjX1 = 2) = P0(EjX1 = 2) = 0;P3(EjX1 = 2) = 1
and for all other i;j2S, Pi(EjX1 = j) = Pj(E).
P0(E) = p0;0P0(EjX1 = 0) +p0;1P0(EjX1 = 1) +p0;2P0(EjX1 = 2) +p0;3P0(EjX1 = 3)
P1(E) = p1;0P1(EjX1 = 0) +p1;1P1(EjX1 = 1) +p1;2P1(EjX1 = 2) +p1;3P1(EjX1 = 3)
P3(E) = p3;0P3(EjX1 = 0) +p3;1P3(EjX1 = 1) +p3;2P3(EjX1 = 2) +p3;3P3(EjX1 = 3)
Plugging in the probabilities,
P0(E) = 13P1(E) + 13P3(E)
P1(E) = 12P0(E) + 12P3(E)
P3(E) = 13P0(E) + 13P1(E) + 13
(Stopping here is ne for the nal, but we will complete the problem.)
Let x = P0(E); y = P1(E); z = P3(E). We will solve the system:
8>
:
3x y z = 0
x+ 2y z = 0
x y + 3z = 1
=)
(
4x 3y = 0
4x+ 5y = 1 =) 2y = 1
We have
x = P0(E) = 3=8; y = P1(E) = 1=2; z = P3(E) = 1=4
and the probability that starting from state 0 the process will land in state 3 before
landing in state 2 is 3/8.
3. Let P be the stochastic matrix giving rise to the following jump diagram
Let C0 =f0;1g, C2 =f2;3g, and C4 =f4;5g be the communication classes.
(a) For two of the three communication classes C, you are guaranteed that an invariant dis-
tribution C exists for the reduced matrix PC. So, for two of the reduced matrices PC,
nd invariant distributions C.
Page 5
Solution: The two closed communication classes, C0 and C4, are positive recurrent (only
nitely many states) and so admit an invariant distribution. We solve ~ C0 PC0 = ~ C0 to
nd C0 = (1=2;1=2), and ~ C4 PC4 = ~ C4 to nd C4 = (1=3;2=3).
(b) For two of the three communication classes C, you are guaranteed that limm!1PmC exists.
So, nd limm!1PmC for any two of communication classes C for which this limit exists.
Solution: Since C2 is open, we have that
Also, since C4 is irreducible (closed), positive recurrent, and aperiodic we have limm!1PmC4
exists and
limm!1PmC4 =
1=3 2=3
1=3 2=
(c) Suppose that for some p 2 (0;1) we have ~ = (0;0;0;0;p;1 p) is the starting vector
for the process (Xn)1n=0 with transition matrix P. After the process has evolved for a
long time, approximately what is the probability that the process is in state 4? Please
give a brief justi cation for you answer. (We are assuming that the state space is ordered
S =f0;1;2;3;4;5g).
Solution: This starting vector has the process starting in the communication class C4,
which is closed. Therefore the process evolves as if its transition matrix is PC4. Therefore,
the long run distribution will be the invariant distribution for PC4, showing that the long
run probability that the process is in state 4 is 1=3.
4. Zombie attack! You nd refuge in the following house containing ve rooms.
At each move, you are equally likely to move to any adjacent room with a connecting door.
Let Xn represent the room you are in on your nth move and assume that the movements
(Xn)1n=0 create a stationary discrete time Markov chain with state space S = f1;2;3;4;5;6g.
Rooms 3;4 and 6 each contain a di erent zombie, labeled F, T, and W. Room 5 contains the
\Zombie-Be-Gone" spray (smells like salad { used to defeat zombies).
Page 6
(a) Starting from Room 1, what is the expected number of moves you make until reaching
the rst zombie? (Your answer may be in the form. such that solving for the inverse of a
matrix is the last step.)
Solution: Let A = f3;4;6g, the rooms with zombies. We want to nd E1[ A], the
expected number of moves until the rst hitting time of A. Note that E3[ A] = E4[ A] =
E6[ A] = 0.
E1[ A] = 1 + (1=2)E5[ A] + (1=2)E2[ A]
E2[ A] = 1 + (1=3)E3[ A] + (1=3)E5[ A] + (1=3)E1[ A]
E5[ A] = 1 + (1=4)E2[ A] + (1=4)E1[ A]
We can put this into matrix form. to get
18. Let fX0;X1;X2;:::g be independent and identically distributed random variables.
(a) Show that E[(Xi X0)2] = 2 Var(Xi) for every i 1. Hint: Expand the square (Xi X0)2.
Solution:
E[(Xi X0)2] = E[X2i 2XiX0 X20 ]
= E[X2i ] 2E[XiX0] E[X20 ] by linearity of exp. value
= E[X2i ] 2E[Xi]E[X0] E[X20 ] by indep. of Xi, Xj, for i6= j
= 2E[X2i ] 2E[Xi]2 by i.i.d. property where E[Xi] = E[X0]
= 2 Var(Xi)
(b) Suppose that N is another random variable taking values in the positive integers and
independent of the Xis. Use the Law of Total Expectation to show that
19. For the following situations, create a Markov chain, indicate the state space, and compute
the transitions probabilities/matrix. Be sure to show your work on computing the transition
probabilities/transition matrix.
(a) Patriotic Jar Game: Consider 3 jars: one red, one white, and one blue. The red jar
contains 1 red and 4 blue balls; the white jar contains 3 white, 2 red, and 2 blue balls; the
blue jar contains 4 white, 3 red, and 2 blue balls. At the initial stage, a ball is randomly
selected form. the red jar and then returned to that jar. At every subsequent stage, a ball
is randomly selected from the jar whose color is the same as that of the ball previously
selected and is then returned to that jar. Let Xn denote the state of the system after the
nth step.
Solution: Let (Xn)1n=0 be a SDTMC where Xn is the state of the system at time n.
That is, Xn is equal to Jar R (at the red jar), Jar W (at the white jar), or Jar B (at the
blue jar) at time n. Let the state space be represented as
S =fR;W;Bg
In Jar R, we have 1 red and 4 blue marbles for a total of 5 marbles. Thus, to stay in
Jar R, we must pick a red marble (prob. 1/5). To move to Jar W, we must pick a white
marble (prob. 0). To move to Jar B, we must pick a blue marble (prob. 4/5).
Continuing in this manner with the other jars, we have the following transition matrix:
(b) True/False Exam Patterns: In a True/False exam, the questions are arranged so that 3=4’s
Page 22
of the time a True answer is followed by a True, while 2=3’s of the time a False answer is
followed by a False.
Solution: Let Xn be the answer to question n. Then, (Xn)1n=0 is a SDTMC. Note that
S =fT;Fg; only true or false answers are allowed. Since a true answer is followed by a
true answer 3/4 of the time, pT;T = 3=4. Then, pT;F = 1=4. We know that pF;F = 2=3,
and so, pF;T = 1=3. The transition matrix is
P =3=4 1=41=3 2=3
(c) Interchangeable Marble Game: Suppose we have a box that contains M marbles; we have
X0 red marbles and M X0 are blue marbles. At each time step n, we ip a fair coin.
If heads appears, then a marble is chosen at random from the box and is replaced by a
blue marble; if tails appears, then a marble is chosen from the box and is replaced by a
red marble.
Solution: Let Xn be the number of red marbles in box at time n. Then, (Xn)1n=0 is a
SDTMC with state space S =f0;1;2;3;:::;Mg. Note that an any time, the next time
step will add one marble (Xn+1 = Xn + 1), subtract one marble from the current count
(Xn+1 = Xn 1), or keep the same number of red marbles (Xn+1 = Xn). Now, to nd
the probabilities of moving from state i to i+ 1.
State i to i+ 1:
We must add 1 red marble to the box by drawing a blue marble and replacing it with a
red.
State i to i 1:
We must lose 1 red marble to the box by drawing a red marble and replacing it with a