32.4 A sampling lemma
Note: also see the paper by Gärtner and Welzl where they outline the general framework a little more concisely.
Let us imagine that we have a set and we sample a random set . Usually sets have specific properties (for example we could have a set of points and be looking for the smallest circle which encloses our points) and it is often interesting to see whether our set retains the properties it has if we add or remove elements from it.
To this end, let us define a function (i.e. for every value maps to some value in the codomain of ). We will define two sets consisting of objects in which have interesting effects when we either add or remove them from .
Let and be as above. Sometimes when we take an element from and add it to , we will find that this causes the output of for to be different than that of . We will call this the set of \sayviolators and define it as
We also may find that sometimes if we remove an element from this will result in a set with a different set of properties than that of . We will call this the set of \sayextreme elements defined as
This is pretty abstract (or at least not very concrete) so let us consider an example.
Consider a set of points and the function defined on the powerset of given by such that is the centre and is the radius of the smallest enclosing circle of the points in (i.e. every point in is either inside or on the edge of this circle). For concreteness, consider the following example (in the diagram directly below) Here the two pink nodes are \sayextreme elements because if we remove them the smallest enclosing circle will shrink. The nodes in black are in but not extreme because removing them has no effect on the smallest enclosing circle.
Let , then violates if and only if is extreme in .
This follows from the definition; if is extreme in then (that is, removing it changes the value of ) and if violates then (as adding to causes the value of to change.
Now it gets a bit more interesting (I would add another Pride and Prejudice quote but I think I added one further up in the document and it is such a boring book that in case anyone else reads my notes I wouldn’t want to subject them to it) as we can advance beyond definitions (a necessary but not sufficient condition for having fun) to some theorems.
Of course, something that many people will naturally be interested (well maybe not many, but there exist at least one) in is how many items we expect to be violators and how many we expect to be extreme elements.
In the abstract setting we are currently residing in this may not seem to be useful, but later (after the theorem) there are some examples (as seems common in mathematics textbooks - not that I would pretend for a moment that this is a textbook, in fact what are you doing reading this document, go read some actual books) one must first present the theorem and then the examples, whereas in discovering this stuff of course people first consider the examples and then make conjectures about their shapes.
Let us fix (which will make life easier). Then let us define and . Then we claim that
We can prove this in (at least) two ways. The first way is using indicator variables. For the random variable let us denote by the function
Then we can write that
The other way to prove this is by defining a bipartite graph such that the vertices of are
and there exists an edge for all of size where violates . Therefore we know that the degree of a node in the left-hand part of the graph - that is all the nodes drawn from the set - is exactly (the number of violators that set has). We also know that the number of edges in the graph is (as is the mean number of items and we multiply it my the total).
Note that edges can also be interpreted as where is extreme in for with . Therefore the degree of each node is (for the same reason as with the violators of ) and the number of edges is .
and by cancelling the factorials, we can see that this indeed implies our desired result.