Transcript presentation source

1
CE 530 Molecular Simulation
Lecture 8
Markov Processes
David A. Kofke
Department of Chemical Engineering
SUNY Buffalo
[email protected]
Monte Carlo Integration: Review
 Stochastic evaluation of integrals
• sum integrand evaluated at randomly generated points
• most appropriate for high-dimensional integrals
error vanishes more quickly (1/n1/2)
better suited for complex-shaped domains of integration
 Monte Carlo simulation
• Monte Carlo integration for ensemble averages
U 
 Importance Sampling
•
•
•
•
1
N!
 dr
N
N e  U ( r
U (r ) Z
N
N)
p(rN)
emphasizes sampling in domain where integrand is largest
it is easy to generate points according to a simple distribution
stat mech p distributions are too complex for direct sampling
need an approach to generate random multidimensional points
according to a complex probability distribution
f
• then integral is given by I  p p
2
3
Markov Processes
 Stochastic process
• movement through a series of well-defined states in a way that
involves some element of randomness
• for our purposes,“states” are microstates in the governing
ensemble
 Markov process
• stochastic process that has no memory
• selection of next state depends only on current state, and not on
prior states
• process is fully defined by a set of transition probabilities pij
pij = probability of selecting state j next, given that presently in state i.
Transition-probability matrix P collects all pij
4
Transition-Probability Matrix
 Example
If in state 1, will stay in state 1
with probability 0.1
• system with three states
 p 11 p 12 p 13   0.1 0.5 0.4 
P   p 21 p 22 p 23    0.9 0.1 0.0 

 

p



 31 p 32 p 33   0.3 0.3 0.4 
If in state 1, will move to state 3
with probability 0.4
Never go to state 3 from state 2
 Requirements of transition-probability matrix
• all probabilities non-negative, and no greater than unity
• sum of each row is unity
• probability of staying in present state may be non-zero
5
Distribution of State Occupancies
 Consider process of repeatedly moving from one state to the
next, choosing each subsequent state according to P
• 1 2  2  1  3  2  2  3  3  1  2  3  etc.
 Histogram the occupancy number for each state
• n1 = 3
• n2 = 5
• n3 = 4
p1 = 0.33
p2 = 0.42
p3 = 0.25
1 2 3
 After very many steps, a limiting distribution emerges
 Click here for an applet that demonstrates a Markov process
and its approach to a limiting distribution
6
The Limiting Distribution 1.
 Consider the product of P with itself
 p 11 p 12 p 13   p 11 p 12 p 13 
All ways of going from state
P 2   p 21 p 22 p 23    p 21 p 22 p 23 

 

1 to state 2 in two steps
p
 p

p
p
p
p
 31
32
33   31
32
33 
 p 11p 11  p 12p 21  p 13p 31 p 11p 12  p 12p 22  p 13p 32 etc. 
  p 21p 11  p 22p 21  p 23p 31 p 21p 12  p 22p 22  p 23p 32 etc. 


p p  p p  p p

 31 11
32 21
33 31 p 31p 12  p 32p 22  p 33p 32 etc. 
Probability of going from
state 3 to state 2 in two steps
 In general Pn is the n-step transition probability matrix
• probabilities of going from state i to j in exactly n steps
( n)
( n)
( n) 
 p 11
p 12
p 13


( n)
( n)
( n)
n
P   p 21 p 22 p 23  defines p ( n )
ij
 ( n)

( n)
( n) 
 p 31 p 32
p
33


7
The Limiting Distribution 2.
 Define p i(0) as a unit state vector
p1(0)  1 0 0  p 2(0)   0 1 0  p 3(0)   0 0 1
 Then p i(n)  p i(0)P n is a vector of probabilities for ending at
each state after n steps if beginning at state i
p 1( n)
( n)
( n)
( n) 
 p 11
p12
p13


(0) n
( n)
( n)
( n)
( n)
( n)
( n)
 p 1 P  1 0 0   p 21 p 22 p 23   p 11
p 12
p 13
 ( n)
( n)
( n) 
 p 31 p 32

p
33 


 The limiting distribution corresponds to n  
()
()
()
• independent of initial state p1  p 2  p 3  p

8
The Limiting Distribution 3.
 Stationary property of p
p  lim p i(0)P n 
n 


 lim p i(0)P n 1  P

n  
 pP
 p is a left eigenvector of P with unit eigenvalue
• such an eigenvector is guaranteed to exist for matrices with rows
that each sum to unity
 Equation for elements of limiting distribution p
p i  p jp ji
j
 0.1 0.5 0.4 
e.g. P   0.9 0.1 0.0 


 0.3 0.3 0.4 


not independent
p1  0.1p1  0.9p 2  0.3p 3
p 2  0.5p1  .1p 2  0.3p 3
p 3  0.4p1  0.0p 2  0.4p 3
p1  p 2  p 3  p1  p 2  p 3
9
Detailed Balance
 Eigenvector equation for limiting distribution
• p i  p jp ji
j
 A sufficient (but not necessary) condition for solution is
• p ip ij  p jp ji
• “detailed balance” or “microscopic reversibility”
 Thus
• p i   p jp ji
j
  p ip ij
j
 p i  p ij  p i
j
 0.1
P   0.9

 0.3
0.5
0.1
0.3
0.4 
0.0 

0.4 
For a given P, it is not always
possible to satisfy detailed
balance; e.g. for this P
p 3p 32  p 2p 23
zero
10
Deriving Transition Probabilities
 Turn problem around...
 …given a desired p, what transition probabilities will yield
this as a limiting distribution?
 Construct transition probabilities to satisfy detailed balance
 Many choices are possible
• e.g. p   0.25 0.5 0.25
• try them out
 0 1 0 
P   0.5 0 0.5 


 0 1 0 


Most efficient
 0.97 0.02 0.01 
P   0.01 0.98 0.01 


 0.01 0.02 0.97 


Least efficient
 0.0 0.5 0.5 
 0.42 0.33 0.25 


P   0.17 0.66 0.17  P   0.25 0.5 0.25 


 0.5 0.5 0.0 
 0.25 0.33 0.42 




Barker
Metropolis
11
Metropolis Algorithm 1.
 Prescribes transition probabilities to satisfy detailed balance,
given desired limiting distribution
 Recipe:
From a state i…
• with probability tij, choose a trial state j for the move (note: tij = tji)
• if pj > pi, accept j as the new state
• otherwise, accept state j with probability pj/pi
generate a random number R on (0,1); accept if R < pj/pi
• if not accepting j as the new state, take the present state as the next
one in the Markov chain p ii  0 
Metropolis, Rosenbluth, Rosenbluth, Teller and Teller,
J. Chem. Phys., 21 1087 (1953)
12
Metropolis Algorithm 2.
 What are the transition probabilities for this algorithm?
• Without loss of generality, define i as the state of greater probability
pj
p ij  t ij 
pi
p ji  t ji
p ii  1   p ij

p j 
in
general:
p

t
min

ij
ij
 p ,1 
 i 

pi  p j
j i
 Do they obey detailed balance?
?
p ip ij  p jp ji
pj ?
p it ij  p jt ji
pi
t ij  t ji
 Yes, as long as the underlying matrix T of the Markov chain is
symmetric
• this can be violated, but acceptance probabilities must be modified
13
Markov Chains and Importance Sampling 1.
 Importance sampling specifies the desired limiting distribution
 We can use a Markov chain to generate quadrature points
according to this distribution
1 inside R
 Example
s
0
0.5
r2 
0.5
dx 
0.5
dy ( x 2  y 2 ) s ( x, y )
0.5
0.5
0.5
0.5
dx 
0.5
outside R

dys ( x, y )
r 2s
s
V
V
q = normalization constant
V
• Method 1: let p1( x, y)  s( x, y) / q1
• then r 2 s
2
2
r
2

p1 p
1
s
p1 p
1

q1r
q1
p1
p1

q1 r
q1
p1
 r
2
p1
Simply sum r2 with points
given by Metropolis sampling
14
Markov Chains and Importance Sampling 2.
 Example (cont’d)
p ( x, y )  r 2 s / q2
• Method 2: let
r2s
• then
r
2

p2 p
2
s
p2 p
2

q2
p2
q2 / r 2

p2
q2
q2 1/ r 2

p2
1
r 2
p2
 Algorithm and transition probabilities
• given a point in the region R
• generate a new point in the vicinity of
given point
xnew = x + r(-1,+1)dx ynew = y + r(-1,+1)dy
• accept with probability min(1,p new / p old )
p 1new s new / q1 s new
• note


p 1old
s old / q1
s old
Normalization constants cancel!
• Method 1: accept all moves that stay in R
2 new r 2 old
r
• Method 2: if in R, accept with probability    
15
Markov Chains and Importance Sampling 3.
 Subtle but important point
• Underlying matrix T is set by the trial-move
algorithm (select new point uniformly in
vicinity of present point)
• It is important that new points are selected
in a volume that is independent of the Different-sized
trial sampling
present position
regions
• If we reject configurations outside R,
without taking the original point as the
“new” one, then the underlying matrix
becomes asymmetric
16
Evaluating Areas with Metropolis Sampling
 What if we want the absolute area
of the region R, not an average over
it?
0.5
0.5
A
0.5
dx 
0.5
dys ( x, y )  s
V
• Let p1( x, y)  s( x, y) / q1
• then A  s
 q1 p  q1
p
1
p1
1
• We need to know the normalization
constant q1
• but this is exactly the integral that we
are trying to solve!
 Absolute integrals difficult by MC
• relates to free-energy evaluation
17
Summary
 Markov process is a stochastic process with no memory
 Full specification of process is given by a matrix of
transition probabilities P
 A distribution of states are generated by repeatedly stepping
from one state to another according to P
 A desired limiting distribution can be used to construct
transition probabilities using detailed balance
• Many different P matrices can be constructed to satisfy detailed
balance
• Metropolis algorithm is one such choice, widely used in MC
simulation
 Markov Monte Carlo is good for evaluating averages, but not
absolute integrals
 Next up: Monte Carlo simulation