# Approximate inclusion-Exclusion?

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:

• what is your instance space? concept class? Since we're talking about PAC. Jun 18, 2022 at 19:39
• 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? Jun 20, 2022 at 22:54
• @NealYoung Thanks, that was a mistake! Jun 21, 2022 at 7:42
• 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). Jun 22, 2022 at 21:02