Why is finding the sign of the sum of exponentially real numbers in PP?

Question

Aaronson mentions in here that:

Recall that $\mathsf{PP}$ is the class of problems like the following:

Given a sum of exponentially many real numbers, each of which can be evaluated in polynomial time, is the sum positive or negative (promised that one of these is the case)?

I simply do not see why this problem is $\mathrm{PP}$. The usual definition of $\mathsf{PP}$ that I know is: "If a decision problem is in $\mathsf{PP}$, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than $1/2$. If the answer is NO, the algorithm will answer YES with probability less than or equal to $1/2$."

So does he mean that there is a randomized algorithm that runs in polynomial time and can decide whether the sum of exponentially many real numbers is positive or negative? If so, what's the algorithm exactly? Can someone please explain?

Answer 1

Yes, $\mathsf{PP}$ can determine the sign of the sum of exponentially many numbers. The main idea is to represent a number by the difference between the accepting probability and the rejecting probability.

Let $x$ be an input number. For now, assume $-1 \le x \le 1$ and that $2^k x$ is an integer. Consider the following machine: choose a uniform random integer $0 \le y \lt 2^{k+1}$. Accept if $y \lt 2^{k+1} (x + 1)$. Then, the difference between accepting and rejecting probabilities is $x$.

By choosing a random number from the input then accepting the input as above, the overall probability difference is the average of input numbers.

The assumption of the input number range can be relaxed by scaling all numbers by a constant depending on the input number size bound. Note that this bound is a fixed polynomial of the input size by assumption.

If an input number is not a multiple of $2^{-k}$, the number is approximated up to $2^{-k-n-1}$. The total error of the sum will be less than $2^{-k}$, so the answer doesn't change due to the promise of non-zeroness.