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

Definition 32.4.1

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

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 $s$ from $R$ this will result in a set $R-\{s\}$ with a different set of properties than that of $R$ . We will call this the set of \sayextreme elements $X$ defined as

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

Lemma 32.4.1

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

This follows from the definition; if $s$ is extreme in $R\cup\{s\}$ then $\phi\left(R\cup\{s\}\right)\neq\phi(R)$ (that is, removing it changes the value of $\phi$ ) and if $s$ violates $R$ then $\phi(R)\neq\phi(R\cup\{s\})$ (as adding $s$ to $R$ causes the value of $\phi$ to change.

$\Box$

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$ (which will make life easier). Then let us define $v_{r}:=\operatorname{E}[|V(R)|]$ and $x_{r}:=\operatorname{E}[|X(R)|]$ . Then we claim that

\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 $X$ let us denote by $[X]$ the function

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

(32.18)

Then we can write that

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

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

V:=\binom{S}{r}\cup\binom{S}{r+1}

(32.23)

and there exists an edge $\{R,R\cup\{s\}\}$ for all $R\subseteq S$ of size $r$ where $s$ violates $R$ . 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 $\binom{S}{r}$ - is exactly $|V(R)|$ (the number of violators that set has). We also know that the number of edges in the graph is $\binom{n}{r}v_{r}$ (as $v_{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\}$ where $s$ is extreme in $Q$ for $Q\subseteq S$ with $|Q|=r+1$ . Therefore the degree of each node $Q$ is $|X(S)|$ (for the same reason as with the violators of $R$ ) and the number of edges is $\binom{n}{r+1}x_{r+1}$ .

Therefore

\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.