# MIT 6 856J - Markov Chains (6 pages)

Previewing pages*1, 2*of 6 page document

**View the full content.**# Markov Chains

Previewing pages *1, 2*
of
actual document.

**View the full content.**View Full Document

## Markov Chains

0 0 38 views

Lecture Notes

- Pages:
- 6
- School:
- Massachusetts Institute of Technology
- Course:
- 6 856j - Randomized Algorithms

**Unformatted text preview: **

Markov Chains Markov chains Powerful tool for sampling from complicated distributions rely only on local moves to explore state space Many use Markov chains to model events that arise in nature We create Markov chains to explore and sample from problems 2SAT Fix some assignment A let f k be expected time to get all n variables to match A if n currently match Then f n 0 f 0 1 f 1 and f k 1 21 f k 1 f k 1 Rewrite f 0 f 1 1 and f k f k 1 2 f k 1 f k So f k f k 1 2k 1 deduce f 0 1 3 2n 1 n2 so nd with probability 1 2 in 2n2 time With high probability nd in O n2 log n time More general formulation Markov chain State space S markov chain begins in a start state X0 moves from state to state so output of chain is a sequence of states X0 X1 Xt t 0 movement controlled by matrix of transition probabilities pij probability next state will be j given current is i thus j pij 1 for every i S implicit in de nition is memorylessness property Pr Xt 1 j X0 i0 X1 i1 Xt i Pr Xt 1 j Xt i pij Initial state X0 can come from any probability distribution or might be xed trivial prob dist Dist for X0 leads to dist over sequences Xt Suppose Xt has distribution q vector qi is prob of state i Then Xt 1 has dist qP Why 1 Observe Pr Xt r j Xt i Pijr Graph of MC Vertex for every state Edge i j if pij 0 Edge weight pij weighted outdegree 1 Possible state sequences are paths through the graph Stationary distribution a such that P left eigenvector eigenvalue 1 steady state behavior of chain if in stationary stay there note stationary distribution is a sample from state space so if can get right stationary distribution can sample lots of chains have them to say which need de nitions Things to rule out in nite directed line no stationary 2 cycle no stationary disconnected graph multiple Irreducibility any state can each any other state i e path between any two states i e single strong component in graph Persistence Transience t rij is probability rst hit state j at t given start state i fij is

View Full Document