Inverse formula for counting marginals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T10:54:47Z http://mathoverflow.net/feeds/question/40383 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40383/inverse-formula-for-counting-marginals Inverse formula for counting marginals Gabriel Mitchell 2010-09-28T20:57:52Z 2010-09-28T21:15:25Z <p>I am interested in a formula which relating two functions over a multiset. </p> <p>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> <p>$p_s = |\{x \in X : s = x\}|$</p> <p>$\eta_s = |\{x \in X : s \subseteq x\}|$</p> <p>One can expand the formula for the marginal count $\eta_s$ as</p> <p>$\eta_s = \sum_{s \subseteq t,|t|\leq m} p_t$</p> <p>I have confirmed for up to $m = 4$ that the following results holds</p> <p>$p_s = \sum_{s \subseteq t,|t|\leq m} (-1)^{|s|-|t|}\eta_t$</p> <p>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$.</p> http://mathoverflow.net/questions/40383/inverse-formula-for-counting-marginals/40384#40384 Answer by Yaroslav Bulatov for Inverse formula for counting marginals Yaroslav Bulatov 2010-09-28T21:15:25Z 2010-09-28T21:15:25Z <p>The answer is yes, and this is known as Moebius inversion. See Section E.1, p.286 in <a href="http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf" rel="nofollow">Graphical models, exponential families, and variational inference.</a></p>