12
$\begingroup$

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 .

$\endgroup$
  • $\begingroup$ Is there any reason you didn't ask the followup question there too ? Is the main issue here one of doing this in sublinear space ? $\endgroup$ – Suresh Venkat Jun 7 '14 at 19:37
  • $\begingroup$ @SureshVenkat Yes the problem is entirely about sublinear space (in the output size). I asked it here as I think the question may be very hard. $\endgroup$ – Lembik Jun 7 '14 at 19:38
  • $\begingroup$ Solving this in $\textrm{poly}(n)$ space and time seems to require techniques similar to SUBSET-SUM (quickly knowing which sums of subsets nearly cancel different sums). Thus, it is unlikely to have a fast solution. $\endgroup$ – Geoffrey Irving Jun 9 '14 at 22:03
  • $\begingroup$ @GeoffreyIrving Do you think this intuition can be made more formal? $\endgroup$ – Lembik Jun 10 '14 at 6:38
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there plausibly a reduction which would make a poly time/space solution implausible? $\endgroup$ – Lembik Jun 10 '14 at 7:53
  • $\begingroup$ You're probably not going to get a solution which takes less than $2^n$ time, since that's the size of the output (and my solution takes $n\, 2^n$ time). I don't have a good lower bound for space, though. $\endgroup$ – Peter Shor Jun 10 '14 at 12:31
  • $\begingroup$ Thank you. I didn't mean poly time of course but rather something linearish in the output size and poly space. $\endgroup$ – Lembik Jun 10 '14 at 18:07
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. That is quite a slow algorithm however :) $\endgroup$ – Lembik Jun 9 '14 at 20:46
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The other answer is certainly different as it requires a priority queue and hence uses $\Theta(2^n)$ space. $\endgroup$ – Lembik Jun 8 '14 at 7:44
  • $\begingroup$ Thanks. I clearly didn't read it carefully enough! I've edited my answer. $\endgroup$ – gandaliter Jun 8 '14 at 11:04
  • 3
    $\begingroup$ Are you sure this solution works? I couldn't figure out the details of the double recursion (pseudocode would help!) but I don't see how this could work. In particular, your solution seems to be local: if it set $v_1=1$ it's now going to output $2^{n-1}$ answers with $v_1=1$. But the actual answers shouldn't look this way. In fact, as far as I understood your solution, it seems to fail even for the simplest case where all $p_i=0.5$. $\endgroup$ – mobius dumpling Jun 8 '14 at 13:16
  • $\begingroup$ You're right, this doesn't work. Sorry! $\endgroup$ – gandaliter Jun 9 '14 at 11:28

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.