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?

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