0
$\begingroup$

I am trying to understand or find literature on the following problem of approximate inclusion exclusion.

Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ have the cardinality $\alpha_k$. Then using principle of inclusion-exclusion, we have that: $$\textstyle\left|\bigcup_{i=1}^{m}A_i\right| = \sum_{k=0}^{m}(-1)^{k-1}\binom{m}{k}\alpha_k$$

The problem:

Given an probabilistically approximately correct estimate of each $\alpha_k$, say $\bar{\alpha}_k$. I.e. $$\mathrm{Pr}(|\alpha_k - \bar{\alpha}_k| \leq \epsilon \alpha_k) \geq 1-\delta$$ For some $0 <\epsilon <1$ and $0 <\delta <1$.With som abuse of notation, I denote $|\cup_{i=1}^{m}A_i|$ as $|S|$. And I denote $\sum_{k=0}^{m}(-1)^{k-1}\binom{m}{k}\bar{\alpha}_k$ as $|\bar{S}|$ (Not that, $|\bar{S}|$ is my estimate for $|S|$). I would like to understand if there exist any gaurentees of the type:

$$Pr[| |S| - |\bar{S}| |\leq \epsilon |S| ] > 1-\delta$$

Adjacent but not exactly the same problems:

  1. Paper 1
  2. Paper 2
Improve this question
$\endgroup$
4
  • $\begingroup$ what is your instance space? concept class? Since we're talking about PAC. $\endgroup$
    – Aryeh
    Jun 18, 2022 at 19:39
  • 1
    $\begingroup$ You've asked whether there is a guarantee of the type $$\Pr[| |S| - |\bar{S}| |\geq \epsilon |S| ] > 1-\delta.$$ Have you reversed an inequality there? $\endgroup$
    – Neal Young
    Jun 20, 2022 at 22:54
  • $\begingroup$ @NealYoung Thanks, that was a mistake! $\endgroup$
    – SagarM
    Jun 21, 2022 at 7:42
  • $\begingroup$ It seems you need some stronger assumptions to get any such bound. E.g. consider $S=A_i = \emptyset$ for $i\in[m]$, so $\alpha_k = 0$ for all $k$. Choose a $k'$ uniformly at random in $[m]$ and set $\overline \alpha_{k'} = 1$, while setting all other $\overline \alpha_{k} = 0$. Then, for any $k\in [m]$, $\Pr[|\alpha_k - \overline \alpha_k| = 0] = 1-1/m$, but $\Pr[|S| = |\overline S|] = 0$ (for example). $\endgroup$
    – Neal Young
    Jun 22, 2022 at 21:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.