diff options
| -rw-r--r-- | brainstorm/results.tex | 9 |
1 files 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. |