<p><strong>Theorem</strong> Exactly computing $F(w,t)$ is #P-hard.</p>

<p><em>proof.</em>  Reduce from the counting version of Subset Sum, the #Subset Sum problem, defined as follows. Input is a set $W = w_1, \ldots, w_n$ of non-negative integers, and an integer $t$. The task is to count the number of subsets $W' \subseteq W$ that add up to exactly $t$. This problem is known to be #P-hard, even when for all $i$, $w_i \leq t$ and $t = 2^{O(n)}$. In particular, the $w_i$'s are $O(n)$ bit integers.  </p>

<p>Suppose now we could compute F in polynomial time. Then we could solve the #Subset Sum problem by outputting:</p>

<p>$$2^n \cdot \left( F(\frac{W}{t}, 1-\frac{1}{t}) - F(\frac{W}{t}, 1) \right) = 2^n \cdot P\left[\sum_{i=1}^n \frac{w_iX_i}{t} = 1 \right],$$
which is precisely the number of subsets of $W$ that add up to $t$. </p>

CC BY-SA 3.0
2017-09-24T11:31:00.940Z
2017-09-24T11:31:00.940Z
daniello
<p>If you're interested in fast algorithms for the original problem,
John Langford worked on numerical approximations of the tails of B(n,p). See his program: <a href="http://hunch.net/~jl/projects/prediction_bounds/bound/bound.html" rel="nofollow noreferrer">http://hunch.net/~jl/projects/prediction_bounds/bound/bound.html</a></p>

<p>The tails of B(n,p) are of practical importance in statistics e.g. for computing Clopper-Pearson confidence interval. So, I would guess that any decent statistics package must have an algorithm for this too.</p>

CC BY-SA 3.0
2017-09-19T22:42:22.713Z
2017-09-19T22:42:22.713Z
David Pal
<p>Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B&gt;t)$. Naively, computing $F$ requires exponential (in $n$) time. Suppose that $p$ and $t$ are specified with $O(n)$ bits -- this precision level is sufficient to describe all of the outputs in the range of $F$. I strongly suspect that there is no poly(n) time algorithm for computing $F$ exactly; is there any formal evidence of this?</p>

<p><b>Edit</b>. As pointed out in the comments, the function above is of course computable in polynomial time. How about the following variant: $X_i$ are independent symmetric Bernoulli variables and $w_i\in[0,1]$ are weights specified with $O(n)$ bits each. Define the function
$$ F(w,t):=P( \sum_{i=1}^n w_i X_i &gt; t) .$$
Hoeffding's inequality provides exponential bounds on $F$; what is the complexity of computing $F$ exactly?</p>

CC BY-SA 3.0
2017-09-17T18:34:32.260Z
I'm pretty sure there is a poly(n)-time algorithm for the problem you describe using the binomial expansion.
Thomas Steinke
CC BY-SA 3.0
2017-09-17T18:38:08.030Z
You want to compute $\sum_{k=\lfloor t+1 \rfloor}^n {n \choose k} p^k (1-p)^{n-k}$ and I don't see why that can't be done in poly time.
Thomas Steinke
CC BY-SA 3.0
2017-09-17T20:13:57.450Z
You're right, of course! I was going for the simplest non-trivial variant but hit a trivial one :)
Aryeh
CC BY-SA 3.0
2017-09-17T22:00:56.837Z
My gut feeling is that the second variant is #P-hard. You're counting the number of solutions $x \in \{0,1\}^n$ to the equation $\sum_i^n w_ix_i >t$, which seems vaguely like a counting version of the knapsack problem.
Thomas Steinke
CC BY-SA 3.0
2017-09-19T19:47:50.930Z
I think that for approximate counting it is still in P because via rapid mixing results by Morris (if I remember correctly).
Gil Kalai
CC BY-SA 3.0
2017-09-19T21:23:54.093Z
Thanks Gil. What about the exact count?
Aryeh
CC BY-SA 3.0
2017-09-21T20:52:53.133Z
This is #P-hard, because by scaling, the weights could just as well be $O(n)$ bit integers, and $P[\sum_{i=1}^n w_iX_i  > t-1] - P[\sum_{i=1}^n w_iX_i  > t] = P[\sum_{i=1}^n w_iX_i  = t]$. Further, $2^n \cdot P[\sum_{i=1}^n w_iX_i  > t]$ is precisely the number of subsets of $\{w_1, \ldots, w_n\}$ that add up to t, which is #P-hard to compute.
daniello
CC BY-SA 3.0
2017-09-23T17:29:44.660Z
@daniello can you turn this into a formal answer, with a clearly spelled out reduction?
Aryeh
<cc.complexity-theory><np-hardness><pr.probability>
Hardness of exact binomial tail bounds
Aryeh
# Hardness of exact binomial tail bounds

(Asked by: username_0 on 2017-09-17)

Chernoff bounds, in their various forms, bound the tails of a Binomial$(n,p)$ random variable $B$. Define the function $F(n,p,t):=P(B>t)$. Naively, computing $F$ requires exponential (in $n$) time. Suppose that $p$ and $t$ are specified with $O(n)$ bits -- this precision level is sufficient to describe all of the outputs in the range of $F$. I strongly suspect that there is no poly(n) time algorithm for computing $F$ exactly; is there any formal evidence of this?

**Edit**. As pointed out in the comments, the function above is of course computable in polynomial time. How about the following variant: $X\_i$ are independent symmetric Bernoulli variables and $w\_i\in[0,1]$ are weights specified with $O(n)$ bits each. Define the function
$$ F(w,t):=P( \sum\_{i=1}^n w\_i X\_i > t) .$$
Hoeffding's inequality provides exponential bounds on $F$; what is the complexity of computing $F$ exactly?

**Tags:** cc.complexity-theory, np-hardness, pr.probability

> **Comments:**
> **username_1**: I'm pretty sure there is a poly(n)-time algorithm for the problem you describe using the binomial expansion.  
> **username_1**: You want to compute $\sum_{k=\lfloor t+1 \rfloor}^n {n \choose k} p^k (1-p)^{n-k}$ and I don't see why that can't be done in poly time.  
> **username_0**: You're right, of course! I was going for the simplest non-trivial variant but hit a trivial one :)  
> **username_1**: My gut feeling is that the second variant is #P-hard. You're counting the number of solutions $x \in \{0,1\}^n$ to the equation $\sum_i^n w_ix_i >t$, which seems vaguely like a counting version of the knapsack problem.  
> **username_2**: I think that for approximate counting it is still in P because via rapid mixing results by Morris (if I remember correctly).  
> **username_0**: Thanks Gil. What about the exact count?  
> **username_3**: This is #P-hard, because by scaling, the weights could just as well be $O(n)$ bit integers, and $P[\sum_{i=1}^n w_iX_i  > t-1] - P[\sum_{i=1}^n w_iX_i  > t] = P[\sum_{i=1}^n w_iX_i  = t]$. Further, $2^n \cdot P[\sum_{i=1}^n w_iX_i  > t]$ is precisely the number of subsets of $\{w_1, \ldots, w_n\}$ that add up to t, which is #P-hard to compute.  
> **username_0**: @username_3 can you turn this into a formal answer, with a clearly spelled out reduction?  

---

## 2 answers

### Answer by username_3 on 2017-09-24. Score: 3 | Accepted answer

**Theorem** Exactly computing $F(w,t)$ is #P-hard.

*proof.* Reduce from the counting version of Subset Sum, the #Subset Sum problem, defined as follows. Input is a set $W = w\_1, \ldots, w\_n$ of non-negative integers, and an integer $t$. The task is to count the number of subsets $W' \subseteq W$ that add up to exactly $t$. This problem is known to be #P-hard, even when for all $i$, $w\_i \leq t$ and $t = 2^{O(n)}$. In particular, the $w\_i$'s are $O(n)$ bit integers.

Suppose now we could compute F in polynomial time. Then we could solve the #Subset Sum problem by outputting:

$$2^n \cdot \left( F(\frac{W}{t}, 1-\frac{1}{t}) - F(\frac{W}{t}, 1) \right) = 2^n \cdot P\left[\sum\_{i=1}^n \frac{w\_iX\_i}{t} = 1 \right],$$
which is precisely the number of subsets of $W$ that add up to $t$.


---

### Answer by username_4 on 2017-09-19. Score: 0

If you're interested in fast algorithms for the original problem,
John Langford worked on numerical approximations of the tails of B(n,p). See his program: <http://hunch.net/~jl/projects/prediction_bounds/bound/bound.html>

The tails of B(n,p) are of practical importance in statistics e.g. for computing Clopper-Pearson confidence interval. So, I would guess that any decent statistics package must have an algorithm for this too.


---

