Inverse formula for counting marginals

2010-09-28T20:57:52Z

I am interested in a formula which relating two functions over a multiset.

I have a multiset $X$ of sets where each element in $X$ is a set $x \subseteq \{1,2,\ldots,m\}$. Now I have two ``count'' functions

$p_s = |\{x \in X : s = x\}|$

$\eta_s = |\{x \in X : s \subseteq x\}|$

One can expand the formula for the marginal count $\eta_s$ as

$\eta_s = \sum_{s \subseteq t,|t|\leq m} p_t$

I have confirmed for up to $m = 4$ that the following results holds

$p_s = \sum_{s \subseteq t,|t|\leq m} (-1)^{|s|-|t|}\eta_t$

Does the above result hold for arbitrary $m$? This seems like it must be related to the inclusion/exclusion principle (http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) but there is a subtle difference, in that the summation is over set which include $s$ as subsets. Perhaps this difference is immaterial, but I don't see the argument just yet. Also, in the general problem that I wish to solve I will have $x \subseteq \{(i,a_i)\}_{i \in I}$ where $I$ is all combinations of $\{1,\ldots,m\}$ and $a_i$ is drawn from a finite set $A:|A|=n$.

Answer by Yaroslav Bulatov for Inverse formula for counting marginals

2010-09-28T21:15:25Z

The answer is yes, and this is known as Moebius inversion. See Section E.1, p.286 in Graphical models, exponential families, and variational inference.

Inverse formula for counting marginals - MathOverflow

Inverse formula for counting marginals

Answer by Yaroslav Bulatov for Inverse formula for counting marginals