# Estimate the rank of a vector

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

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