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 SS and we sample a random set RSR\subseteq S. 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 ϕ:𝒫(S)ϕ(S)\phi:\mathcal{P}(S)\to\phi(S) (i.e. for every value RSR\subseteq S ϕ\phi maps RR to some value in the codomain of ϕ\phi). We will define two sets consisting of objects in SS which have interesting effects when we either add or remove them from RR.

Definition 32.4.1

Let SS and ϕ\phi be as above. Sometimes when we take an element ss from SRS-R and add it to RR, we will find that this causes the output of ϕ\phi for R{s}R\cup\{s\} to be different than that of RR. We will call this the set of \sayviolators and define it as

V(R):={sSR:ϕ(R{s})ϕ(R)}.V(R):=\{s\in S-R:\phi(R\cup\{s\})\neq\phi(R)\}. (32.15)
Definition 32.4.2

We also may find that sometimes if we remove an element ss from RR this will result in a set R{s}R-\{s\} with a different set of properties than that of RR. We will call this the set of \sayextreme elements XX defined as

X(R):={sR:ϕ(R{s})ϕ(R)}.X(R):=\{s\in R:\phi(R-\{s\})\neq\phi(R)\}. (32.16)

This is pretty abstract (or at least not very concrete) so let us consider an example.

Example 32.4.1

Consider a set of points P2P\subseteq\mathbb{R}^{2} and the function CC defined on the powerset of PP given by C(X)=(c,r)C(X)=(c,r) such that cc is the centre and rr is the radius of the smallest enclosing circle of the points in PP (i.e. every point in PP 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 RR but not extreme because removing them has no effect on the smallest enclosing circle.

Lemma 32.4.1

Let sSs\in S, then ss violates RR if and only if ss is extreme in R{s}R\cup\{s\}.

This follows from the definition; if ss is extreme in R{s}R\cup\{s\} then ϕ(R{s})ϕ(R)\phi\left(R\cup\{s\}\right)\neq\phi(R) (that is, removing it changes the value of ϕ\phi) and if ss violates RR then ϕ(R)ϕ(R{s})\phi(R)\neq\phi(R\cup\{s\}) (as adding ss to RR causes the value of ϕ\phi 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.

Theorem 32.4.1

Let us fix |R|=r|R|=r (which will make life easier). Then let us define vr:=E[|V(R)|]v_{r}:=\operatorname{E}[|V(R)|] and xr:=E[|X(R)|]x_{r}:=\operatorname{E}[|X(R)|]. Then we claim that

vrnr=xr+1r+1\frac{v_{r}}{n-r}={x_{r+1}}{r+1} (32.17)

We can prove this in (at least) two ways. The first way is using indicator variables. For the random variable XX let us denote by [X][X] the function

[X]:={1iff X0otherwise[X]:=\begin{cases}1&\text{iff $X$}\\ 0&\text{otherwise}\end{cases} (32.18)

Then we can write that

(nr)vr\displaystyle\binom{n}{r}v_{r} =R(Sr)sSR[s violates R]\displaystyle=\sum_{R\in\binom{S}{r}}\sum_{s\in S-R}\text{[$s$ violates $R$]} (32.19)
=R(Sr)sSR[s extreme in R{s}]\displaystyle=\sum_{R\in\binom{S}{r}}\sum_{s\in S-R}\text{[$s$ extreme in $R% \cup\{s\}$]} (32.20)
=Q(Sr+1)sQ[s is extreme in Q]\displaystyle=\sum_{Q\in\binom{S}{r+1}}\sum_{s\in Q}\text{[$s$ is extreme in $% Q$]} (32.21)
=(nr+1)xr+1\displaystyle=\binom{n}{r+1}x_{r+1} (32.22)

The other way to prove this is by defining a bipartite graph GG such that the vertices of GG are

V:=(Sr)(Sr+1)V:=\binom{S}{r}\cup\binom{S}{r+1} (32.23)

and there exists an edge {R,R{s}}\{R,R\cup\{s\}\} for all RSR\subseteq S of size rr where ss violates RR. 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(Sr)\binom{S}{r} - is exactly |V(R)||V(R)| (the number of violators that set has). We also know that the number of edges in the graph is (nr)vr\binom{n}{r}v_{r} (as vrv_{r} is the mean number of items and we multiply it my the total).

Note that edges can also be interpreted as {Q{s},Q}\{Q-\{s\},Q\} where ss is extreme in QQ for QSQ\subseteq S with |Q|=r+1|Q|=r+1. Therefore the degree of each node QQ is |X(S)||X(S)| (for the same reason as with the violators of RR) and the number of edges is (nr+1)xr+1\binom{n}{r+1}x_{r+1}.


(nr)vr=(nr+1)xr\binom{n}{r}v_{r}=\binom{n}{r+1}x_{r} (32.24)

and by cancelling the factorials, we can see that this indeed implies our desired result.