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?

$\endgroup$
  • $\begingroup$ I'm pretty sure there is a poly(n)-time algorithm for the problem you describe using the binomial expansion. $\endgroup$ – Thomas Sep 17 '17 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 Sep 17 '17 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 Sep 17 '17 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 Sep 17 '17 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 Sep 19 '17 at 19:47
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$.

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

$\endgroup$

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.