Herewith I submit what may or may not be considered a simpler version of this question.

The question is whether it is provable that there is no efficient deterministic numerical method for a particular task that will be done by Monte Carlo below.

It was proposed that on average a motorist takes longer to leave a parking space when someone is waiting for that space than when that is not the case. To test this, data were collected. The number of seconds taken by 20 persons leaving a parking space with no one waiting and by 20 others with someone waiting was recorded. The average time taken by those with someone waiting exceeded the average of the other 20 by about $9.8$ seconds. As one would expect, the data were so right-skewed that the usual two-sample t-test could not be considered valid.

The following was repeated 10,000 times. The entire list of $(x_i)_{i=1}^{40}$ was sorted into random order, i.e. a uniformly distributed random permutation $\sigma$ of $\{1,\ldots,40\}$ was chosen, yielding the list $(x_{\sigma(i)})_{i=1}^{40}.$ Then $$ \operatorname{mean}(x_{\sigma(i)})_{i=21}^{40} - \operatorname{mean}(x_{\sigma(i)})_{i=1}^{20} $$ was found. For only $2\%$ of permutations $\sigma$ was the difference in means at least $9.8$ (the difference mentioned above). Thus one can reject the no-difference hypothesis if one is willing to tolerate probability $0.02$ of a false positive.

An obvious reason why one might naively think no deterministic method would work is that computing the difference all $40! \approx 8.16\times 10^{47}$ permutations takes far too long. But that does not prove you can't do something clever with a list of numbers of length only $40$ that could yield an exact result quickly.

Can it be proved that no efficient exact method exists?

  • $\begingroup$ It's enough to compare the mean of a random set of 20 to the mean of the whole 40, so one need only check 40-choose-20, not 40-factorial. Of course, that's still far too many to be practical. $\endgroup$ – Gerry Myerson Apr 8 '19 at 22:32
  • 1
    $\begingroup$ @GerryMyerson : Actually $\left. \dbinom{40}{20}\!\right/\! 2$ is enough. $\qquad$ $\endgroup$ – Michael Hardy Apr 9 '19 at 3:57
  • $\begingroup$ Forgive this likely dumb question, but is the issue whether no efficient method exists to compute the given expression, or to compute the 0.02 false positive result? $\endgroup$ – user114668 Apr 9 '19 at 9:44
  • $\begingroup$ I doubt that it is possible to prove that no "efficient" method exists, but it may be that the generalized problem of counting $m$-subsets of a $2m$-set with sum greater than a given number is #P-complete. On the other hand, it may be possible to produce an FPRAS (fully polynomial-time randomized approximation scheme) $\endgroup$ – Robert Israel Apr 9 '19 at 12:45
  • $\begingroup$ @student : The problem is how to arrive at $0.02. \qquad$ $\endgroup$ – Michael Hardy Apr 9 '19 at 16:07

There is a method, provided the times can be scaled to be integers not too large. Consider that the times are $t_1,\ldots,t_{40}$. The problem can be described like this: for some given $N$, how many of the $\binom{40}{20}$ sums of 20 of the times are $\ge N$?

We can assume $1\le N\le T = t_1+\cdots+t_{40}$.

Now define $$F(x,y)=\prod_{j=1}^{40}\, (1 + xy^{t_j}).$$ Then the number we want is $$\sum_{m=N}^T \,[x^{20}y^m]\, F(x,y),$$ where $[x^{20}y^m]$ denotes coefficient extraction.

You can multiply the polynomial out very quickly. Just use an array $A=(a_{ij})$ of size $21\times (T{+}1)$, to represent $\sum_{ij} a_{ij}x^{i-1}y^{j-1}$. Multiplying by each term takes $O(T)$ arithmetic operations and there are only 40 terms.

If the times are arbitrary real numbers, this doesn't work because $T$ is too large. But in practice that won't happen, since times will all be smallish multiples of, say, $\frac1{10}$ sec.

I'LL ADD that it we want an algorithm which is polynomial in the total size in bits of $t_1,\ldots,t_{40}$, the similarly with the PARTITION problem makes me suspect it is NP-hard. But I don't have a proof.

  • $\begingroup$ Rounding the times up or down to multiples of some convenient unit may allow computation of good bounds. $\endgroup$ – Robert Israel Apr 9 '19 at 19:33

I tried Brendan's method on some data: $t_1 \ldots t_{40}$ are a sample of size $40$ from the exponential distribution with parameter $1$. I want to bound the probability $p$ that $\sum_{i \in S} t_i \ge 29$, where $S$ is a random subset of size $20$. An upper bound is the probability that $\sum_{i \in S} x_i \ge 29000$ where $x_i = \lceil 1000 t_i \rceil$, while a lower bound is the probability that $\sum_{i \in S} (x_i - 1) \ge 29000$, i.e. $\sum_{i\in S} x_i \ge 29020$.

Here is the Maple code, where the $t_i$ are in array $T$.

X:= map(t -> ceil(1000*t), T);
L:= convert(X,`+`);
A:= Matrix(1..21,1..L+1): A[1,1]:= 1:
for i from 1 to 40 do
  A[2..21,X[i]+1..L+1]:= A[2..21,X[i]+1..L+1] + A[1..20, 1..L+1-X[i]];
Upperbound:= evalf(add(A[21, i],i=29001..L+1)/binomial(40,20));
Lowerbound:= evalf(add(A[21, i],i=29021..L+1)/binomial(40,20));

It takes less than $2$ seconds to run on my computer. On a typical run, the lower and upper bounds were $0.03830583966$ and $0.03875584015$.


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.