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

<p>#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$.</p>

<p>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.</p>

<p>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 &gt; 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.</p>

CC BY-SA 3.0
2015-01-23T05:26:49.260Z
2015-01-23T05:35:14.293Z
2015-01-23T05:35:14.293Z
sd234
<p>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>

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

<p>This is by definition the convolution of the two distributions (denoted by *)</p>

<p>$P_{z_2}= P_{x_1} * P_{x_2}$</p>

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

<p>Using the convolution theorem</p>

<p>$ P_{z_2}={\mathcal  {F}}^{{-1}}{\big \{}{\mathcal  {F}}\{P_{x_1}\} \cdot{\mathcal  {F}}\{P_{x_1}\}{\big \}}$</p>

<p>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.</p>

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

<p>$P_{z_n}=P_{z_{n-1}}*P_{x_n}$</p>

<p>For $n$ variables this takes approximately $O(n^2)$ time.</p>

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

CC BY-SA 3.0
2016-06-28T09:26:08.483Z
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.
D.W.
CC BY-SA 3.0
2016-06-30T06:18:40.313Z
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.
Manos Orfanoudakis
CC BY-SA 3.0
2016-06-30T06:28:52.997Z
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).
D.W.
CC BY-SA 3.0
2016-06-30T06:30:52.460Z
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.
D.W.
CC BY-SA 3.0
2016-06-30T10:21:45.773Z
$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.
Manos Orfanoudakis
CC BY-SA 3.0
2016-06-30T10:47:14.887Z
also, part of the input is the distrubutions, and therefore the size of the input is NOT $n*logL$. We do not simply enumerate the input distributions. Actually they ARE the input. so the input is ALWAYS $N*L*k$ bits.
Manos Orfanoudakis
CC BY-SA 3.0
2016-06-30T17:25:39.847Z
As I said in my original comment, for the problem in the first paragraph of the question (Bernoulli r.v.'s), your approach *does* give a polynomial running time.  For the problem in the second paragraph of the question (non-Bernoulli r.v.'s), your approach does *not* have a polynomial running time.  The length of a rational number $r/s$ is $\lg r + \lg s$; this can be as small as $\Theta(\lg L)$, rather than $L$.  I appreciate the enthusiasm and eagerness to help, but I'm afraid the facts aren't on your side on this one.
D.W.
CC BY-SA 3.0
2016-07-01T21:43:58.190Z
Let me understand, you are claiming that the information contained in L x k bits of L floating point numbers is only log L bits ? Or what? L is NOT the length of a number. is the SIZE of the domain of the distribution.
Manos Orfanoudakis
CC BY-SA 3.0
2016-07-01T22:49:25.867Z
Let me rephrase my question: We are not simply given a number L of the number of distinct values. We are given L distinct values. For example, Knapsack is O(nW) generally and is PP w.r.t. to W. It is not PP for for n.
Manos Orfanoudakis
CC BY-SA 3.0
2016-06-25T22:26:40.493Z
2016-06-25T22:26:40.493Z
Manos Orfanoudakis
<p>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?</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-21T02:33:01.547Z
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$.
Geoffrey Irving
CC BY-SA 3.0
2015-01-21T05:49:31.513Z
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$.
Neal Young
CC BY-SA 3.0
2015-01-22T00:52:24.653Z
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...
sd234
CC BY-SA 3.0
2015-01-22T12:05:42.943Z
@srd: could you perhaps provide us with the references that you dug up?
Gamow
CC BY-SA 3.0
2015-01-23T05:27:29.367Z
Sure. I'll post a thorough answer below. FYI, I meant #P hard rather than PP hard in my above comment.
sd234
<cc.complexity-theory><counting-complexity>
Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?
sd234
# Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

(Asked by: username_0 on 2015-01-20)

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.

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: 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$.  
> **username_2**: 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$.  
> **username_0**: 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...  
> **username_3**: @srd: could you perhaps provide us with the references that you dug up?  
> **username_0**: Sure. I'll post a thorough answer below. FYI, I meant #P hard rather than PP hard in my above comment.  

---

## 2 answers

### Answer by username_0 on 2015-01-23. Score: 3

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.


---

### Answer by username_4 on 2016-06-25. Score: -2

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.

> **Comments:**
> **username_5**: 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.  
> **username_4**: 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.  
> **username_5**: 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).  
> **username_5**: 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.  
> **username_4**: $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.  
> **username_4**: also, part of the input is the distrubutions, and therefore the size of the input is NOT $n*logL$. We do not simply enumerate the input distributions. Actually they ARE the input. so the input is ALWAYS $N*L*k$ bits.  
> **username_5**: As I said in my original comment, for the problem in the first paragraph of the question (Bernoulli r.v.'s), your approach *does* give a polynomial running time.  For the problem in the second paragraph of the question (non-Bernoulli r.v.'s), your approach does *not* have a polynomial running time.  The length of a rational number $r/s$ is $\lg r + \lg s$; this can be as small as $\Theta(\lg L)$, rather than $L$.  I appreciate the enthusiasm and eagerness to help, but I'm afraid the facts aren't on your side on this one.  
> **username_4**: Let me understand, you are claiming that the information contained in L x k bits of L floating point numbers is only log L bits ? Or what? L is NOT the length of a number. is the SIZE of the domain of the distribution.  
> **username_4**: Let me rephrase my question: We are not simply given a number L of the number of distinct values. We are given L distinct values. For example, Knapsack is O(nW) generally and is PP w.r.t. to W. It is not PP for for n.  

---

