Choosing $k$ different assignments of binary variables in order to capture the largest volume of the joint probability distribution

Question

Assume you have $n$ independent binary variables $\{x_1,\dots,x_n\}$ and for each variable $x_i$ you know that its value is equal to $1$ with a probability $p_i$. I would like to enumerate the joint assignments of these variables in such a way that in $k$ steps I capture as much volume of the joint probability mass function as possible. Does there exist some approximation algorithm which runs faster than the algorithm which enumerates the assignments according to their joint probability $\Pi p_i$. Or something related?

Answer 1

You want to find a $k$-subset $S\subseteq\{0,1\}^n$ to maximize $$\sum_{(y_1,\dots,y_n)\in S} \prod_{i=1}^n \left(p_{i}y_i+(1-p_i)(1-y_i)\right).$$

Equivalently, find the $k$ largest (with multiplicity) $$\prod_{i=1}^n \left(p_{i}y_i+(1-p_i)(1-y_i)\right).$$

Equivalently, find the $k$ largest (with multiplicity) $$\sum_{i=1}^n \left((\log p_{i})y_i+(\log(1-p_i))(1-y_i)\right).$$

Some integer linear programming (ILP) solvers have an option to find the $k$ best solutions. An alternative approach to get the $k$ best solutions is to call an ILP solver $k$ times. After each solve, yielding optimal solution $\hat{y}\in\{0,1\}^n$, impose an additional no-good cut $$\sum_{i:\hat{y}_i = 0} y_i + \sum_{i:\hat{y}_i = 1} (1 - y_i) \ge 1$$ that excludes only that solution.

Answer 2

There are no general shortcuts as far as I can see.

To simplify things, complement some variables $x_i$ and renumber so that you have $$ p_1\geq p_2 \geq p_3 \geq \cdots \geq p_n \geq \frac{1}{2},\qquad p_i=\mathbb{P}[x_i=1], \forall i. $$ The $k=1$ case will use the assignment $(x_1,\ldots,x_n)=(1,\ldots,1).$ If some $p_i=\frac{1}{2},$ whenever $i\in J \subset \{1,\ldots,n\},$ those variables $x_i$ can be chosen either as $x_i=1$ or as $x_i=0,$ and achieve the same maximum probability value of the $(1,\ldots,1)$ assignment, which gives you a total of $2^{\#J}$ such assignments. Thus if $k\leq 2^{\#J}$ you can choose these assignments and add terms of maximal probability.

So let's ignore this case which simply restates the problem on $n-\#J$ coordinates, and assume $p_n>1/2,$ which is the minimal probability after reassignment. We can also assume $p_1<1,$ to rule out another pathological case since complementing that will yield zero probability, with no further consideration needed.

You could start flipping $x_i$ in singletons from 1 to 0 and first flip $p_n,$ then $p_{n-1}$ etc (since $p_i\geq p_{i+1}$ in a greedy manner to obtain new probabilities that are the largest possible due to the renumbering. This will give you assignments $$ (1,\ldots,1,1,0),(1,\ldots,1,0,1),(1,\ldots,0,1,1),\ldots $$ in order. However, beyond the first two assignments in the list here one cannot give general guarantees of monotonicity of the newly added probabilities, since one might have $$ (1-p_i)(1-p_j) > (1-p_k) $$ for example and this requires checking assignments with two zeroes before exhausting those with one zeroes, hence the simple monotonicity of the problem is lost.