MATH 56A: STOCHASTIC PROCESSESCHAPTER 77. ReversalThis chapter talks about time reversal. A Markov process is a stateXtwhich changes with time. If we run time backwards what does itlook like?7.1. Basic equation. There is one point which is obvious. As timeprogresses, we know that a Markov process will converge to equilibrium.If we reverse time then it will tend to go away from the equilibrium(contrary to what we expect) unless we start in equilibrium. If a processis in equilibrium, it will stay in equilibrium (fluctuating between thevarious individual states which make up the equilibrium). When werun the film backwards, it will fluctuate between the same states. So,we get a theorem:Theorem 7.1. A Markov process with equilibrium distribution π re-mains a Markov process (with the same equilibrium) when time is re-versed provided that(1) left limits are replaced by right limits,(2) the process is irreducible(3) and nonexplosive.The time revered process has a different transition matrix!P = Π−1PtΠwhere P = (p(x, y)) is the transition matrix for the original processandΠ =π(1) 0 · · ·0 π(2) · · ·0 0 · · ·is the diagonal matrix with diagonal entries π(1), π(2), · · · given by theequilibrium distribution. In other words,ˆp(x, y) = π(x)−1p(y, x)π(y)orπ(x)ˆp(x, y) = π(y)p(y, x)Date: December 14, 2006.12 MATH 56A: STOCHASTIC PROCESSES CHAPTER 7This makes sense because π(y)p(y, x) is the equilibrium probabilitythat a random particle will start at y and then go to x. When we runthe film backwards we will see that particle starting at x and movingto y. So, the probability of that is π(x)ˆp(x, y)x•p(y,x)←−−− •π(y)yx•π(x)ˆp(x,y)−−−→ •y7.1.1. Example 1. Take the continuous Markov chain with infinitesmalgeneratorA =−2 2 00 −4 41 1 −2The row are required to have sum zero and terms off the diagonal mustbe nonnegative. The equilibrium distribution (satisfying πA = 0) isπ = (1/4, 1/4, 1/2)So, the time reversed process is!A = Π−1AtΠ =442−2 0 12 −4 10 4 −21/41/41/2!A =−2 0 22 −4 20 2 −27.2. Reversible process.Definition 7.2. A Markov process is called reversible if!P = P . Thisis the same as!A = A. We say it is reversible with respect to a measureπ ifπ(x)p(x, y) = π(y)p(y, x)Example 1 is not a reversible process becauseˆA $= A.Theorem 7.3. If a Markov chain is reversible wrt a measure π then(1) If&π(k) < ∞ thenλ(j) =π(j)&π(k)is the (unique) invariant probability distribution.(2) If&π(k) = ∞ then the process is not positive recurrent.MATH 56A: STOCHASTIC PROCESSES CHAPTER 7 37.2.1. example 2. Take the random walk on S = {0, 1, 2, · · · } where theprobability of going right is p. I.e., p(k, k + 1) = p, p(k + 1, k) = 1 − p.(1) Show that this is a reversible process.(2) Find the measure π(3) What is the invariant distribution λ?To answer the first two questions we have to solve the equation:π(k)p(k, k + 1) = π(k + 1)p(k + 1, k)or:π(k + 1) =p1 − pπ(k)This has an obvious solution:π(k) ='p1 − p(kTherefore, the random walk is reversible.Now we want to find the invariant distribution λ.If p < 1/2 then∞)k=0π(k) =1 − p1 − 2pSo, the equilibrium distribution isλ(k) =pk(1 − 2p(1 − p)k+1If p ≥ 1/2 then∞)k=0π(k) = ∞since the terms don’t go to zero. So the process is not positive recurrentand there is no equilibrium.7.3. Symmetric process.Definition 7.4. A Markov chain is called symmetric if p(x, y) =p(y, x). This implies reversible with respect to the uniform measure:π(x) = 1 for all x and the process is positive recurrent if and only ifthere are finitely many states.I talked about one example which is related to the final exam. It isexample 3 on page 160: Here S is the set of all N-tuples (a1, a2, · · · , aN)where ai= 0, 1 and the infinitesimal generator isα(a, b) =*1 if a, b differ in exactly one coordinate0 otherwise4 MATH 56A: STOCHASTIC PROCESSES CHAPTER 7This is symmetric: α(a, b) = α(b, a).We want to find the second largest eigenvalue2of A. (The largest eigenvalue is λ1= 0. The second largest is negativewith minimal absolute value.) The eigenvectors of A are also eigenvec-tors of P = eAwith eigenvalue eλ, the largest being e0= 1 and thesecond largest being eλ2< 1.The first thing I said was that these eigenvectors are π-orthogonal.Definition 7.5.'v, w(π:=)x∈Sv(x)w(x)π(x)When π(x) = 1 (as is the case in this example) this is just the dotproduct. v, w are called π-orthogonal if'v, w(π= 0According to the book the eigenvalues of A areλj= −2j/Nfor j = 0, 1, 2, · · · , N. This implies that the distance from Xtto theequilibrium distribution decreases at the rate of −2/N on the average:E(||Xt− π||) ≤ e−2t/N||X0− π||7.4. Statistical mechanics. I was trying to explain the Gibbs poten-tial in class and I gave you a crash course in statistical mechanics.The fundamental assumption is that All states are equally likely.Suppose that we have two systems A, B with energy E1, E2. SupposethatΩA(E1) = #states of A with energy E1ΩB(E2) = #states of B with energy E2ThenΩA(E1)ΩB(E2) = #states of (A, B) with energy E1for A, E2for BSuppose that the two systems can exchange energy. Then they willexchange energy until the number of states is maximal. This is thesame as when the log of the number of states is maximal:ln ΩA(E1+ ∆E) + ln ΩB(E2− ∆E) = 0or:∂∂E1ln ΩA(E1) =∂∂E2ln ΩB(E2) = β (constant)MATH 56A: STOCHASTIC PROCESSES CHAPTER 7 5Define the entropy of the system A to be S(E) = ln ΩA(E). In equi-librium we have to have∂∂ES(E) = βWe think of B as an infinite reservoir whose temperature will notchange if we take energy out.Every state has equal probability. But, a state x of A with energyE(x) cannot exist without taking E(x) out of the environment B. Thenthe number of states of the environment decreases by a factor of e−βE(x).Therefore, the probability of the state is proportional to e−βE(x). So,the probability of state x isP(x) =e−βE(x)&y∈Se−βE(y)The denominator is the partition functionZ(β) =)y∈Se−βE(y)We looked at the Ising model in which there are points in a latticeand a state x is given by putting a sign &i(x) = ±1 at each lattice pointi and the energy of the state x is given byE(x) =)i−j|&i(x) − &j(x)| · H(This is 2H times the number of adjacent lattice point i, j so thatthe signs &i(x), &j(x) are different.) Then I tried to