MelissaPena

PURDUE UNIVERSITY, IE 336

Midterm 2 (25 points + crib-sheet + on-time )

Wednesday, March 3, 2021

Starting time: 8pm (unless online student scheduled differently)

Duration: 1 hour and 40 minutes (unless accommodations scheduled)
Late submissions will imply -2 points per minute late

Midterm 2 must be submitted via Gradescope (it will not be graded otherwise)
Midterm 2 must include this page filled and signed (it will not be graded otherwise)

By taking this midterm, I acknowledge and commit to follow the following academic hon-
esty terms, under penalty of otherwise failing this course:

1 - I will not communicate with anyone during Midterm 2.

2 - I will not share the contents of Midterm 2 in anyway and with anyone.

3 - I will solely use the crib-sheet, a calculator, and an application/software to resolve powers
of matrices and/or sets of linear equations, blank pages if needed, and my knowledge to do
Midterm 2.

4 - All the contents will be written by myself (using a pen, pencil or virtual pencil).

Full Name Melissa Pena

PUID
0030514706
Signature
Yelissapenst
1
PURDUE UNIVERSITY, IE 336

Midterm 2 (25 points + crib-sheet + on-time )

Wednesday, March 3, 2021

Starting time: 8pm (unless online student scheduled differently)

Duration: 1 hour and 40 minutes (unless accommodations scheduled)
Late submissions will imply -2 points per minute late

Midterm 2 must be submitted via Gradescope (it will not be graded otherwise)
Midterm 2 must include this page filled and signed (it will not be graded otherwise)

By taking this midterm, I acknowledge and commit to follow the following academic hon-
esty terms, under penalty of otherwise failing this course:

1 - I will not communicate with anyone during Midterm 2.

2 - I will not share the contents of Midterm 2 in anyway and with anyone.

3 - I will solely use the crib-sheet, a calculator, and an application/software to resolve powers
of matrices and/or sets of linear equations, blank pages if needed, and my knowledge to do
Midterm 2.

4 - All the contents will be written by myself (using a pen, pencil or virtual pencil).

Full Name
MelissaPena
PUID
0030514706

Yeh.ssafZzt
Signature

1
A. T HEORY (10 P OINTS )
For questions in section Theory: no calculations or numerical solutions are needed.

Figure A.1: Diagrams of four different Markov chains

For each Markov chain shown above, identify if it is:

• terminating / non-terminating,

• ergodic,

• regular.

Briefly justify your responses.

(1) (1 Point) Markov chain 1 (See Figure A.1 top left)

ergodic allStatesreach allotherStates

nonterminating noabsorbingstate
Notregular Statesdonotreachthemselvesin anodd ofsteps

2
(2) (1 Point) Markov chain 2 (See Figure A.1 top right)

nonterminating noabsorbing states

NIergodic it is notpossibleto goto State ACallStatesmustreach allotherStates
NIregular notergodic notregular

(3) (1 Point) Markov chain 3 (See Figure A.1 bottom left)

ergodicallStatesreach allotherStates
nonterminating noabsorbingstate
regular there isatleastonestatethatcanreturnto itselfin 3odd steps

(4) (1 Point) Markov chain 4 (See Figure A.1 bottom right)

terminating hasabsorbingstate
cannotbeergodicorregularif terminating

(5) (2 Points) Explain the four possible interpretations of a steady-state probability, ºi , for
regular Markov chains.

1 Theprobability afterlongtimethattheprocess willbe instatei

2 timeaverageoftimespent instate i as processhasbeenoperatingforlong
periodof time
3 ensembleaverage proportionofsimultaneousidentical processes thatare in
state i afterlongtime
4 averagetimebetweenvisitstostatei
3
(6) (1 point) Consider an absorbing state i . What is the recurrence probability f i i ? Also,
obtain f i(1)
i
and f i(2)
i
for that same absorbing state. Justify your responses.

fii n
fiith
fit fii
m
fii 1 fii
Given the following transition probability matrix for a regular Markov Chain with three
states, answer questions 7,8,9. Note that since p i j are generic terms, the answers to ques-
tions 7,8, and 9 should be in terms of p i j where i , j = 1, 2, 3.

1 2 3
2 3
1 p 11 p 12 p 13
P= 2 4 p 21 p 22 p 23 5
3 p 31 p 32 p 33

(7) (1 Point) Using the matrix P defined in above, what is the expected number of visits of
state 3 in the first 4 epochs, considering that the process starts at state 3.

fz It pzztpzzlh

pzzldtpzzl4 EIND
(8) (1 Point) Using the matrix P defined in above, explain the meaning of mean sojourn time
and how to obtain it. Write down the mean sojourn time equation for each state.

j.pl ElNzftp.z E Ns itps3

sojourntime israndomvariableNithatcounts ofconsecutiveepochsthattheprocess
isin state i giventhatitstartsthere

4
(9) (1 Point) Using the matrix P defined in above, write down all the equations needed to
obtain the mean-first-passage-time between state 2 and 3: m 23 .

Miz It PiiMB Pl2m23

M23 ItP2M131P22m23

5
B. E XERCISES (15 P OINTS )
For questions in this section: final answers are expected to be numerical, hence including
not only the writing of the equations but also any needed calculations. On each exercise,
please pay attention to all the information provided.

B.1. QUALITY OF S ODA (6 P OINTS )

The quality of Soda varies from year to year depending on a combination of factors (includ-
ing quality of water, and carbonation procedures). Some of these factors are predictable and
some others are not. From historical data extending over last years, we obtained the follow-
ing count matrix

Previous Year
Current Year
Poor Fair Excellent
Poor 3 6 0
Fair 6 12 2
Excellent 3 2 0

Table B.1: Count matrix with historical data for quality of soda

Answer the following.

(1) (1 Point) Obtain the one-step transition probability matrix for the quality of soda.

tf Tf
transposed
fitof
p
f
fools
if O l O

(2) (1 Point) Write down all the steady state equations needed to obtain the steady-state con-
figuration for this Markov Chain.

Ti OIbIT t 0.3112
The ObIT t0.6112 t113 6
113 0 IbIT t 0 I112
Ti tThtTiz I
(3) (0.5 Points) Out of 2,000 bottles sampled randomly from many years, what is the expected
number that would be Fair? Do not provide a numerical solution, instead express the an-
swer in terms of steady state variable(s).

2,00011T expected of fair bottles

(4) (1 Point) If this year was a "Poor" quality year, how many of the next four years (including
current year) can be expected to be "Fair" or "Excellent"?

P F E
epitope 3.03
p F z5f of
Pff
fpp4 ppptppfhipppe31ippr.tw E O I
0.5 0.67510.62410.62
2.422
141
fpt ppptppehippec31ippp.tw
0.25 0.112510.12 0.12
0.6085

(5) (1 Point) If this year is a "Fair" quality year, what is the expected number of years until the
next "Excellent" year?

Mas P F E
p
MB I Plimbtphpzz f
p p z5f go.it
M3 ltP21M13tP22Pz3 E O l O

Mis I 10.15M1310.5P23 7
M251 10.3M13 0.6P23

Ml3 6 Mz3 7
(6) (1 Point) If this year was "Poor" quality and it turns out that next year is "Fair", what is the
probability that the following year will be "Excellent"?

PFE O

(7) (0.5 Points) What is the mean number of years between occurrences of "Poor" quality
years?

Mii TT at 4years

8
B.2. F LIPPING C OIN P ROBLEM (4 P OINTS )
We play a flipping coin game with an unfair coin. Head (H) and Tail (T) occur with P (H ) =
1/3 and P (T ) = 2/3, respectively. The game stops when either two heads or two tails appear
consecutively. While writing this problem, we found a note with the following "mysterious
matrix", that we are providing just in case it helps:

0 H T
2 3
0 1 0.71 1.14
E= H 4 0 1.29 0.86 5
T 0 0.43 1.29

(1) Draw the transition diagram and write down the one-step transition probability matrix for
this problem (1 point)

O H T HH TT
13 213 213 o O 13 213
pm 2 3
H T AHLY
t 88
HH O O O l O
31
13 TT O 0 O O I

(2) What is the probability that, starting a new game, the game will stop by obtaining two
tails? (1.5 Points)

A ERO H T HHTT
a

HH
ii
TT
Hf
A
it s
H
probability ofending in't 0.76
9
(3) When starting a new game, what is the expected number of flips until the game stops? (1.5
Points)

O H T
HO O 113 213
Q 143
t gg

Iib
e a a too
is
I t0.71 t l14 2.85flips

10
B.3. T HE B EAUTY OF R EGULAR M ARKOV C HAINS (5 P OINTS )
Given the following one-step transition probability matrix of a regular Markov chain P:

A B C D
2 3
A 1/4 1/2 1/4 0
B
6 0 0 1/2 1/2 7
6 7
P= 6 7
C 4 2/3 1/6 1/6 0 5
D 1/4 0 0 3/4
and the following n-step matrices, obtained from P:

A B C D
2 3
A 0.23 0.17 0.35 0.25
B
6 0.46 0.09 0.08 0.37 7
6 7
P(2) = 6 7
C 4 0.28 0.36 0.28 0.08 5
D 0.25 0.13 0.06 0.56

A B C D
2 3
A 0.36 0.17 0.20 0.27
B
6 0.26 0.24 0.17 0.33 7
6 7
P(3) = 6 7
C 4 0.28 0.19 0.30 0.23 5
D 0.24 0.14 0.14 0.48

A B C D
2 3
A 0.29 0.17 0.19 0.35
B
6 0.29 0.17 0.19 0.35 7
6 7
P(50) = 6 7
C 4 0.29 0.17 0.19 0.35 5
D 0.29 0.17 0.19 0.35
(1) (1 Point) What is the probability of going from state A to state C in 3 steps?

PAC131 0.2

A (2) (1 Point) What is the probability of going from state C to D and return directly to C again?

PcpPoo 0.350.19
0.0665

11
(3) (1 Point) Obtain the steady state probabilities for all the states {A, B,C , D}.

IT Tip

lift 4

(4) (1 Point) What is the mean number of steps between occurrences of state D?

MDD 3 7.29Steps

(5) (1 Point) Obtain P(55) . Justify your answer.

Fn the
nfoie's's father'efonresidifFdananimaggtimethoat

p Bfg
c
D 1 processhas reached a steadystatesowe
know 150 155 and
that p p so on

12
MM
Elissa's bribesheet
WalkProbabability KojiPim Pjnijn product ofonesteptransition probabilities
transitionProbability PExn ilXo i nsteptransitionprobability distinctwalksaremutuallyexclusive
pl is 2steptransition matrix
pinkpn nsteptransitionmatrix onesteptransitionmatrixraisedtonthpower

stateprobabilities Pim unconditionalprobabilitythatprocess

is instate j atepochn
i
pjinkp Xn j
Expected ofvisits Gj'm expected oftimes a state i isvisited in1st n epochs where i is
M piilo'tPijl t
fijiIN pi int where it j initialstate
ofjj lol
It Pjj Pjj l t t In
Pjj Where j j
sojourntime random variable Nithat countsthe of consecutiveepochsthattheprocessisin
state i giventhat itstartsthere
ElNi I
l Pii
firstpassagetime fromstate i to j probabilitythatprocessreachesstate j for1sttime in nepochs
fijiM piint IIfig Pjj n k When recurrence isassured
fX f d
1214 p214 f plz f p
Y 2212 ff put
Returnprobabilities fii FEfilm recurrenceprobabilityfor
state i isprobabilitythat i isevervisited
againgivenprocessstartsthere

GlassesofMarkovchain

terminating absorbing chainseventuallyend atleastoneabsorbingstate

Ergodic possibletogofromentrystatetoeverystate

regular itsomepowerofthe transition matrixhasonlypositiveelements NOZeros

forsome n its possibletogofromeverystatetoeverystate
FindOne Odd loop
mmmmunnmnnny
everyregularchainis ergodicbutnoteveryergodic chain is regular noergodic no
With regular

Steadystateprobabilities TI TIP limitValves

Ti
P Placevalves in systemof equationby columnsnotrows
Iz timeaverage mean proportion oftimespentinstateasprocesshasoperated
forlongtime
ensembleaverage runmanyidentical processes
averagetimebetweenvisitstostatei
Meanfirstpassage time timefromstate i to j ti ti is expected valveof firstpassagetime
Mij I PikMKj
My a PF I Pj jthcolumn replacedbyZeros
meanrecurrencetime expectationofrandomvariable Nii
Mii It kEtiPiKMki
Mii Thissteadystateprobabilityvector

TerminatingMarkovchain onlyconsists oftransientsabsorbingStates

absorbingstate pj I canonlygotoitself
transientstate recurrence probability islessthan1 statewhichleadstoabsorbingstate

P flag Q setw alltransientStates

f R setw allabsorbingStates
0 zeroentries
1 identitymatrix

Expected ofvisits mean oftimes atransientstate i is visitedstartingat i let is

E CI QI expectation of oftimesthat j isvisitedpriortoterminationbyabsorbingstate
expectedduration ofterminatingprocess expected Of
transitionsuntil thefirstvisitto any
k absorbing state
di lik
d El
absorbingprobability probabilityabsorbingStato j isevervisited an
A ER Aij Pij1k PikaKj
A Caindenotates probabilitythattransientstate i isabsorbed in theabsorbingstatej
hitprobability probabilitytransientstate j isevervisited F
fij Pijt 8 PikfKj
transient

fi CI QI 9j Q jthcolumn replacedbyZeros