Mixing Time Markov chain:t=(,P) stationary distribution: p):distribution at time when initial state is △(t)=lp-π‖Tv △(t)=max△x(t) x∈2 Tx(e)=min{t|△x(t)≤e}T(e)=max T(e) x∈2 mixing time: Tmix =T(1/2e) rapid mixing: Tmix=(log2)0(1) △(k·Tmix)≤e-and(e)≤Tmix, InMixing Time Markov chain: M = (⌦, P) • mixing time: ￾x(t) = kp(t) x ￾ ⇡kT V ￾(t) = max x2⌦ ￾x(t) ⌧x(✏) = min{t | ￾x(t)  ✏} ⌧ (✏) = max x2⌦ ⌧x(✏) ⌧mix = ⌧ (1/2e) stationary distribution: ⇡ p(t) x : distribution at time t when initial state is x rapid mixing: ⌧mix = (log |⌦|) O(1) ￾(k · ⌧mix)  e￾k ⌧ (✏)  ⌧mix · ⇠ ln 1 ✏ ⇡ and