6
$\begingroup$

Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least $0.5$. What is the computational complexity of this decision problem, when $p_1,\ldots,p_n$ and $t$ are represented in binary and given as input?

More generally, I'm interested in the generalization of this problem to (non-Bernoulli) discrete distributions. Specifically, there are $n$ independent random variables, each supported on at most $m$ rational numbers, with each variable's probability histogram given explicitly in the input. In this case, also, I want to decide whether the sum of these variables exceeds $t$ with probability at least $0.5$.

I have a feeling this problem is PP-hard, though I can't quite prove it. I wonder what the answer is, and whether it's already known.

Note that I'm not looking for approximation algorithms for this problem. It's clear that monte carlo methods yield positive answers to approximate versions of this decision problem. I'm interested in the exact decision problem as stated above.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ As stated, the Bernoulli version has a straightforward dynamic programming solution since the sum takes only a polynomial set of values. This lets you compute $P(p_1 + \cdots + p_k = s)$ by induction on $k$ and $s$. $\endgroup$ – Geoffrey Irving Jan 21 '15 at 2:33
  • 3
    $\begingroup$ NP-hard, at least.. The following variant of SUBSET-SUM reduces to your general problem: given $n$ positive integers $X=(x_1, x_2, \ldots, x_n)$, does any subsequence of $X$ sum to exactly $t=\sum_{i=1}^n x_i/2$? The reduction: create an $n$-variable instance where the $i$th r.v. is $x_i$ with prob. 1/2 and 0 otherwise. The answer to this instance is 'yes' iff at least half the subsequences of $X$ sum to more than $t$. If a subsequence $S$ sums to more than $t$, its complement $X-S$ sums to less than $t$, so the answer is 'yes' iff $X$ has no subsequence that sums to exactly $t$. $\endgroup$ – Neal Young Jan 21 '15 at 5:49
  • $\begingroup$ You are both right. The Bernoulli version is (obviously in retrospect) in P, and the general version is NP-hard. I did some more digging and came up with an answer to my own question: it is in fact PP-hard, as it is simply a generalization of the #P-hard problem #Knapsack. Oh well... $\endgroup$ – sd234 Jan 22 '15 at 0:52
  • $\begingroup$ @srd: could you perhaps provide us with the references that you dug up? $\endgroup$ – Gamow Jan 22 '15 at 12:05
  • $\begingroup$ Sure. I'll post a thorough answer below. FYI, I meant #P hard rather than PP hard in my above comment. $\endgroup$ – sd234 Jan 23 '15 at 5:27
3
$\begingroup$

The general (non-bernoulli) problem is #P hard, via a reduction from #Knapsack.

#Knapsack is the problem of counting the solutions to an instance of the knapsack problem. This problem is known to be #P complete. An equivalent way to think of the #Knapsack problem is the following: You are given a set of integers $a_1,\ldots,a_n$ and a threshold $t$. Let $x_i$ be a random variable which is either $0$ or $a_i$ with equal probability, and assume those random variables are independent. Compute the probability that $\sum_i x_i \leq t$.

It is not too hard to see that the #Knapsack problem could be equivalently defined as the problem of computing the probability that $\sum_i x_i \geq t$ (simply flip the sign of all the integers and add a large constant). Therefore, had I stated my problem with an arbitrary probability $p$ rather than $0.5$, the problem stated in the question can be interpreted as the decision version of #knapsack. A reduction of #knapsack to its decision version via binary search would then complete the #P hardness proof.

The way I defined the problem, however, fixed a particular threshold 0.5. It's not too hard to see that this doesn't make the problem easier. We can reduce the decision problem with probability $p\leq 0.5$ to the problem with $p=0.5$ by simply adding an additional random variable $x_0$ which is equal to the threshold $t$ with probability $\frac{0.5-p}{1-p}$ and $0$ the rest of the time. For $p > 0.5$, a similar reductions lets $x_0$ be $-M$ for a sufficiently large $M$ with probability $\frac{p-0.5}{p}$ and $0$ otherwise; if you don't like negative numbers, simply shift all random variables and the threshold $t$ up by a suitable constant.

Improve this answer
$\endgroup$
-2
$\begingroup$

A polynomial time and space algorithm exists for the sum of any discrete independent R.V. Let $x_1+ ...+ x_n$ be the sum of independent variables. Working incrementally: $Z_2=X_1+X_2$ Then

$P(Z_2=z)=\sum_{i=-\infty}^{+\infty} P(X_1=i) \cdot P(X_2=z-i) $

This is by definition the convolution of the two distributions (denoted by *)

$P_{z_2}= P_{x_1} * P_{x_2}$

The vectors $P_{x_1} , P_{x_2}$ are zero padded to the length $L$ of the sum of their lengths.

Using the convolution theorem

$ P_{z_2}={\mathcal {F}}^{{-1}}{\big \{}{\mathcal {F}}\{P_{x_1}\} \cdot{\mathcal {F}}\{P_{x_1}\}{\big \}}$

Computing the fourier and inverse fourier transforms using FFT is an $O(L log L)$ operation, and the element-wise product requires $L$ operations. all in all, the "combination" of the r.vs into the distribution of their sum takes $O(L log L)$ time.

Computing the distributions of the sums of n variables is computed iteratively: Let $Z_k=X_1+...+X_k$. Then

$P_{z_n}=P_{z_{n-1}}*P_{x_n}$

For $n$ variables this takes approximately $O(n^2)$ time.

Given that the pdf is computed, the cdf is a trivial $O(n)$ operation.

Improve this answer
$\endgroup$
  • $\begingroup$ Your running time analysis is not correct. The running time depends on the range of possible values for the $x_i$'s, and on the maximum possible value of $x_1+\dots + x_n$. You haven't taken that into account. You need to choose $L$ to be at least that value, and that will impact the running time. For Bernoulli r.v.'s the running time will indeed be polynomial, but for other r.v.'s it won't necessarily be. $\endgroup$ – D.W. Jun 28 '16 at 9:26
  • $\begingroup$ You are correct. More precisely off the top of my head is $ O(L log ( L n) n^2 )$ however the whole point was to provide with a Polynomial algorithm w.r.t. n, which is the original question as I understood it. $\endgroup$ – Manos Orfanoudakis Jun 30 '16 at 6:18
  • $\begingroup$ Not quite. The complexity of a problem is defined as a function of the length of the input (in bits). So, we need to ask whether there is an algorithm that is polynomial in the length of the input (not polynomial in $n$). The length of the input is $n \lg L$. An algorithm with running time $O(L n^2)$ is not polynomial in the length of the input; that's exponential in $\lg L$ and thus effectively exponential in the length of the input (when $L$ is large). $\endgroup$ – D.W. Jun 30 '16 at 6:28
  • $\begingroup$ This is effectively the difference between a polynomial vs pseudo-polynomial algorithm; subset sum is NP-complete even though there is a pseudo-polynomial algorithm for it. $\endgroup$ – D.W. Jun 30 '16 at 6:30
  • $\begingroup$ $lg x = O(x^k) $ therefore lg L is indeed in P. In any case: for L=2 as in the original problem, the problem is polynomial in n. $\endgroup$ – Manos Orfanoudakis Jun 30 '16 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.