3
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ I'm pretty sure there is a poly(n)-time algorithm for the problem you describe using the binomial expansion. $\endgroup$
    – Thomas Steinke
    Commented Sep 17, 2017 at 18:34
  • 3
    $\begingroup$ 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. $\endgroup$
    – Thomas Steinke
    Commented Sep 17, 2017 at 18:38
  • $\begingroup$ You're right, of course! I was going for the simplest non-trivial variant but hit a trivial one :) $\endgroup$
    – Aryeh
    Commented Sep 17, 2017 at 20:13
  • 4
    $\begingroup$ 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. $\endgroup$
    – Thomas Steinke
    Commented Sep 17, 2017 at 22:00
  • 1
    $\begingroup$ I think that for approximate counting it is still in P because via rapid mixing results by Morris (if I remember correctly). $\endgroup$
    – Gil Kalai
    Commented Sep 19, 2017 at 19:47

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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