MIT 6 856J - Markov Chains (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

Markov Chains



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

Markov Chains

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

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Markov Chains and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Markov Chains and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?