Now here is something quite cool. The probabilistic method.
The idea is this, in glib summary, that you prove something exists by proving that the probability of it existing is greater than 0, or that the probability of it not existing is less than one.
There are many different ways to approach this really, though they all amount to the same thing. You consider a distribution of mathematical objects, and you're interested in one with a particular property. You imagine picking one of those objects from that random distribution, and show that the probability of picking the one your after, or one of the type your after, is greater than zero, or the probability of not picking it is less than one. The idea is that if there is a probability of you picking it, then it must exist /somewhere/ in the set. You don't know where, but it's got to be there somewhere or you would have no probability of finding it.
It's rather silly in many ways. For example, even though you prove that something exists, especially in this way, gives you no insight into how to find it. It's completely non-constructive, but the logic of the approach is irrefutable.
But I suppose it is best taught by example.
First off, a bit on graph theory.
A graph is a collection of things. Objects. They can be ... most anything really. These are called vertices. The important part of the graph is that it also contains connections, or edges between the vertexes. A good example is a map. A map can be modeled as a graph, were the vertices are cities and edges the roads between them. But the idea of a graph can be extended and used to apply to many things. As such, it's useful to study the abstract model of a graph, because any insights can then be applied to anything you can model with graphs.
There are many nice questions you can ask about graphs. For example, graph colorings. Suppose you are going give each vertex of a graph a color. However, you don't want to connect any vertex to be connected to a vertex of the same color. For a given graph, what is the minimum number of colors needed to color it?
That's actually a really interesting example. A quite famous ... issue ... in mathematics is the four color theorem. The idea is that given a map, any map, you can color the countries on the map such that no country is touching a country of the same color, with no more than four colors. This is actually a graph coloring question. The idea is you model each country as a vertex in your graph, and create edges between countries that touch each other. The problem is completely generalizable to graph theory. The nice thing about this is that you've taken a problem that can be overly complicated due to borders of countries being strange shapes, and all kinds of bizarre geometries, and turned it into something much more straight forward, a set of vertexes and connections between them. That is the beauty of abstract mathematics.
For those interested in reading further, MarkCC has an excellent set of posts on graph theory. Unfortunately the link lists them in reverse chronological orders, so for introductory graph theory posts you have to scroll all the way to the bottom and work your way up. Have at it :)
But the problem I would like to address, with the probabilistic method, is that of dominating sets.
Here we have a graph. Please excuse the crudeness.
Notice how one of the edges in this graph overlaps another, without a vertex between. This ok. The only think that matters about edges is the two vertices they connect. The more complicated the graph, the harder it is to draw sensibly on a surface like that.
However, a dominating set is a set of vertices such that anything not in the set is connected to something in the set. For example, the set of all vertices in the graph is a dominating set because anything not in the set (which is nothing) is connected to something in the set. Below, I've circled vertices that compose a dominating set.
A given graph can have multiple dominating sets. A interesting question then is what is the size of the smallest dominating set for a given graph?
For this exercise, I'm going to limit myself to r-regular graphs. An r-regular graph is a subtype of graph such that any vertex is necessarily connected to r many other vertexes. So, the question is this:
Given an r-regular graph, what is the size of the smallest dominating set?
And we're going to use the probabilistic method! The one you've been waiting for.
Consider a random graph. That is to say, we have n vertices, and we are, at random, going to construct edges between them, with no restriction other than that the resultant graph is r-regular.
Next we're going to perform an experiment. We're going to consider each of the n vertices, and with probability p, we are going to add them to set S1. After this is done, there should be, on average, p*n many elements in set S1, and (1 - p)*n vertexes remaining.
Next, we go through the remaining (1 - p)*n vertexes. Considering each vertex, if there is /not/ an edge connecting it to something in S1, we add it to S2. After this, all the remaining vertices not in S1 or S2 will be connected to something in S1.
So then consider the set S as the union of sets S1 and S2. S is a dominating set of the graph.
Note that any dominating set of the graph can be constructed in this way. Assume that the graph has a given dominating set. In the first step of our experiment, there is every possibility that every vertex in that dominating set will be added to S1. On average, there will be n*p elements in S1, but it can happen that exactly the vertices of a dominating set are added to S1. In that case, since everything else is connected to S1, S2 will be empty, and S = S1, a dominating set.
What we are going to look at though is, performing this experiment, on average how big will the resultant dominating set be?
So we want to consider what the expected size of S is. We know that S1 and S2 share no elements, because S2 taken from the vertices not in S1. As such, we know that the size of S is the size S1 plus the size of S2.
S1 will contain, on average, n*p vertices.
But what's the expected size of S2? It's chosen from a population of (1 - p)*n vertices. But, given an element from that population, we'll call it w, what is the probability that it is added to S2? That is, the probability that it is not connected to anything in S1.
So, given a single vertex w, what is the probability that it is not connected to S1?
A given element of S1, u, what is the probability that u is not connected to w? We know that u is connected to r many things. The probability that any one of them is w is 1/(n - 1), because w is one out of the n - 1 remaining vertices. So the probability that u connects to w is r/(n - 1). Therefore the probability that u is /not/ connected to w is 1 - r/(n - 1).
But that is for one element of S1. We want all elements of S1 not connected to w. The probability of this occurring is given by
Therefore, the expected size of S, the generated dominating set, is given by
That expression there is the fruit of our probabilistic labors. But now what can we do with it? Suppose for example we have that p = 1/2, so elements are inserted into S1 initially with a 50% chance. Then we have
Looking at the above expression,
What does this mean? If the expected size is a given value, then there must be a dominating set with size less than that which has some probability of occuring. What this says then is that there exists a dominating set whose size is at most n/2*(all that stuff). What this shows then is that, for any r-regular graph with n vertices, the minimum dominating set will have size less than or equal to n/2*(stuff).
Can we improve this, though? The idea is, can we modify our experiment to produce a better result. The only parameter we have to play with, without changing the actual structure of our experiment, is p. By choosing appropriate values of p, we can minimize the expression for the expected value of the size of the dominating set. Minimizing that, as before, since that is the expected size of the dominating set, there must be dominating sets with size less than or equal that.
But how do we know that this approach is valid, really? Well, we can test it for known cases. For example, consider a graph of r + 1 vertices, where each vertex is connected to every other vertex. Clearly this fits the r-regular restriction. In this case also, a single vertex is a dominating set, because all vertices are connected to every other vertex. But what does our expression give in that case? Letting n = r + 1,
Note, if we had chosen that p = 1/(r + 1), the expected size of the dominating set would be 1, which confirms what we already knew, the graph has a dominating set of size 1.
So ideally, we want to strictly minimize our expression with respect to p. One way to do this would be the typical calculus approach, finding the zeros of the derivative with respect to p. Unfortunately this produces an absolutely unintelligible, unsimplifiable mess, albeit a very nice upper bound on the size of the minimum dominating set. Given actual values of r and n, one can use that formula to calculate an explicit upper bound, but the general formula is rather ugly and uninteresting.
However, in general, choosing a near optimal p value,
Which gives a much nicer upper bound, though not quite as tight as I would like. I'll leave that as an exercise to the interested reader.
But what have we accomplished here, really? If you take the above inequality as true, and I do think it is, we've shown that for any r-regular graph with n vertices, it contains a dominating set of size less than or equal to (1 + Ln(r))/r*n. Because we started our experiment with a general r-regular graph, this holds true across all r-regular graphs. Notice though, we have made no assumptions or declarations about that dominating set, except proving that it exists.
And that is the probabilistic method. Given a random distribution of objects, you prove that the probability of getting it is greater than 0. Therefore it must exist in the distribution, and it must exist period.
I really like this. I often think of myself as a math experimentalist, and this kind of approach, setting up an 'experiment' and looking at the implications of the outcomes rather appeals to me.
Anyway. I hope that was informative. And that I didn't muck anything up.
|