Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

Question

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.

Answer 1

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