Monday, January 11, 2010

Some snapshots of Markov chains and Monte Carlo Methods

Hello everybody,

Sorry for choosing such a bad name for today's blog. The problem is - this was the first lecture on the subject today, and I did not really know what else to call this blog.

Anyway, this semester, spring 2010, I am enrolled in a course called Markov Chains and Monte Carlo Method (henceforth MCMC) here at Georgia Tech. Our instructor is the wonderful professor Dana Randall and she has an amazing knack for surprising you in each of her lectures. I do not understand how she communicates her lectures this nice - which in essence is ,in my opinion, an art of explaining things effectively - an art I am really horrible at. I guess to explain this nice you have to understand nicer.

Anyways, enough belaboring, let me get to the point; but wait let me get some other things out of the way first.

(The section below definitely need some rework; I hope I will get around to do that)

The exposition in this series of lectures by Prof Randall will be mainly technique driven. That is, we will see the techniques that have evolved while we work with Markov Chains to solve some important problems in Graph Theory, Statistical Physics, Molecular Biology and other curious areas. We will begin our tour with some classical counting problems and see the power of Markov chains as they solve the problem for us by developing appropriate context and motivation.

Last but not the least, since I do not trust my memory fully, I may skip some of what Professor taught in the class owing to my RAM (memento style temporary memory, well not exactly memento style) and thus do a poor job of presenting the lecture's material (with high probability) and sometimes I may add a few extra things from my knowledge that could make the lecture's material a little easier to follow (with vanishingly small probability).

Now the lecture.

So, as I said above, we begin the tour with some classical counting problems.

So, let me just mention the following problem. Can you decide in polynomial time whether an arbitrary undirected graph has got a perfect  matching or not? If you can, can you explicitly find that matching? Going further, can you count the number of matchings in an arbitrary undirected graph? Lastly, can you return an arbitrary perfect matching from the graph (assuming graph has got some finite number, $n$ of perfect matchings, this question asks you to select anyone uniformly).

If I tell you how to solve the $3^{rd}$ the first two problems become trivial. Also, if I tell you answer to the second one, first one becomes trivial. No sweat.

Thus, the first problem is no harder than the second one and the second one is no harder than the third one. What about the other way round?

It turns out if you have access to some oracle which can answer the first question (viz whether the graph has  got a perfect matching or not) you can answer the $2^{nd}$ question as well. And given an oracle access to some device that solves the $3^{rd}$ question, you can answer the $4^{th}$ one. We will see in future posts how to do all these (if I get around to write some).

But let me remind you about the problem of counting perfect matchings in a bipartite graph. Its "cute" in the sense that it has a very good linear algebraic interpretation. Turns out, solving the above counting problem is as tough as computing the permanent of a matrix. You know permanent? Its just the determinants with all the "minuses" gone. And surprisingly its hard to compute permanent whereas computing the determinant (which involves some zig-zagging through 'signs") is easy. In fact, computing the permanent is #$P-Complete$.

Thus, given the above information you can see that counting the  number of perfect matchings in an arbitrary general graph must also be, well, #$P-Complete$.

Now, lets see how the knowledge that a graph has a perfect matching helps in constructing one. Hmmm....So I tell you that I have a graph which has got a erfect matching. What good is this information in finding out one?

Pretty good it turns out. We capture the essence of the above discussion by saying that graphs are self reducible with respect to the perfect matching property. We will prove this later.

Now, I will turn to discuss something about a special bipartite graph, namely the chessboard. Turns out in a chessboard the number of perfect matchings is easily computable. First, lets turn to the following famous problem. You have a $n*n$ chessboard. Can you tile it up using $2*1$ dominos?

You can easily see that its not possible for odd n. For even $n$ its clearly possible. Too trivial. Now I ask is it always the case that you can tile up an arbitrary connected figure which has got an even number of squares. The answer is no. Consider the traditional chessboard with two opposite corners removed. Say the removed squares are both black. The number of white squares being more, domino-tiling is not possible anymore.

Thus, it looks like the sufficient condition for tilability is an elusive beast. Not if Prof Randall has her way. Somewhere, in the course of her graduate studies, she made the following cute observation.

Consider the following special "marked" dominoes (alongwith an unmarked one)

Call these figures (a), (b), (c) and (d). The marked tiles, (a), (b) and (c) respectievely connect $(x, y)$ to $(x+1, y-1), (x+1, y+1)$ and $(x+2, y)$.

Then Prof Randall makes a nice series of observations beginning with a very simple idea. She first says that if you can tile the board with unmarked dominoes only, then you can trivially put marks on them and obtain a marked tiling.

But a marked tiling is not she is happy with. She is looking for a meaningful marking - a marking which can tell her something about the number of perfect matchings in the above kind of graphs. In short, she establishes a bijection between the number of domino tilings and the number of perfect matchings. The mental gymnastics she went through for this are not very clear to me, but I can try imparting some intuition by "cooking up" the following explanation. Possibly, she arrived at this result by some other genius inventive idea; but the description below should help.

Note The discussion below uses the word domino and tiles interchangeably.

First, let us assume we are on a $n*n$ grid where $n$ is even. (We will discuss the general case for $\RR \subseteq Z^2$ later). Further, to assist our discussion imagine that squares are coloured black and white like they  are in a chessboard. Also, think of your dominoes as all being transparent. Now, put a red dot over the center of the region of the domino which lies over a black square. Let us identify the starting point of a tile as this red dot lying over a black region on the tile.

You can now imagine the tiles as being some sort of "teleporter" carrying the red dot from one tile to the other. They can carry it "horizontally through" the tile as shown in (c), or "diagonally" as in (a) and (b).

[I am not providing any diagrams, but should you need one, you can look here on page 9.]

Thus, you obtain a triangular lattice whose edges correspond to the direction the "teleporter" carried the red dot in. If you can chalk out a simply connected path for red dot starting at some left boundary tile (source) and ending at some right boundary tile (sink), you basically just figured out a tiling for the squares you traversed on the original board.

Thus figuring a simply connected path on the triangular lattice corresponds to figuring out a tiling for the corresponding portion of the chessboard! Figure out a series of such non-intersecting paths, each beginning at some source $s_i$ and ending at some sink $t_i$ such that all the paths are non-intersecting; you win.

(If paths intersect, your tiles overlap - thats why we need them all to be disjoint). The series of paths from $s_i$'s to $t_i$'s is called routing. Thus, the number of domino-tilings of the chessboard is the same as the number of routings! Also, notice that a source-sink pair, $(s_i, t_i)$ is respected by all tilings. That is, if one arbitrary routing has got a set of sources $(s_1, s_2, ..., s_k)$ and a set of sinks $(t_1, t_2,...,t_k)$, all other routings will have the same set of source and sinks. Its easy to see why. If it were not, paths would intersect leading to pathologies (not to mention other disasters like earthquakes, vampires, stinking socks, filth, etc.)

You might have noticed that under the assumption that the region was tilable, the number of sources and sinks is the same. Figure out why on your own. (Its too trivial).

The same analysis extends to any other tilable $\RR \subseteq Z^2$.

But as of now we have not mentioned when is a region tilable. Relax, we are coming to it as well. We would do it using some tools from group theory. Our proof will be a constructive one, if there exist some tilings, it will find one.

Allow me to relax a bit. I will resume posting soon.