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

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)$$?

• You may be able to use an adversary argument to show an $\Omega(2^n)$ lower bound. You could try to "hide" one instance of $\prod p_{i,b} < \epsilon$ such that it can only be precisely determined after $\sim 2^n$ queries. You could create a query model such that they submit some amount of $p_{i,b}$'s to you and you return the product or value if there is only 1.
– ryan
Commented Apr 16, 2019 at 18:05

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).