Topics

- Sections: 6.1 - 6.6, 6.14
- Definitions:
- Markov Chain
- Homogeneous Markov Chain
- Transition Matrix
- n-step Transition Matrix
- Recurrent State
- Transient State
- Null and positive recurrent
- Periodic
- Intercommunicating States
- Closed
- Irreducible
- Stationary Distribution
- Reversible
- Total Variation Distance
- Mixing Time
- Coupling of Two Markov Chains
- Random Walk on a Graph

- Theorems: 6.1.5, 6.1.8, 6.2.3, 6.2.4, 6.2.5, 6.2.9, 6.3.2, 6.3.3, 6.3.4, 6.3.5, 6.4.3, 6.4.6, 6.4.17, 6.5.4, 6.6.1, 6.14.9, Coupling Collison Time Bound on Mixing Time,
- Sample Questions:
- What is the mixing time for a random walk on the complete graph with self loops?
- Give upper and lower bounds for the mixing time of a random walk on two complete graphs of size n connected by a single edge.
- Can a single Markov Chain have more than one stationary distribution? Why or why not?
- Consider a two state MC with states A, B. p(A,A) =1/2, p(A, B) =1/2. P(B,B) =1/4, P(B,A) =3/4. What is the stationary distribution? What are the eigenvalues of the adjacency matrix?
- Is a branching process a reversible Markov Chain? How about SRW?
- Decompose the state space of the branching process MC.
- Prove that 3d random walk is transient.
- Prove that 2d random walk is null recurrent.
- What is the stationary distribution of the random walk on the complete bipartite graph where the left partition has n vertices, the right 2n, and at each step there is probability 1/2 of remaining in the current state.
- Give a graph whose random walk has period 3.
- Give a Markov chain whose state space is not irreducible.
- Give a Markov chain whose state space can be partitioned into two closed sets of states.
- Consider m balls lying in n bins. At each step we pick a ball at random out of a bin, and throw it into a bin chosen uniformly at random. Is this a Markov Chain? What is the state space? Clasify the chain. What is the stationary distribution? Give upper and lower bounds for its mixing time.