# Is resampling random variables to maximize value NP-hard?

Setup Let $$S = {X_1, ..., X_n}$$ be a set of independent binary random variable, i.e. $$X_i \in \{0, 1\}$$, each with prior $$P(X_i = 1) = p_i$$. The $$X_i$$ are not iid, so $$p_i, p_j$$ need not be equal if $$i\neq j$$. Let $$A = \{a_0, a_1, ..., a_n\}$$ represent different values of outcomes of $$S$$, more specifically if for a given outcome of $$S$$, say $$\{X_1 = x_1, ..., X_n = x_n\}$$, let $$j = \sum_{i=1}^nx_i$$, then we get value $$a_j$$.

Objective Given an outcome $$\{X_1 = x_1, ..., X_n = x_n\}$$, with associated value $$a_j$$, suppose you can select up to $$\alpha \leq n$$ number of $$X_i$$'s to have their outcomes re-rolled. Select the set of $$X_i$$'s that, in expectation, yields the greatest value of $$A$$. (For clarity, the nodes are selected all at once, then all re-rolls happen simultaneously, no node may be re-rolled more than once.)

Question Does their exist a polynomial time algorithm to solve this problem? Is it NP-hard?

Work so Far So far I've worked out that if $$A$$ defines a monotone sequence, then the optimal set of variables to resample can be computed in polynomial time. To see this, suppose that $$A$$ is monotone increasing, then a greedy selection scheme is optimal. Namely, from all nodes that have outcome $$X_i = 0$$ that have not yet been selected to be resampled, pick the $$X_i$$ with the greatest $$P(X_i=1)$$. Do this until you select $$\alpha$$ variables, or no such variables with outcome 0 exist. A similar scheme works when $$A$$ is decreasing.

I also tried a dynamic programming approach which has not yet been fruitful.

• Are the $X_i$ independent random variables? If yes, do we have $P(X_i = 1) = p_i$, if not, what is their relationship? I'm also confused about $j, a_j$ and $A$. Can you clarify precisely which one you wish to maximize? In particular explain why the greedy scheme won't always work. – orlp Aug 30 '19 at 5:59
• @orlp The variables are independent, but not iid, and the prior $p_i$ is known for all variables. $A$ is some set of potential rewards that can be earned, based of $j$ which is the sum of the random variables. So if the sum is $j$, then we get reward $a_j$. Our goal is to maximize the $a_j$ we receive. – Barcode Aug 30 '19 at 14:20
• Are you OK with heuristics that might work well in practice, or do you want exact algorithms that give the exact optimum with guaranteed worst-case performance? – D.W. Aug 30 '19 at 19:18
• @D.W. I was hoping to have some algorithm that either constant factor approximates the optimal solution ( even if the problem isn't NP hard), or gives the optimal solution. In a few experiments of mine, greedy versions of hill climbing work quite well on random examples, but could be arbitrarily bad. – Barcode Aug 30 '19 at 19:47