Probability
9.6 Markov Chain Monte Carlo (MCMC)
Alex Tsun
Agenda
Discrete-Time Stochastic Processes
Discrete-Time Stochastic Processes
Discrete-Time Stochastic Processes
X0
X1
X2
X3
X4
X5
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Random Walk on a Graph Example
Definition of
Expectation
1
2
3
5
4
Markov Chains
Markov Chains
Markov Chains
Transition Probability Matrix Example
1
2
3
5
4
To s1
To s2
To s3
To s4
To s5
From s1
From s2
From s3
From s4
From s5
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
Transition Probability Matrix Example
1
2
3
5
4
P(Xt+1= 2 | Xt= 1)
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
P(Xt+1= 3 | Xt= 1)
1
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
P(Xt+1= 1 | Xt= 2)
P(Xt+1= 4 | Xt= 2)
2
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
Transition Probability Matrix Example
1
2
3
5
4
From s1
From s2
From s3
From s4
From s5
To s1
To s2
To s3
To s4
To s5
Transition Probability Matrix Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
From state 2, can only go to 1 and 4 with nonzero probability
Computing Probability Example
1
2
3
5
4
From state 2, can only go to 1 and 4 with nonzero probability
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Computing Probability Example
1
2
3
5
4
Random Picture
Definition of
Expectation
Applying A Transition Matrix
1
2
3
5
4
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Suppose we start at a random state with these probabilities (sum to 1).
Applying A Transition Matrix
1
2
3
5
4
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Suppose we start at a random state with these probabilities (sum to 1).
What is my belief distribution for where I am next?
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Def of TPM (works for any time)
Def of v
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Def of TPM (works for any time)
Def of v
LTP
P(X1= 1)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
P(X1= 1)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
P(X1= 1)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Def of TPM (works for any time)
Def of v
P(X1= 1)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Def of TPM (works for any time)
Def of v
LTP
P(X1= 1)
P(X1= 2)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
Def of TPM (works for any time)
Def of v
LTP
P(X1= 2)
HMMMM
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
P(X1= 1)
P(X1= 2)
P(X1= 3)
P(X1= 4)
P(X1= 5)
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
P(X1= 1)
P(X1= 2)
P(X1= 3)
P(X1= 4)
P(X1= 5)
Right-multiplying by P gives the belief distribution at the next time step!
Applying A Transition Matrix
P(X0= 1)
P(X0= 2)
P(X0= 3)
P(X0= 4)
P(X0= 5)
Let’s compute the matrix product vP (we’ll see why soon!).
P(X1= 1)
P(X1= 2)
P(X1= 3)
P(X1= 4)
P(X1= 5)
Right-multiplying by P gives the belief distribution at the next time step!
By induction (repeatedly applying this matrix P), vPn is the distribution after n time steps.
Stationary Distribution of a Markov Chain
Markov Chain Monte Carlo (MCMC)
Markov Chain Monte Carlo (MCMC)
Markov Chain Monte Carlo (MCMC)
Markov Chain Monte Carlo (MCMC)
The Knapsack Problem
The Knapsack Problem
The Knapsack Problem
The Knapsack Problem
The Knapsack Problem
Greedy Algorithm for The Knapsack Problem?
Greedy Algorithm for The Knapsack Problem?
Item | Value | Weight | Value / Weight |
Laptop | 156 | 52 | 3 |
iPad | 100 | 50 | 2 |
Tablet | 98 | 49 | 2 |
Greedy Algorithm for The Knapsack Problem?
Item | Value | Weight | Value / Weight |
Laptop | 156 | 52 | 3 |
iPad | 100 | 50 | 2 |
Tablet | 98 | 49 | 2 |
Greedy Algorithm for The Knapsack Problem?
Item | Value | Weight | Value / Weight |
Laptop | 156 | 52 | 3 |
iPad | 100 | 50 | 2 |
Tablet | 98 | 49 | 2 |
Greedy Algorithm for The Knapsack Problem?
Item | Value | Weight | Value / Weight |
Laptop | 156 | 52 | 3 |
iPad | 100 | 50 | 2 |
Tablet | 98 | 49 | 2 |
Greedy Algorithm for The Knapsack Problem?
Item | Value | Weight | Value / Weight |
Laptop | 156 | 52 | 3 |
iPad | 100 | 50 | 2 |
Tablet | 98 | 49 | 2 |
MCMC for the Knapsack Problem
We’ll define a Markov Chain whose state space is of size 2n:
Binary vectors x of length n (which can only have 0/1 entries), representing whether or not we have each item.
We’ll transition only to “good” states - ones that are feasible (satisfy weight constraint), while keeping track of the best solution so far.
MCMC for the Knapsack Problem
We’ll define a Markov Chain whose state space is of size 2n:
Binary vectors of length n (which can only have 0/1 entries), representing whether or not we have each item.
We’ll transition only to “good” states - ones that are feasible (satisfy weight constraint), while keeping track of the best solution so far.
MCMC for the Knapsack Problem
We’ll define a Markov Chain whose state space is of size 2n:
Binary vectors of length n (which can only have 0/1 entries), representing whether or not we have each item.
We’ll transition only to “good” states - ones that are feasible (satisfy weight constraint), while keeping track of the best solution so far.
MCMC for the Knapsack Problem
We’ll define a Markov Chain whose state space is of size 2n:
Binary vectors of length n (which can only have 0/1 entries), representing whether or not we have each item.
We’ll transition only to “good” states - ones that are feasible (satisfy weight constraint), while keeping track of the best solution so far.
MCMC for the Knapsack Problem
MCMC for the Knapsack Problem
By running many iterations, we get to the stationary distribution.
The stationary distribution has higher probabilities for “good” or “feasible” solutions, so we are likely to get a good solution!
Note: This is one version of MCMC for this knapsack problem, but it may not be the best. It would be good to transition to “better” solutions (higher value), and not just to any feasible solution.
END PIC
Alex Tsun
Joshua Fan