# Sum over products of weighted subset of certain size

Consider a commutative semiring $(R,+,⋅)$. $0$ is the identity for $(R,+)$, and $1$ is the identity for $(R,⋅)$. Let $f,g:V→R$, $w:V→N$ and $Z⊂N$. It is common that we are interested in computing expressions of the following form.

$S⊂V,∑_{x∈S}w(x)∈Z∑ x∈S∏ f(x)x∈V\S∏ g(x)$

Examples:

If $w(x)=1$ for all $x$, and $f(x)$ be the probability that event $x$ occurs, $g=1−f$, we find the probability that the number of event occurs $t$ times, where $t∈Z$. In probability, this is computing the Poisson distribution.

If $(R,+,⋅)=(N,+,⋅)$, $f=g=1$, for all $x$ and $w(x)=x$ and $V⊂N$ and $Z={t}$, then we find the number of subsets that have element sum $t$.

If $(R,+,⋅)=(N,max,+)$, $V⊂N$, $g=0$ and $Z={0,…,W}$, then this solves the knapsack problem with knapsack size $W$, value $f$ and cost $w$.

An actual application inspired this post: An automated test suite that runs $n$ subtests, and it is allowed to rerun a subtest if it fails the first time. A subtest passes if first run passes or the rerun passes. The test is successful if all the subtests passes and the number of total reruns is at most $k$. Assume probability of passing is independent for each subtest. One want to estimate the probability of a successful test given the probability a run passes for a specific subtest.

Let $maxZ=k$ and $∣V∣=n$. The naive algorithm runs in $O(n2_{n})$ time (assuming semiring operation takes $O(1)$ time). There is a common transformation that turns this problem that sum over all subsets to a problem that sums over $Z$. So it runs in $O(nk)$ time.

Let $V={v_{1},…,v_{n}}$ and $V_{j}={v_{1},…,v_{j}}$. Define $D(i,j)=S⊂V_{j},∑_{x∈S}w(x)=i∑ x∈S∏ f(x)x∈V\S∏ g(x)$.

Certainly, $S⊂V,∑_{x∈S}w(x)∈Z∑ x∈S∏ f(x)x∈V\S∏ g(x)=i∈Z∑ D(i,n)$

We only incur a $O(k)$ number of semiring operations once we compute all $D(i,n)$ for $0≤i≤k$.

Let $[P]$ be the Iverson bracket notation, namely

$[P]={10 ifPis true;otherwise. $

- $D(i,0)=[i=0]$
- For $j≥1$, $D(i,j)=[i≥w(v_{j})]f(v_{j})D(i−w(v_{j}),j−1)+g(v_{j})D(i,j−1)$.

The base case can be verified easily, we show part of a inductive step.

$f(v_{j})D(i−w(v_{j}),j−1)+g(v_{j})D(i,j−1) =f(v_{j})S⊂V_{j−1},∑_{x∈S}w(x)=i−w(v_{j})∑ x∈S∏ f(x)x∈V\S∏ g(x)+g(v_{j})S⊂V_{j−1},∑_{x∈S}w(x)=i)∑ x∈S∏ f(x)x∈V\S∏ g(x)=v_{j}∈S⊂V_{j},∑_{x∈S}w(x)=i∑ x∈S∏ f(x)x∈V\S∏ g(x)+v_{j}∈S⊂V_{j},∑_{x∈S}w(x)=i∑ x∈S∏ f(x)x∈V\S∏ g(x)=S⊂V_{j},∑_{x∈S}w(x)=i∑ x∈S∏ f(x)x∈V\S∏ g(x) $