ε-net

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

Let $P$ be a probability distribution over some set $X$ . An $\varepsilon$ -net for a class $H \subseteq 2^X$ of subsets of $X$ is any subset $S \subseteq X$ such that for any $h \in H$

$P(h) \ge \varepsilon \quad \Longrightarrow \quad S\cap h \neq \varnothing.$

Intuitively $S$ approximates the probability distribution.

A stronger notion is $\varepsilon$ -approximation. An $\varepsilon$ -approximation for class $H$ is subset $S \subseteq X$ such that for any $h \in H$ it holds

$\left| P(h) - \frac{|S \cap h|}{|S|} \right| < \varepsilon$