Markov Chains Mixing Times Lecture 5 Omer Zentner 30.11.2016 Agenda Notes from previous lecture

Mixing time Time reversal & reversed chain Winning Streak Time Reversal (example) A bit about time reversal in Random Walks on Groups Eigenvalues (and bounds for mixing time we get with them) Eigenvalues example Notes from previous lecture

Weve seen the definition of Total Variation Distance How similar 2 distributions are = = Weve used TV to define 2 distance measures Distance from stationary distribution

Distance between rows of the transition matrix Notes from previous lecture Weve seen some properties of the distance measures From which we got Well now continue with defining Mixing Time

Mixing Time Definitions Mixing Time From:

( ) ( ) ( )

We get: And with : Time Reversal The time reversal of an irreducible Markov chain with transition

matrix P and stationary distribution is: Let be an irreducible Markov chain with transition matrix P and stationary distribution We write for the time reversed chain with transition matrix is stationary for For every , we have:

Time Reversal Weve seen in lecture 2: If a transition matrix and the stationary distribution have the detailed balance property, then the chain is reversible: This means that the distribution of is the same as the distribution of Follows from the detailed balance property When a chain is reversible, its time reversal is the same as itself.

We have: = Time Reversal & reversed chains Reversible chain example undirected graph Non reversible chain example biased random walk on the n-cycle Example Winning streak Repeatedly tossing a fair coin, while keeping track of the length of last

run of heads. Memory is limited can only remember n last results. is a Markov chain with state space {0,,n} Current state of chain is =2 +1=3 +2=0

Example Winning streak Transition matrix is given by (non-zero transitions): Example Winning streak stationary distribution for P Can check:

Example Winning streak Time reversal The Time reversal is (non-zero transitions): ^ =0 ^ +1=3

^ +2=2 Example Winning streak Time reversal For the time reversal of the winning streak: After n steps distribution is stationary, regardless of initial distribution

Why? If , distribution is stationary for all , since If , transitions force , so stationary for t > k Example Winning streak Time reversal If :

The location of depends on how much time we spent at n For 0 < k < n: probability of to hold for (k-1) times, and then proceeding on the k-th turn. In this case : and ( since = (n-1) (n-k)) Altogether, If initial distribution is not concentrated on a single state distribution at time n is a mixture of the distributions for each possible initial state, and is thus stationary.

Example Winning streak Time reversal Note (lower bound): If the chain is started at n, and then leaves immediately, then at time n-1 it must be at state 1. Hence And from the definition of total variation distance we get: Conclusion - for the reverse winning streak chain we have:

for any positive Example Winning streak conclusion It is possible for reversing a Markov chain to significantly change the mixing time The mixing time of the Winning-Streak will be discussed in following lectures.

Reminder random walk on a group A random walk on a group G, with incremental distribution :

=G is a distribution over At each step, we randomly choose , according to , and multiply by it Or, in other words: Weve seen that for such a chain, the uniform probability distribution is a stationary distribution. Will sometimes be noted as

Weve also seen that if is symmetric (), the chain is reversible, and P = Mixing Time and Time Reversal inverse distribution: If is a distribution on a group G, is defined by: (g) := , for all .

let P be a transition matrix of a random walk on group G with incremental distribution , then the random walk with incremental distribution is the time reversal . Even when is not symmetrical, forward and reverse walk distributions are at the same distance from stationary Mixing Time and Time Reversal Lemma 4.13

Let P be the transition matrix of a random walk on a group G with incremental distribution Let be the transition matrix of a walk on G with incremental distribution Let be the uniform distribution on G. Then, for any Mixing Time and Time Reversal

lemma 4.13 - proof Proof: Let be a Markov chain with transition matrix P, and initial state id Can write: where are random elements chosen independently from Markov chain with transition matrix , initial state id With increments chosen independently from

Mixing Time and Time Reversal lemma 4.13 proof cont. For any fixed elements , From the definition of Summing over all strings such that : Hence:

Mixing Time and Time Reversal Corollary If is the mixing time of a random walk on a group and is the mixing time of the inverse walk, then Eigenvalues spectral representation of a reversible transition matrix

Note: Because we regard elements of as functions from to , we will call eigenvectors of the matrix P eigenfunctions Eigenvalues Define another inner-product on :

Eigenvalues Lemma 12.2 - proof Define a matrix A, as follows: A is symmetric: We assumed P is reversible with respect to , so we have detailed balance:

=> So, A(x,y) = Lemma 12.2 proof cont. A= The Spectral Theorem for Symmetric Matrices, guarantees that the inner-product space (, ) has an

orthonormal basis , such that is an eigenfunction with real eigenvalue Lemma 12.2 proof cont. Can also see that is an eigenfunction of A, with eigenvalue 1: +=

Column i = Lemma 12.2 proof cont. We can decompose A as is diagonal with

A= Lemma 12.2 proof cont. Lets define We can see that is an eigenfunction of P with eigenvalue : =

Lemma 12.2 proof cont. are orthonormal in respect to the inner product : => so, we have that is an orthonormal basis for (, ), such that is an eigenfunction with real eigenvalue Lemma 12.2 proof cont.

Now, lets consider the following function: can be written as a vector in (, ) , via basis decomposition with : Lemma 12.2 proof cont. (x,y) = ()(x)

So: ( Dividing both sides by completes the proof Absolute spectral gap For a reversible transition matrix, we label the eigenvalues of P in decreasing order Definition: :

Definition: absolute spectral gap (: from lemma 12.1 we get that if P is aperiodic and irreducible, then -1 is not an eigenvalue of p, so > 0 Side note: The spectral gap of a reversible chain is defined by If the chain is lazy, =

Relaxation time Definition: relaxation time (): We will now bound a reversible chains mixing time, with respect to its relaxation time Theorem 12.3 (upper bound)

Theorem 12.4 (lower bound) Theorem 12.4- proof Suppose is an eigenfunction of P with eigenvalue Weve seen that eigenfunctions are orthogonal with respect to , and that 1 (vector/function) is an eigenfunction

So we have = Theorem 12.4- proof cont. So, taking x such that = , we get Using :

Theorem 12.4- proof cont. Theorem 12.4- proof cont. = == Maximizing over eigenvalues different from 1, we get: (-1)

Mixing time bound using eigenvalues example Weve seen random walks on the n-cycle, and random walks on groups. A random walk on the n-cycle can be viewed as a random walk on an n-element cyclic group. We will now use this interpretation to find eigenvalues and eigen

functions of that chain Mixing time bound using eigenvalues example Random walk on the cycle of n-th roots of unity Let , are the n-th roots of unity Since , we have

Hence, is a cyclic group of order n, generated by Random walk on the cycle of n-th roots of unity Now, will consider the random walk on the n-cycle, as the random walk on the multiplicative group our incremental distribution will be the uniform distribution over As usual, Let P denote the transition matrix for the walk.

Random walk on the cycle of n-th roots of unity Now, lets examine at the eigenvalues of P If is an eigenfunction of P, then Random walk on the cycle of n-th roots of unity

Lets look at , when we define ) := i.e. is an eigenfunction of P: Eigenvalue of is

Random walk on the cycle of n-th roots of unity What is the geometrical meaning of this? For any the average of and is a scalar multiple of Since the chord connecting and is perpendicular to , the projection of onto has length

Random walk on the cycle of n-th roots of unity spectral gap & relaxation time ) := is an eigenfunction with eigenvalue We have Cos(x) = 1 - Random walk on the cycle of n-th

roots of unity spectral gap & relaxation time So, spectral gap is of order Relaxation time () is order Note that when n is even, the chain is periodic: is an eigen value, and so = 0 THE END

Questions? Thank you!