Time complexity of a problem in probabilistic inference on a Bayesian network

Question

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

We would like to find the probability of the joint event $E$ that both (i) all $y_k$ are 1 and (ii) the total assignment of states on the network has a probability above $\epsilon$.

Is exponential time required to compute the probability of $E$, and if so (or not), how do we prove this?

---

In case it is helpful, let me give a low-$n$ example:

Suppose $n = 3$. If we just want to compute the probability of (i), then this is $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0}p_{2,0}p_{3,0} + p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,0} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,0}p_{3,1} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$ We can factor the right-hand side so that rather than a sum of $2^3$ terms we just have a product of $3$ factors: $$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0} + p_{1,1})(p_{2,0} + p_{2,1})(p_{3,0} + p_{3,1}).$$ This reduces our computational time from $O(2^n)$ to $O(n)$ (as shown here for arbitrary $n$).

However, now consider the case that the terms $p_{1,0}p_{2,0}p_{3,0}$, $p_{1,0}p_{2,1}p_{3,0}$, and $p_{1,1}p_{2,0}p_{3,1}$ are quite small -- each less than $\epsilon$ -- and we would like our overall probability to 'ignore' such small terms. Then we want to compute: $$\Pr(E) = 2^{-3}(p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$

Of course, no generalizable factorization seems possible for the right-hand side. This motivates the above question: how can we prove (or disprove) that computing $\Pr(E)$ in the case of arbitrary $n$, $p_{k,0}$, $p_{k,1}$, and $\epsilon$ is indeed $\Omega(2^n)$?

Answer 1

Your problem is equivalent to:

Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$
Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $\sum_i a_i x_i \ge t$.

I think this problem is #P-complete, so you shouldn't expect any polynomial-time algorithm for computing it exactly.

Let me explain why. Let $\ell(x,y)$ denote the likelihood of the states $x,y$, $\ell(x) = \ell(x,1^n)$, and $L(x) = \log \ell(x)$ its log-likelihood. Then $L(x)$ has the form

$$L(x) = -n \log 2 + \sum_i \log p_{i,x_i}.$$

An assignment $x,1^n$ satisfies $E$ iff $L(x) \ge \log \epsilon$. Note that

$$\log p_{i,x_i} = \log p_{i,0} + x_i (\log p_{i,1} - \log p_{i,0}).$$

Letting $a_i = \log p_{i,1} - \log p_{i,0}$, we have

$$\sum_i \log p_{i,x_i} = \sum_i \log p_{i,0} + \sum_i a_i x_i.$$

If we now let $t = \log \epsilon + n \log 2 - \sum_i \log p_{i,0}$, we find that $x$ satisfies $E$ iff $\sum_i a_i x_i \ge t$. So, given $t$, we want to compute the probability that a random chosen $x$ satisfies $\sum_i a_i x_i \ge t$. This is equivalent to counting the number of $x$'s that satisfy $\sum_i a_i x_i \ge t$.

According to https://cstheory.stackexchange.com/q/19758/5038, this problem is #P-complete, so you shouldn't expect to find any polynomial time algorithm to compute the answer exactly.

However, there are techniques for approximating it: for instance, you could use algorithms for estimating the number of lattice points in a convex polytope (see, e.g., https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf) or computing them exactly in super-polynomial time (https://cstheory.stackexchange.com/q/22280/5038, https://cstheory.stackexchange.com/a/6464/5038).