From 54cac035f77c8c617ae666790f6efca8c61d047a Mon Sep 17 00:00:00 2001 From: Jean Pouget-Abadie Date: Tue, 14 Apr 2015 18:47:29 -0400 Subject: fixing typo --- brainstorm/results.tex | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/brainstorm/results.tex b/brainstorm/results.tex index 0b37049..6f2dc6d 100644 --- a/brainstorm/results.tex +++ b/brainstorm/results.tex @@ -662,14 +662,15 @@ $$\mathbb{P}_{S_1, \dots S_m \sim {\cal D}}\left(\mathbb{P}_{\hat S} The previous proposition can be reformulated in the slightly weaker formulation which is more intuitive: -$$\mathbb{P}_{S_1, \dots S_m \sim {\cal D}}\left(\mathbb{E}(f(\hat S)) \geq +$$\mathbb{P}_{S_1, \dots S_m \sim {\cal D}}\left(\mathbb{E}(f(\hat S)) \leq \frac{1}{n}OPT \right) \geq 1 - \frac{n^C}{2f(n)} \rightarrow 1 \text{ when } n \rightarrow +\infty$$ Note that the restriction on ${\cal D}$ is verified by many distributions. In -the case of the uniform distribution $ = \frac{1}{2^{n-1}}$ and in the case of -observing all sets of size $k>1$ uniformly at random: $=0$ This example is not -fully satisfying for two reasons: +the case of the uniform distribution $ \mathbb{P}(\{A_1\}) + \mathbb{P}(\{A_2\}) += \frac{1}{2^{n-1}}$ and in the case of observing all sets of a certain fixed +size $k>1$ uniformly at random: $\mathbb{P}(\{A_1\}) + \mathbb{P}(\{A_2\})= 0$ +This example is not fully satisfying for two reasons: \begin{itemize} \item the coverage function is not monotone. -- cgit v1.2.3-70-g09d2