e-net (probability theory)

For other uses, see Ε-net.

An $\varepsilon$-net is any of several related concepts in mathematics, and has a particular meaning in probability theory where it is used to describe the approximation of one probability distribution by another.

Theory

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)\geq \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 a subset $S\subseteq X$ such that for any $h\in H$ it holds

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