<p>I am trying to understand or find literature on the following problem of approximate inclusion exclusion.</p>
<p>Let <span class="math-container">$S:=\{A_i\}_{i=1}^{m}$</span> be a set of <span class="math-container">$m$</span> sets. Every intersection of <span class="math-container">$k$</span> elements in <span class="math-container">$S$</span> have the cardinality <span class="math-container">$\alpha_k$</span>. Then using principle of inclusion-exclusion, we have that:
<span class="math-container">$$\textstyle\left|\bigcup_{i=1}^{m}A_i\right| = \sum_{k=0}^{m}(-1)^{k-1}\binom{m}{k}\alpha_k$$</span></p>
<p>The problem:</p>
<p>Given an probabilistically approximately correct estimate of each <span class="math-container">$\alpha_k$</span>, say <span class="math-container">$\bar{\alpha}_k$</span>. I.e.
<span class="math-container">$$\mathrm{Pr}(|\alpha_k - \bar{\alpha}_k| \leq \epsilon \alpha_k) \geq 1-\delta$$</span>
For some <span class="math-container">$0 &lt;\epsilon &lt;1$</span> and <span class="math-container">$0 &lt;\delta &lt;1$</span>.With som abuse of notation, I denote <span class="math-container">$|\cup_{i=1}^{m}A_i|$</span> as <span class="math-container">$|S|$</span>. And I denote <span class="math-container">$\sum_{k=0}^{m}(-1)^{k-1}\binom{m}{k}\bar{\alpha}_k$</span> as <span class="math-container">$|\bar{S}|$</span> (Not that, <span class="math-container">$|\bar{S}|$</span> is my estimate for <span class="math-container">$|S|$</span>). I would like to understand if there exist any gaurentees of the type:</p>
<p><span class="math-container">$$Pr[| |S| - |\bar{S}| |\leq \epsilon |S| ] &gt; 1-\delta$$</span></p>
<p>Adjacent but not exactly the same problems:</p>
<ol>
<li><a href="https://www.cs.huji.ac.il/%7Enati/PAPERS/approx_incl_excl.pdf" rel="nofollow noreferrer">Paper 1</a></li>
<li><a href="https://link.springer.com/article/10.1007/BF01271266?noAccess=true" rel="nofollow noreferrer">Paper 2</a></li>
</ol>

CC BY-SA 4.0
2022-06-18T19:39:03.400Z
what is your instance space? concept class? Since we're talking about PAC.
Aryeh
CC BY-SA 4.0
2022-06-20T22:54:12.327Z
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?
Neal Young
CC BY-SA 4.0
2022-06-21T07:42:51.420Z
@NealYoung Thanks, that was a mistake!
SagarM
CC BY-SA 4.0
2022-06-22T21:02:32.627Z
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).
Neal Young
<approximation-algorithms><counting-complexity><set-cover><approximation>
Approximate inclusion-Exclusion?
SagarM
# Approximate inclusion-Exclusion?

(Asked by: username_0 on 2022-06-16)

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](https://www.cs.huji.ac.il/%7Enati/PAPERS/approx_incl_excl.pdf)
2. [Paper 2](https://link.springer.com/article/10.1007/BF01271266?noAccess=true)

**Tags:** approximation-algorithms, counting-complexity, set-cover, approximation

> **Comments:**
> **username_1**: what is your instance space? concept class? Since we're talking about PAC.  
> **username_2**: 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?  
> **username_0**: @NealYoung Thanks, that was a mistake!  
> **username_2**: 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).  

---

## 0 answers

