# Monte Carlo Methods in Scientific Computing

6. 6. Markov Markov Chain Chain State Space The state space is the set of values a random variable X can take. E.g.: integer 1 to 6 in a dice experiment, or the locations of a random walker, or the coordinates of set of molecules, or spin configurations of the Ising model. Markov Process

A stochastic process is a sequence of random variables X0, X1, , Xn, The process is characterized by the joint probability distribution P(X0, X1, ) If P(Xn+1|X0, X1,, Xn) = P(Xn+1|Xn) then it is a Markov process. Markov Chain A Markov chain is completely characterized by an initial probability distribution P0(X0), and the transition matrix W(Xn->Xn+1) = P(Xn+1|Xn). Thus, the probability that a sequence of X0=a, X1=b, , Xn= n appears, is

P0(a)W(a->b)W(b->c) W(..->n). Properties of Transition Matrix Since W(x->y) = P(y|x) is a conditional probability, we must have W(x->y) 0. Probability of going anywhere is 1, so y W(x -> Y) = 1. Evolution Given the current distribution, Pn(X), the distribution at the next step, n +1, is obtained from

Pn+1(Y) = x Pn(X) W( X -> Y) In matrix form, this is Pn+1 = Pn W. Chapman-Kolmogorov Equation We note that the conditional probability of state after k step is P(Xk=b|X0=a) = [Wk]ab. We have P(X k s | X 0 ) P(X k s | X s )P(X s | X 0 ) Xs which, in matrix notation, is Wk+s=Wk Ws.

Probability Distribution of States at Step n Given the probability distribution P0 initially at n = 0, the distribution at step n is Pn = P0 Wn (n-th matrix power of W) Example: Random Walker A drinking walker walks in discrete steps. In each step, he has probability

walk to the right, and probability to the left. He doesnt remember his previous steps. The Questions Under what conditions Pn(X) is independent of time (or step) n and initial condition P0? And approaches a limit P(X)? Given W(X->X), compute P(X) Given P(X), how to construct W(X>X) ? Some Definitions:

Recurrence and Transience A state i is recurrent if we visit it infinite number of times when n -> . P(Xn = i for infinitely many n) = 1. For a transient state j, we visit it only a finite number of times as n -> . Irreducible From any state I and any other state J, there is a nonzero probability that one can go from I to J after some n steps. I.e., [Wn]IJ > 0, for some n.

Absorbing State A state, once it is there, can not move to anywhere else. Closed subset: once it is in the set, there is no escape from the set. Example 1 2 0 W 0

0 1 2 0 1 2 0 0 0 1

2 0 1 0 1 1 1 4

4 4 0 0 0 1

0 0 1 4 1 2 1 2

2 1/4 1/2 1/2 1/2 1/4 4 5 {1,5} is closed, {3} is

closed/absorbing. It is not irreducible. 1/4 3 Aperiodic State A state I is called aperiodic if [Wn]II > 0 for all sufficiently large n. This means that probability for state I to go back to I after n step for all n > nmax is nonzero. Invariant or Equilibrium

Distribution If P(y )W(y x ) P(x ) y we say that the probability distribution P(x) is invariant with respect to the transition matrix W(x->x ). Convergence to Equilibrium Let W be irreducible and aperiodic, and suppose that W has an invariant

distribution p. Then for any initial distribution, P(Xn=j) -> pj, as n -> for all j. This theorem tell us when do we expect a unique limiting distribution. Limit Distribution One also has n lim[W ] ij pj n independent of the initial state i,

such that P = P W, [P]j = pj. Condition for Approaching Equilibrium The irreducible and aperiodic condition can be combined to mean: For all state j and k, [Wn]jk > 0 for sufficiently large n. This is also referred to as ergodic. Urn Example There are two urns. Urn A has two balls, urn B has three balls. One draws a ball in

each and switches them. There are two white balls, and three red balls. What are the states, the transition matrix W, and the equilibrium distribution P? The Transition Matrix 1 1 0 0 W 1/ 6 1/ 2 1/ 3

0 2/ 3 1/ 3 3 1 1/3 2/3 1/6 2 Note that elements of W2 are all positive.

1/ 2 1/ 3 1/ 6 W 2 1/ 12 23/ 36 5/ 18 1/ 9 5/ 9 1/ 3

Eigenvalue Problem Determine P is an eigenvalue problem: P=PW The solution is P1 = 1/10, P2 = 6/10, P3 = 3/10. What is the physical meaning of the above numbers? Convergence to Equilibrium Distribution Let P0 = (1, 0, 0) P1 = P0 W = (0, 1, 0) P2 = P1 W = P0 W2 = (1/6,1/2,1/3)

P3 = P2 W = P0 W3 = (1/12,23/36,5/18) P4 = P3 W = P0 W4 = (0.106,0.587,0.3) P5 = P4 W = P0 W5 = (0.1007, 0.5986, 0.3007 ... P0 W = (0.1, 0.6, 0.3) Time Reversal Suppose X0, X1, , XN is a Markov chain with (irreducible) transition matrix W(X->X) and an equilibrium distribution P(X), what transition probability would result in a time-reversed process Y0 = XN, Y1=XN-1, YN=X0?

Answer The new WR should be such that P(x) WR(x->x) = P(x)W(x->x) Original process P(x0,x1,..,xN) = P(x0) W(x0->x1) W(x1>x2) W(xN-1->xN) must be equal to reversed process P(xN,xN-1,,x0) = P(XN) WR(XN->XN-1) WR(xN-1->XN-2) WR(x1->x0). The equation (*) satisfies this. (*) Reversible Markov Chain A Markov chain is said reversible if

it satisfies detailed balance: P(X) W(X -> Y) = P(Y) W(Y ->X) Nearly all the Markov chains used in Monte Carlo method satisfy this condition by construction. An example of a chain that does not satisfy detailed balance 0 2/ 3 1/ 3 W 1/ 3 0 2/ 3 2/ 3 1/ 3

0 Equilibrium distribution is 1 2/3 1/3 3 1/3 1/3

2/3 P=(1/3,1/3,1/3). The reverse chain has transition matrix WR = WT (transpose of W). WR W. 2/3 2 Realization of Samples in Monte Carlo and Markov Chain Theory A Monte Carlo sampling do not deal with probability P(X) directly, rather

the samples, when considered over many realizations, following that distribution. Monte Carlo generates next sample y from the current x, using the transition probability W(x -> y).

## Recently Viewed Presentations

• Florida International University CGS 3300 Introduction to Information Systems How does an email travel down the data lines? 56 Kbps V.90 modem DSL Cable modem ISDN T1/T3 Wireless connection Email travels by V.90 Modem Email travels by V.90 Modem What...
• V. UK Legislation. The United Kingdom of Great Britain and . Northern Ireland consists of 4 countries . forming 3 distinct jurisdictions, being . England and Wales; Scotland and
• Varying cone angle and tip diameter in chemical etch of single mode tapered optical fibers Jenny Yu, Dr. Keith Roper, Department of Bioengineering, 2007
• Template for a standard presentation without a specific subject ... (Internet Science and Engineering) Programme, CSA, IISc Softcore for the M.E. (Systems Science and Automation) Programme offered jointly by CSA and EE, IISc Softcore for the MBA Programme offered by...
• Beyond virtualization. Scale and secure workloads, cost-effectively build a privatecloud, and securely connect to cloud services. Every app, any cloud. Build on an open and scalable web platform that supports applications across premises. Modern workstyle, enabled. Support a mobile and...
• Do the higher levels-- Hard Law/Soft Law Some forms of international law: General approaches to the relationship between domestic and international law Ways in which international agreements can find their way into domestic law If an international norm isn't "hard"...
• What steps do you have to remember to take when using a Bunsen burner? The temperature and colour of the flame can be adjusted by opening or closing the adjustable air hole. The safety flame is a yellow flame (air...
• People are not permitted to divorce until they reach a property settlement. Divorce - often straightforward. Property Settlement + Parenting Arrangements - often complicated. Parenting Arrangement. JOINT & EQUAL responsibility until the Family Court makes an order. Couples must partake...