How to iterate over vectors in order of probability

Question

Consider a random $n$ dimensional vector $v$ where $v_i \in \{0,1\}$. For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. Using these probabilities, is there an efficient way to iterate over all possible binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties)?

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.

For small $n$ we could label each vector with its probability and sort although this isn't very efficient. However, consider $n=100$ for example. This is no longer an option.

Answer 1

You can solve this with a priority queue.

Let $L(x)$ be the log-probability of the vector $x$, i.e.,

$$L(x) = \log \prod_i p_i^{x_i} (1-p_i)^{1-x_i} = \sum_i \ell_i(x_i)$$

where

$$\ell_i(b) = \log (p_i^b (1-p_i)^{1-b}).$$

Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \{0,1\}^n$ in order of decreasing $L(\cdot)$ value.

Of course, it is easy to identify the vector which has highest probability, i.e., highest $L(\cdot)$-value. We simply put a $1$ in the $i$-th position if $p_i\ge 1/2$ and a $0$ otherwise; call the result $x_{\text{best}}$. So create a priority queue that will hold a set of $n$-vectors. Initialize it to a single element, $x_{\text{best}}$. Assign it the priority $L(x_{\text{best}})$. In general, if $x$ is in the priority queue, its priority will be $L(x)$. Also, create a set $S$ of nodes that have been previously output; initially we will have $S = \emptyset$.

Now repeat the following loop:

• Find the value of maximum priority and remove it from the priority queue. Call it $x$.

• Output $x$. Add $x$ to $S$.

• For each $i=1,2,\dots,n$: Let $y$ denote the vector obtained by flipping the $i$th bit of $x$; if $y \notin S$, add $y$ to the priority queue, with priority $L(y)$.

This loop will output the elements of $\{0,1\}^n$ in order of decreasing $L(\cdot)$-value.

Why does this work? Basically, if $x$ has the highest $L(\cdot)$-value, then the next-highest must be obtained by flipping a single bit; flipping two bits will give you something strictly worse. The same kind of justification can be applied inductively. Or, to think about it another way, this is basically Dijkstra's algorithm applied to the $n$-dimensional cube (vertices are $\{0,1\}^n$), and Dijkstra's algorithm is an efficient way to enumerate the nodes of a graph in order of decreasing distance. Since $L(\cdot)$ is additive, it can be understood as a distance from $x_{\text{best}}$.

Answer 2

To address the issue of asymptotic behavior a bit (in an answer, since this is too long for a comment): in $n$ dimensions, the priority-queue algorithm that's been mentioned essentially marches an '$(n-1)$-plane' through the $n$-cube, so the worst-case behavior is exponential in the dimension — but then, so is the number of vectors being iterated over. Finer-grained analysis requires understanding of the number of edges of a hypercube that can be 'cut' by such an $n-1$-plane (and more to the point, the number of vertices they can connect to on the other side); I'm pretty certain this is maximized when the plane is orthogonal to the long diagonal of the hypercube, but proving that is a little tricky. The asymptotic worst-case should be roughly ${n\choose\lceil n/2\rceil}\approx\frac1{\sqrt{\pi n/2}}2^n$ (for instance, when all the weights are equal then this is the number of elements of weight $\lceil n/2\rceil$), so that the priority queue will have to be of size roughly $\frac1{\sqrt{\pi n/2}}$ times the total number of elements iterated over — for instance, when $n=20$ it'll grow to roughly $18\%$ of the $2^{20}$ total elements. In particular, note that since the maximum heap size is asymptotically very close to the total size of the data being worked on, the total running time of the priority-queue algorithm is essentially the same, asymptotically, as just sorting all the weights upfront: for $n$-dimensional data, it's of time $2^n\cdot\lg(Cn^{-1/2}2^n)$ $\approx 2^n\cdot(n-\frac12\lg n+\lg C)$ $\in\Theta(2^n\cdot n)$, which is the asymptotic complexity of the sort-based approach. (In practice, of course, the queue is noticably better than sorting.)

My strong suspicion is that you're going to need time $\Theta(v\log v)$ (or maybe even $\Theta(nv)$) to iterate over the first $v$ values; the real question (to my mind at least) is whether you can do it in space $\ll\Theta(v)$. To that end, you might look at variants of the Bresenham line-drawing-algorithm; it solves a similar problem (finding the next pixel in a line) by keeping track of $n$ 'discrepancies', one for each of the $n$ axes, and updates those on each step of the line. I don't know of any It's possible you could find a way to hold only a small discrepancy vector, use that to determine the next point(s), and then update it suitably; digging into the details of the Bresenham algorithm (and again, variants and extensions of it) is the best place I can think of to find more information on that potentially-fruitful approach. (But again, since in the worst case you can have $\Theta(2^n/\sqrt{n})$ points with the same weight, any general algorithm that uses less space is going to have to be smart enough to figure out a good way of iterating over those without having to store all of them.)