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.

  • 4
    $\begingroup$ 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. $\endgroup$ – orlp Aug 30 '19 at 5:59
  • $\begingroup$ @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. $\endgroup$ – Barcode Aug 30 '19 at 14:20
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Aug 30 '19 at 19:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Barcode Aug 30 '19 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.