Estimate the rank of a vector

Question

Consider {0,1}-vectors $v$ with $n$ elements. For each $i\in[n]$ we are given $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. We can therefore associate a probability to each of the $2^n$ $n$-dimensional vectors. Let $V$ be the sorted list of this set of vectors using probability as the key, ordered from most likely to least likely. For a given vector $w$, its rank is simply its index in $V$.

If we are given an $n$-dimensional vector $w$ and probabilities $p_i$, how accurately can we estimate the rank of $w$ in polynomial time?

(Please feel free to improve the title or tags as I am not sure either is very good.)

Answer 1

I'll give a rough answer whose utility might depend on to what extent you want to answer the question in theory vs. practice.

The given problem is at least morally reducible to the problem #KNAPSACK of counting solutions to a knapsack problem. To see this note that by swapping $0$'s and $1$'s we can safely assume $p_i>0.5$ for all $i$. The probability in question is then $$\mathbb{P}(v) = \prod_i (1-p_i) \prod_i \left(\frac{p_i}{1-p_i}\right)^{v_i}.$$ Since we are only interested in how these are ordered, we can drop the first product, which does not depend on $v$. If we then define $\rho_i = \log\frac{p_i}{1-p_i}$, we have $$\log \mathbb{P}(v) = C + \sum_i v_i\rho_i,$$ where $C = \sum_i\log(1-p_i)$. Since $C$ does not depend on $v$, finding the rank of $\mathbb{P}(w)$ among all values $\mathbb{P}(v)$ reduces to finding the number of $v$ with $\sum_i v_i\rho_i \leq \sum_i w_i\rho_i$. This is the number of solutions to the knapsack problem with items of size $\rho_i$ and total space $\sum_i w_i\rho_i$.

So any practical (exact or approximate) algorithm for #KNAPSACK can be used to solve the given problem. As for theoretical guarantees, if you want to talk about complexity of the reduction above you'd need to decide how many bits of precision to use for computing the logs. I haven't thought about how this would translate into guarantees about approximation ratio / correctness or running time, so this is why I said "morally" reducible.

It's also worth noting that the resulting instance of #KNAPSACK is quite general; the only difference between the output of the reduction and a general instance is that in the reduction the total space in the knapsack is of the form $\sum_i w_i\rho_i$ for some $w_i$. This doesn't seem a priori to be a very strong restriction so it's conceivable that you could tweak things to find a reduction in the other direction.

Thus I'd guess that this problem is equivalent complexity-wise to #KNAPSACK (which is known to be #P complete but admits various types of approximation algorithms), but there are some details that would need to be filled in to make a precise statement.