Introduction to Markov chain mixing

 Recall 

if ($X_n)_n$ is an irreducible Markov chain with stationary distribution $\pi$, thhen 

$\lim_{n \to \infty} \frac{1}{n} \sum_{j=0}^n 1_{[X_j = x]} = \pi(x)$,  $ \quad \mathbb{P}_\mu$ - a.s

Today's goal 

We will show that $X_n$ converges to $\pi$ under some "strong sense".
  • Total variation distance
  • The convergence theorem
  • Mixing times
There is three ways to characterize the total variation distance:
$\mu$ and $\nu$ : probability measures on $\Omega$.
        $\mid\mid \mu - \nu \mid\mid_{TV}$ = $max_{A\subset \Omega} \mid\mu (A) - \nu (A)\mid$.
Lemma
  •  $\mid\mid \mu - \nu \mid\mid_{TV}  = \frac{1}{2} \sum_{x \in \Omega} \mid \mu (x) - \nu (x)\mid$.
  • $\mid\mid \mu - \nu \mid\mid_{TV} = \frac{1}{2} sup{\mu \f - \nu \f : \f satisfying \max_{x\in \Omega} \mid \f(x) \mid \leq 1}$.
  • $\mid\mid \mu - \nu \mid\mid_{TV} = inf{\quad \mathbb{P} [X \neq Y] : (X, Y) is a coupling of \mu , \nu }.
Definition
We call (X, Y) the optimal coupling if $\quad \mathbb{P} [X \neq Y] = \mid\mid \mu - \nu \mid\mid_{TV}$.

The Convergence Theorem

Suppose that ($X_n)_n$ is a Markov chain with transition matrix P. Assume that P is irreducible and aperiodic, then
  • there exists r such that $\mathbb{P}^r (x, y) > 0 for all x, y \in \Omega$;
  • there exists a unique stationary distribution $\pi and \pi(x) > 0 for all x \in \Omega$.
Theorem
Suppose that P is irreducible, aperiodic, with stationary distribution $\pi$.
Then there exist constants $\alpha \in$ (0, 1) and C > 0 such that
            $\max_{x\in \Omega}\mid\mid \mathbb{P}^n (x, .) - \pi \mid\mid_{TV} \leq \mathbb{C}\alpha ^n \  \forall n \geq 1$.

Mixing time

Definition 
        d(n) = $\max_{x\in \Omega}\mid\mid \mathbb{p}^n (x, .) - \pi \mid\mid_{TV}$
         $\bar d (n) = \max_{x,y \in \Omega} \mid\mid \mathbb{P}^n(x,.) - \mathbb{P}^n (y,.) \mid\mid_{TV}$
Lemma
        $ d(n) \leq \bar d (n) \leq 2d(n)$
Lemma 
        $\bar d (m + n) \leq \bar d (m) . \bar d (n)$
Corollary 
        $\bar d (mn) \leq \bar d (n)^m$ 
Definition
        $ t_{mix} = \min {n : d(n) \leq \frac{1}{4} }, \   \ t_{mix} (\in) = \min {n : d(n) \leq \in}$
Lemma
        $ t_{mix} (\in) \leq$  $\log({\frac{1}{\in}}) \frac{t_{mix}}{\log{2}}$ 

Couple tow Markov chains

Definition
A coupling of two Markov chains with transition matrix P is a process ($\X_n, \Y_n)_{n \geq 0}$ with the following two properties.
  • Both ($\X_n ) and (\Y_n)$ are Markov chains with transition matrix P.
  • They stay together after their first meet. 
Notation : If ($\X_n)j_{n \geq 0} and (\Y_n)_{n \geq 0}$ are coupled Markov chains with $\X_0 = x, \Y_0 = y, then we denote by \quad\mathbb{P}_{x,y} the law of (\X_n, \Y_n)_{n \geq 0}$.

Theorem
Suppose that P is irreducible with stationary distribution $\pi$. Let $(\X_n, \Y_n)_{n \geq 0}$ be a coupling of Markov chains with transition matrix P for which $\X_0 = x, \Y_0 = y$. Define $\tau$ to be their first meet time : 
        $\tau = \min {n \geq 0 : \X_n = \Y_n }$. 
Then 
          $\mid\mid \mathbb{P}^n (x, .) - \mathbb{P}^n (y, .)\mid\mid_{TV} \leq \quad\mathbb{P}_{x,y} [\tau \> n]$. 
In particular, 
            d(n) $\leq \max_{x,y} \quad\mathbb{P}_{x,y}[\tau > n]$.

Random walk on N-cycle : Upper bound on $t_{mix}$

Lazy walk : it remains in current position with probability 1 / 2, moves left with probability 1 / 4, right with probability 1 / 4.
  • It is irreducible.
  • The stationary measure is the uniform measure.
Theorem
For the lazy walk on N-cycle, we have
            $ t_{mix} \leq N^2$.

Comments

Post a Comment

Popular posts from this blog

Introduction to Stochastic Processes

Domain Definition $\Omega$: finite state space P: transition matrix $| \Omega | \times |\Omega|$ we will see it multiple time (it mean what is the probability of moving from state $S_x$ to state $S_y$). A sequence of random variables ($X_0,X_1,X_2,\ldots) is a Markov chain with state $\Omega$ and transition matix P if for all n $\geq$ 0, and all sequences ($x_0, x_1,\ldots,x_n,x_{n+1}), we have that      $\mathbb{P}[X_{n+1} = x_{n+1} | X_0 = x_0,\ldots,X_n=x_n] = \mathbb{P}[X_{n+1} = x_{n+1} | X_n = x_n] = P(x_n, x_{n+1})$.  Gambler's ruin     The gambler's situation can be modeled by a Markov chain on the state space {0, 1, ..., N}: $X_0$: initial money in purse $X_n$: the gambler's fortune at time n $\mathbb{P}[X_{n+1} = X_n + 1 | X_n] = 1/2$ $\mathbb{P}[X_{n+1} = X_n - 1 | X_n] = 1/2$ The states 0 and N are absorbin. $\tau$: the time that the gambler stops. Theorem: Assume that $X_0 = k for some 0 \leq k \geq N$. Then  ...
Read more

Markov chains: time-reversal

 Ergodic Theorem Let $f$ be a real-valued function defined on $\Omega$. If $(X_n)_n$ is an irreducible Markov chain with stationary distribution $\pi$, then for any starting distribution $\mu$, we have          $\lim_{n \to \infty} \frac{1}{n} \sum_{j=0}^n{f(X_j)} = \pi f$,  $\quad \mathbb{P}_\mu$ - almost surely (a.s.) In particular, $\lim_{n \to \infty} \frac{1}{n} \sum_{j=0}^n 1_{[X_j = x]} = \pi(x)$,    $ \quad \mathbb{P}_\mu$ - a.s Detailed balance equations Definition Suppose that a probability measure $\pi$ on $\Omega$ satisfies                         $\pi(x)$P(x,y) = $\pi(y)$P(y,x),  $\quad \forall$ x, y $\in \Omega$. These are called detailed balance equations. Lemma Any distribution $\pi$ satisfying the detailed balance equations is stationary for P. Definition A chain satisfying detailed balance equations is called reversible. Simple random walk on grap...
Read more

Markov chains: stationary distribution

 Irreducible Definition      A transition matrix P is called irreducible, if for any x, y $\in \Omega$, there exists a number n (possibly depending on x,y) such that           $P^n(x,y) > 0$.     For any x $\in \Omega, define T(x) = {n \geq 1: P^n(x,x) > 0}$. The period of state x is the greatest common divisor of T(x), denoted by gcd(T(x)). Lemma if P is irreducible, then gcd(T(x)) = gcd(T(y)) for all x, y $\in \Omega$. Aperiodic Definition For an irreducible chain, the period of the chain is defined to be the period which is common to all states. the chain is aperiodic if all states have period 1. Example: Consider a simple random walk on N-cycle where N is odd. Then the walk is irreducible and aperiodic. Theorem If P is irreducible and aperiodic, then there exists an integer r such that                          $P^n(x,y) > 0, \forall x, y \...
Read more