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
  • $\begingroup$ what is your instance space? concept class? Since we're talking about PAC. $\endgroup$
    – Aryeh
    Commented 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
    Commented Jun 20, 2022 at 22:54
  • $\begingroup$ @NealYoung Thanks, that was a mistake! $\endgroup$
    – SagarM
    Commented 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
    Commented Jun 22, 2022 at 21:02


Your Answer

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