15-750				04/19/01

* A simple coupling example (walk on a line)
* eigenvalues and rapid mixing
* conductance and expanders
* a practical example of MCMC (Markov Chain Monte Carlo).

See also: http://www.cs.berkeley.edu/~sinclair/mcmc.ps

==================================

One more (simple) coupling example:
Consider a random walk on the line 1,...,n.  You start at point 1.
At each step you flip a coin: heads means go left, tails means
go right. If you're at 1 and get a heads, just stay put (same if
you're at n and get a tails).

1. What is the stationary distribution?  Ans: uniform.  [Can verify
directly or view as special case of random walk on graph, where the
self-loops give each node the same out-degree]

2. How long until we get close?  Let's usse a coupling argument. We
are particle x, starting at location 1.  Also imagine particle y, at a
random spot according to stationary distribution.  Now, let's
correlate the walks: each time we get heads, so does y, and same with
tails.  So, y stays uniformly distirbuted.  But also, notice that our
distance to y never goes up, and sometimes goes down.  In particular,
by the time we reach point n, we must have coupled.

We can now use fact from before that expected time to reach n is at
most 2mn = 2n^2.  Let's use "Markov's inequality": the probability we
have reached by time 4n^2 is at least 1/2.  If not, then at least a
1/2 chance in next 4n^2 steps.  So, if we want success probability
1-epsilon, then we just have to walk for O(n^2* log(1/epsilon))
steps.  So, in this many steps, the prob we have *not* coupled is at
most epsilon, so by our lemma from last time, this means our variation
distance is at most epsilon.  That's it.

Note: the lemma about variation distance is kind of clever.
More straightforward way to do that last part of the argument is:
	Pr(x is at i) >= Pr(y is at i)*Pr(coupled | y is at i).  
We want this to be at least 1/n * (1-epsilon).
We know Pr(y is at i) is 1/n.  But the coupling probability might
depend on y [think of n=2 and a zero-step walk].  So you end up
getting a bit worse bounds if you do it this way.

==================================
Now we're going to talk more generally about what properties of a
graph make the walk rapidly mixing.  

One way to think of a random walk is as a matrix-vector product.  Say
we have n states.  Define transition matrix:

         M_ij = prob of going to j given that you're in state i.

 E.g., our random walk on the line...

 Write a prob distribution as a row vector q.  Then, one step of walk = qM

 stationary distribution: eigenvector of eigenvalue 1.


Say we're interested in rapid mixing.  Want to approach stationary
dist in time poly in log(n).  Can we talk about this in terms of
properties of the matrix?

Eigenvalue gap -> Rapid Mixing
==============================

THEOREM: Say M is a transition matrix with real eigenvalues and orthogonal
eigenvectors.  Then, for any starting distribution, the L_2 distance
between q^(t) (the distribution after t steps) and the stationary
distribution \pi is at most |\lambda_2|^t, where \lambda_2 is the
eigenvalue of second-largest absolute value.

First of all, when do we get real eigenvalues and orthogonal
eigenvectors?  Well, one case is when M is symmetric.  E.g., think of
a random walk on a regular graph (all nodes have the same degree).  In
fact, can generalize to ``time-reversible'' Markov chains: \pi_i *
M_{ij} = \pi_j * M_{ji} for all i,j.  E.g., random walk on an
undirected graph where nodes are not necessarily all the same degree.
[Non-time-reversible: random walk on a directed cycle].

Second: we know that the stationary distribution is an eigenvector of
eigenvalue equal to 1.  This is also the largest eigenvalue: all other
eigenvalues have magnitude <= 1.  (The proof of the theorem will show
us why.)  The difference between 1 and |\lambda_2| is called the
"eigenvalue gap".

So, if we have an eigenvalue gap of some amount gamma, and we want an
L_2 distance of delta_2, then we need only O((1/gamma)*log(1/delta_2))
steps.  We'll relate L_2 distance to variation distance in a minute.


PROOF OF THEOREM: 
Say orthogonal eigenvectors are e_1, \ldots, e_n.  e_1 = \pi.
Say we start at

        q^{(0)} = c_1e_1 + ... + c_ne_n.

By definition of eigenvectors (and since M(a+b) = Ma + Mb), after t
steps, we're at:

    q^{(t)} = c_1e_1 + (c_2(\lambda_2)^te_2 +... + c_n (\lambda_n)^te_n).

Notice that |lambda_2| cannot be larger than 1, since otherwise our
vector is getting bigger and bigger.  Can't have a probability vector
with a Euclidean length longer that 1 (Euclidean length is always
between 1/sqrt(n) and 1).  

Assuming that |lambda_2| < 1 (else the theorem is vacuous), and e_1 is
pi, we must have c_1 = 1.  So, the L_2 distance between q^(t) and e_1
is just the length of the vector corresponding to the second part of
the RHS.  We can rewrite this vector like:
		(lambda_2)^t * blah
where blah is shorter than (c_2e_2 + ... + c_ne_n), which for sure is
shorter than q^(0), which has length at most 1.  So, this means the
L_2 distance between q^(t) and e_1 is at most (lambda_2)^t.  QED


How does this relate to variation distance?  Variation distance = 1/2
of L_1 distance.  L_1 distance is at most sqrt(n) * L_2 distance.
[[E.g., if you have a unit-length vector in R^n, the largest the sum
of the entries can be is if they are all equal to 1/sqrt(n), in which
case the sum is sqrt(n).]]  So, if we want a variation distance of
delta_1, we just need to run for O((1/gamma)*log(n/delta_1)) steps.



What does the eigenvector of 2nd-largest eigenvalue look like?  It has
some positive entries and some negative entries.  E.g., if graph is
regular, then the eigenvector of highest eigenvalue has all entries
equal to 1/n; since the next one is perpendicular, the sum of its
positive entries must equal the sum of its negative entries.  If the
graph is dumbbell shaped, then the positives will be on one side and
the negatives will be on the other.  These describe the sets that in a
sense mix most slowly together.  In fact, this approach is often used
for graph partitioning (splitting into large pieces that have few
edges between them).
=============================================================================

When do we get rapid mixing?

Ans #1: if have gap between largest and 2nd largest eigenvalue.

Ans #2: when the Markov chain has high "conductance".

[Note: this has nothing to do with the notion of "resistance" we
discussed last time.]


Def:

* pi(S) = sum_{i in S} pi_i.
  (prob of being in S according to pi)

* flow(S) = sum_{i in S, j not in S} w_ij, 
  where w_ij = (pi_i)*(p_ij) = prob of being on edge i->j in pi.
  (measure of # edges leaving S).

* Conductance.  Let Phi(S) = flow(S)/pi(S).
  Conductance Phi is the minimum Phi(S) over all sets S of pi <= 1/2.

Think of Phi(S) this way:  If you started out at a random place in S
(according to pi), what's the chance that you won't be in S in your
next step? This is sum_{i in S, j not in S} Pr(was at i and went to j).
This is sum_{i in S, j not in S} p_{ij} * pi_i / pi(S).
This is flow(S) / pi(S).


If graph has *low* conductance,then it's pretty clear it's *not*
rapidly mixing.  In particular, if you start out at a random point in
the bad set S, it will take a long time to get out.  More interesting
thing is that if have high conductance, then it *is* rapidly mixing.

Note: very similar to definition of an Expander graph.
A graph is an epsilon-expander if for all sets S of <= n/2 nodes, 
                |N(S) - S| > epsilon*|S|.

Here is the main theorem (we won't give the proof): if diagonal entries
are constant > 0 (e.g., self-loops) then
	Eigenvalue gap is Omega(conductance^2).

In the other direction (also won't give the proof):
	Conductance is Omega(eigenvalue gap).

Intuition for main theorem: Imagine giving each node a number
according to eigenvector of 2nd largest eigenvalue, and pretend this
is a distribution (it's not: the values all sum to 0).  After 1 step
in the walk, the fact that we have high conductance means there will
be a lot of cancelling going on.  (and self-loops make surewe don't
just bounce between S and its complement.)

==================================================

Application: Gibbs sampling from a posterior.  Say you have some large
set of hypotheses about some phenomenon.  before you see any data, you
might have some prior belief about which is true.  Now, you see some
data, and use Bayes rule: Pr(h | d) = Pr(d | h)*Pr(h) / Pr(d).
Want to find h of highest posterior.

Let's ignore the denominator (it's the same for each h) and say we
know how to compute Pr(d | h) for any given h.  Problem is: too many
h's.  So, how about this: can we at least randomly *sample* h's
according to the posterior distribution?  This is called "Gibbs
sampling".

From now on, let value(h) = posterior prob of h.

Idea: set up some neighborhood structure and take a random walk using
"Metropolis filter"  (Metropolis is someone's name --- I used to think
this was because people were thinking of this as a walk on a grid...)
Specifically, let's say we set up a neighborhood structure so that
each h has d-1 neighbors, plus add self-loop for aperiodicity, so a
total of d neighbors.  Now, say we're at h and our coin toss tells us
to move to neighbor h'.  If value(h') >= value(h) then we go there.
Otherwise, we only go there with prob value(h')/value(h); otherwise we stay
put.  Claim is that this has the correct stationary distribution:

Say at time t, prob at h = value(h) for all h.  Then at time t+1,
Pr(h) = Pr(got here by taking an edge) + Pr(got here by not taking an edge)
      = sum_{nbrs h' of h} value(h')*(1/d)*min{1,value(h)/value(h')} +
        sum_{nbrs h' of h} value(h)*(1/d)*max{0,1 - value(h')/value(h)}.
    = avg_{nbrs h' of h} [min{value(h'), value(h)} + max{0,value(h)-value(h')}]

If h' has smaller value than h, then thing in [...] is
value(h')+value(h)-value(h') = value(h).  If h' has larger value than
h, then thing in [...] is value(h)+0.  Either way, we're averaging a
bunch of things all of which are value(h).

So, the stationary dist is just what we want.  We just hope the markov
chain has high conductance.  

Unfortunately, high conductance means not only that neighborhood
structure is expanding, but also that values are nice.  One place this
happens [from Kalai-Vempala'00] is when h's are CRP investment
strategies.  value(h) means how much money we would have had if we had
used that investment strategy from the start.  Goal is pick random
strategy in proportion to value.  Here, the natural neighborhood
structure has the property that similar strategies have similar
values.  So this all works.