Problems in Markov chains - ku

1 Problems inMarkov chainsDepartment of Mathematical SciencesUniversity of CopenhagenApril 2008 This collection of Problems was compiled for the course Statistik 1B. It con-tains the Problems in Martin Jacobsen and Niels Keiding: Markovk der(KUIMS 1990), and 1990 Torben MartinussenJan W. NielsenJesper MadsenIn this edition a few misprints have been correctedSeptember 1992S ren Feodor NielsenIn this edition a few misprints have been correctedSeptember 1993 Anders BrixTranslated into English. A number of additional Problems have been 2007 Merete Grove JacobsenS ren Feodor NielsenMisprints corrected and additional Problems 2008S ren Feodor Nielsen21. Conditional independenceProblem that there are functions (of sets)fzandgzsuch thatfor all setsAandBwe haveP{X A, Y B|Z=z}=fz(A)gz(B)for everyz.

2 Show thatXandYare conditionally independent the result of the previous problem to show, or showdirectly, that ifP{X=x, Y=y, Z=z}=f(x, z) g(y, z)for some functionsfandgthenXandYare conditionally independent thatXandYare conditionally independent givenZifand only ifP{X A|Y=y, Z=z}=P{X A|Z=z}for every (measurable) setAand ((Y, Z)(P)-almost) every (y, z).Thus ifXandYare conditionally independent givenZ, thenXis inde-pendent thatX,YandZare independent random that(a)XandYare conditionally independent givenZ(b)XandX+Y+Zare conditionally independent givenX+YProblem ,U1andU2be independent random variables and letF:R2 Rbe a measurable function. PutXn=F(Xn 1, Un)n= 1,2 Show thatX0andX2are conditionally independent givenX1. MayFdependonn?

3 problem thatXis independent ofYandXis conditionally3independent ofZgivenY, show thatXis independent of (Y, Z). (Recallthat independence ofXandYand ofXandZdoes not ensure independenceofXand(Y, Z)) problem that the probability mass function of (X, Y, Z) isstrictly positive.(a) Show that ifXandYare conditionally independent givenZandXandZare conditionally independent givenYthenXis independent of(Y, Z).(b) Show that the result in question (a) is not necessarily correct withoutthe assumption on the probability mass function (consider the casewhereX=Y=Zis non-degenerate). problem (Xi)i Ibe a (at most countable) collection of randomvariables. Make agraphby writing down all the random variablesXiandconnectingXiandXjif and only if the conditional distribution ofXigiven(Xk)k I\{i}depends onXj.

4 (The correct mathematical way of saying this isthat there should be an edge (a connection) betweenXiandXjunlessP{Xi A|Xk=xk, k I\{i}}may be chosen so that is does not dependxjfor anyA.)The resulting graph is called theconditional independence graph. TheXisare called theverticesand the connections between two vertices are calledthe edges. If we can go fromXitoXjby following a sequence of edges,we say there is apathbetweenXiandXj.(a) Show that this is well-defined, that if the conditional distribution ofXigiven (Xk)k I\{i}depends onXj, then the conditional distributionofXjgiven (Xk)k I\{j}depends onXi.(b) Sketch the conditional independence graph for a Markov chain.(c) Show that if there is no edge betweenXiandXjthen they are condi-tionally independent given the rest.

5 (d) Define the neighbours ofXito be the variables that are connected toXiby an edge. LetNci={j I\{i}:Xjis not a neighbour ofXi}Show thatXiare conditionally independent of (Xj)j Ncigiven theneighbours ofXi4A conditional independence graph1234In the graph above, the variables marked 1 and 2 are conditionally indepen-dent given the rest, and given the variable marked 3, the variable marked 2is independent of the rest (3 is the only neighbour of 2).We would like to have the following result:LetI1, I2andI3be disjointsubsets ofIand suppose that every path form a variable inI1to a variableinI2passes throughI3, then(Xi)i I1and(Xi)i I2are conditionally inde-pendent given(Xi)i I3.(IfI3= then read independent for conditionallyindependent). For instance, this would imply that 1 and 2 areconditionallyindependent given 3 and that 2 and 4 are independent.

6 This is true underadditional assumptions, for instance if (Xi)i Ihas a strictly positive jointdensity wrt a product independence graphs are important in a class ofstatisticalmodels known asgraphical Discrete time homogeneous Markov (Random Walks). LetY0, Y1, ..be a sequence of independent,identically distributed random variables onZ. LetXn=nXj=0 Yjn= 0,1, ..Show that{Xn}n 0is a homogeneous Markov , Y1, ..be a sequence of independent, identically dis-tributed random variables onN0. LetX0=Y0andXn=(Xn 1 YnifXn 1>0Xn 1+YnifXn 1 0n= 0,1, ..Show that{Xn}n 0is a homogeneous Markov (Branching processes). LetUi,j, i= 0,1, .. , j= 1,2, ..bea sequence of independent, identically distributed randomvariables onN0,and letX0be a random variable independent of theUi,js.)

7 LetXn= Xn 1Xj=1Un 1,jifXn 1>00ifXn 1= 0n= 1,2, ..Show that{Xn}n 0is a homogeneous Markov {Xn}n 0be a homogeneous Markov chain with count-able state spaceSand transition probabilitiespij, i, j S. LetNbe arandom variable independent of{Xn}n 0with values inN0. LetNn=N+nYn= (Xn, Nn)for alln N0.(a) Show that{Yn}n 0is a homogeneous Markov chain, and determine thetransition (b) Instead of assuming thatNis independent of{Xn}n 0, it is now onlyassumed thatNis conditional independent of{Xn}n ((X1, .. , Xn) = (i1, .. , in), N=j|X0=i0)=P((X1, .. , Xn) = (i1, .. , in)|X0=i0) P(N0=j|X0=i0)for alli1, .. , in S, n N, j N0, and alli0 SwithP(X0=i0)> that{Yn}n 0is a homogeneous Markov chain and determine thetransition {Xn}n 0be a stochastic process on a countable state spaceS.

8 Suppose that there exists ak N0such thatP(Xn=j|X1=i1, .. , Xn 1=in 1)=P(Xn=j|Xn k=in k, .. , Xn 1=in 1)for alln kand alli0, .. , in 1, j Sfor whichP(X0=i0, .. , Xn 1=in 1)>0 Such a process is called ak-dependent chain. The theory for these processescan be handled within the theory for Markov chains by the following con-struction:LetYn= (Xn, .. , Xn+k 1)n {Yn}n 0is a stochastic process with countable state spaceSk, some -times refered to as thesnake chain. Show that{Yn}n 0is a homogeneousMarkov urn holdsbblack andrred marbles,b, r N. Con-sider the experiment of successively drawing one marble at random from theurn and replacing it withc+1 marbles of the same colour,c N. Define thestochastic process{Xn}n 1byXn=(1 if then th marble drawn is black0 if then th marble drawn is redn= 1,2.)

9 Show that{Xn}n 1is not a homogeneous Markov , Y1, ..be a sequence of independent, identically dis-tributed random variables onZsuch thatP(Yn= 1) =P(Yn= 1) = 1/2n= 0,1, ..Consider the stochastic process{Xn}n 0given byXn=Yn+Yn+12n= 0,1, ..(a) Find the transition probabilitiespjk(m, n) =P(Xn=k|Xm=j)form < nandj, k= 1,0,1.(b) Show that the Chapman-Kolmogorov equations are not satisfied, andthat consequently{Xn}n 0is not a homogeneous Markov Transient and recurrent a series of transition matrices for homogeneous Markovchains is given. Draw (or sketch) the transition graphs and examine whetherthe chains are irreducible. Classify the states.(a) 1 0 00 1 01/3 1/3 1/3 (b) 0 1/2 1/21 0 01 0 0 (c) 0 1 00 0 11/2 1/2 0 (d) 1 0 00 1/2 1/20 1/2 1/2 (e) 1/2 0 1/2 0 01/3 1/3 1/3 0 01/2 0 1/2 0 00 0 0 1/2 1/20 0 0 1/2 1/2 (f) 0 1/2 1/2 0 0 00 0 0 1/3 1/3 1/30 0 0 1/3 1/3 1/31 0 0 0 0 00 0 0 0 1 00 0 0 0 1/2 1/2 9(g) 100 0 1 pp0 0 0 1 pp0 00 1 p p.

10 (h) 1 p0p0 0 1 p0 0p0 1 p0 0 0p .. problem there be givenrempty urns,r N, and consider a se-quence of independent trials, each consisting of placing a marble in an urnchosen at random. LetXnbe the number of empty urns afterntrials,n that{Xn}n 1is a homogeneous Markov chain, find the transition ma-trix and classify the a homogeneous Markov chain with state spaceN0and transition probabilitiespij, i, j N0given bypij= 1i=j= 0p i=j >0q i j= 10 otherwisewherep+q= 1, p, q >0. Findf(n)j0=Pj{T0=n}forj N, and show thatEj(T0) =jq, whereT0is the first return time to state (Random Walks). LetY0, Y1, ..be a sequence of indepen-dent, identically distributed random variables onZ. LetXn=nXj=0 Yjn= 0,1, ..and letpij, i, j, Zbe the transition probabilities for the Markov chain{Xn}n 0.