How to iterate over vectors in order of probability in small space

Question

Consider an $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 binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties) using space sublinear in the output size?

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 very small $n$ we could label each of the $2^n$ vectors with its probability and simply sort but this would of course still not use sublinear space.

A close variant of this question was previously asked at https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability .

Answer 1

The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.

First, let's look at the problem of sorting the sums of all subsets of $n$ items.

Consider this subproblem: you have two sorted lists of length $m$, and you would like to create a sorted list of the pairwise sums of the numbers in the lists. You would like to do this in roughly $O(m^2)$ time (the output size), but sublinear space. We can achieve $O(m)$ space. We keep a priority queue, and pull the sums out of the priority queue in increasing order.

Let the lists be $a_1 \ldots a_m$ and $b_1 \ldots b_m$, sorted in increasing order. We take the $m$ sums $a_i + b_1$, $i = 1 \ldots m$, and put them in a priority queue.

Now, when we pull the smallest remaining sum $a_i + b_j$ out of the priority queue, if $j < m$ we then put the sum $a_i + b_{j+1}$ into the priority queue. The space is dominated by the priority queue, which always contains at most $m$ sums. And the time is $O(m^2 \log m)$, since we use $O(\log m)$ for each priority queue operation. This shows we can do the subproblem in $O(m^2 \log m)$ time and $O(m)$ space.

Now, to sort the sums of all subsets of $n$ numbers, we just use this subroutine where the list $a_i$ is the set of sums of subsets of the first half of the items, and the list $b_i$ is the set of sums of subsets of the second half of the items. We can find these lists recursively with the same algorithm.

We will now consider the original problem. Let $S_0$ be the set of coordinates which are $0$, and $S_1$ be the set of coordinates which are $1$. Then \begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &=& \prod_{1\leq i \leq n} p(v_i=0) \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &=& \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}

Sorting these numbers is the same as sorting the numbers $\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$, so we have reduced the problem to sorting the sums of subsets of $n$ items.

Answer 2

We can do that in space $O(n)$ (if we don't care about the running time).

1. For a given string $x \in \{0,1\}^n$, we can compute in space $O(n)$ the number $r(x)$ of strings that are more likely than $x$; that is, the number of $x'$ s.t. $p(x') > p(x)$: just go over all $x'\in \{0,1\}^n$ and count the number of $x'$ s.t. $p(x') > p(x)$. Note that $r(x)$ is the sequential number of string $x$ in the output.
2. For every $k$, we can find $x$ with $r(x) = k$ in space $O(n)$: go over all $x \in \{0,1\}^n$, for each $x$ compute $r(x)$, stop and output $x$ if $r(x) = k$.
3. Now just go over all $k$ from $0$ to $2^n-1$, for each $k$ print $x$ with $r(x) =k$.

(We should also take care of possible ties, but this is not difficult.)

Answer 3

Edit: This answer is incorrect. See comments for details. ~gandaliter

Linear in the output means $O(2^n)$. I think the obvious algorithm only uses $O(n)$ space, apart from the output itself of course.

1. Take the list containing the pairs $(i, p_i)$, and sort it by $\left|0.5 - p_i\right|$, largest first.

2. Define a doubly recursive function which takes a list of such pairs and a partially filled vector $v$, sets the value of $v_i$ as $1$ if $p_i > 0.5$, and $0$ otherwise, and recurses (using the tail of the list, and $v$), then flips $v_i$ and recurses again. If the list is empty it instead outputs $v$.

3. Call this recursive function on the sorted list and an empty vector.

The intuition is that you are setting the values of the most certain elements in the vector first (the ones whose probabilities are closest to $0$ and $1$), and filling the vector in like that, finishing with the ones whose probabilities are closest to $0.5$. Each possible value that the whole vector could take is outputted in order of its probability.

The run time is $O(2^n)$, which is the lower bound because that is the length of the output. The space complexity is $O(n)$ because the sort doesn't require more than that, and the recursive length is the length of the vector, which is $n$. I believe this is also the lower bound because there must be a different state in memory for every time step in the running of the algorithm, and the time complexity is $O(2^n)$. $O(n)$ states in memory are required to enumerate $O(2^n)$ time steps. Therefore this algorithm is worst-case complexity optimal.