6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As a heuristic, you can sort the vectors with small Hamming weight (assuming wlog that $p_i < 1/2$ for all $i$) to get a prefix of the ordering. This works better if the $p_i$ are not close to $1/2$. $\endgroup$ – Yuval Filmus Apr 26 '14 at 13:00
  • $\begingroup$ In your $n=100$ case you're going to be marching through $2^{100}$ vectors eventually, so that's not especially feasible in any case.. $\endgroup$ – Steven Stadnicki Apr 28 '14 at 18:53
  • 1
    $\begingroup$ @StevenStadnicki As is commented below, the intention is to iterate over $k \approx 2^{32}$ of them or basically as many as you can in a reasonable amount of time. $\endgroup$ – user10101 Apr 28 '14 at 21:31
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So greedy does work. The log-trick is nice (esp for practical implementation) but it's not necessary, isn't it? $\endgroup$ – Raphael Apr 26 '14 at 17:58
  • $\begingroup$ How large can this priority queue grow if $n =100$? $\endgroup$ – user10101 Apr 26 '14 at 18:13
  • $\begingroup$ @Raphael, Right, the log-trick is not necessary. It does make the connection to Dijkstra's algorithm clearer, though. $\endgroup$ – D.W. Apr 26 '14 at 18:26
  • $\begingroup$ I am worried the priority queue grows linearly with the running time. $\endgroup$ – user10101 Apr 26 '14 at 18:27
  • 1
    $\begingroup$ @user10101, a tighter analysis (or a better algorithm) will depend upon the precise values of the $p_i$'s. Why don't you implement it and try it and see what happens? Or give us more details about the value of the $p_i$'s in your specific scenario? (For instance, if all the $p_i$'s are the same, then we can get a much better algorithm.) $\endgroup$ – D.W. Apr 26 '14 at 18:47
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your analysis assumes that the OP is going to enumerate through all of the $2^n$ values. In practice, I suspect it will be common to only enumerate through a tiny fraction of the values (i.e., will only examine the first $k$ with highest probability, where $k \ll 2^n$). So that seems like the case to focus on. Your analysis focuses on the case of enumerating through all $2^n$ vectors; I agree that the priority queue algorithm isn't so hot for that, but I suspect that's not what the OP is going to do. $\endgroup$ – D.W. Apr 28 '14 at 20:07
  • $\begingroup$ @D.W. That makes good sense, although I think the core concept of the 'slice' and the accompanying estimates of the number of simultaneous values carry over even to partial enumeration; in the partial case, the priority queue is still likely to grow to size roughly $v/d$ after examining the first $v$ values, and so total time will be $\Theta(v\log v)$. $\endgroup$ – Steven Stadnicki Apr 28 '14 at 20:15

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.