Practical Randomization Question

We need to choose Bernoulli random variables x_i. Each x_i must be one with probability p_i (zero otherwise), but the x_i do not need to be independent. The easy way to do this is to choose x_i independently, but we would like to find a method that reduces the mean absolute (or mean squared) difference between sum(h_i x_i) and sum (h_i p_i) for a given set of positive weights h_i. It seems there should be a slick, easy way to do this, no?

The motivation is that we have a bunch of predators and prey items. Each prey item has its own chance of being eaten, but we want the total amount eaten by the predators to be about the amount that they eat per time step.

Jonathan Dushoff

One way might be this. Let S_j = sum_{i<j} h_i x_i. There is m_j such that Pr{S_j < m_j} < p_j and Pr{S_j <= m_j} >= p_j. Let t_j = (p_j - Pr{S_j < m_j})/Pr{S_j = m_j}. Take x_j = 1 if S_j < m_j, x_j = 0 if S_j > m_j, and x_j = 1 with probability t_j if S_j = m_j. Thus if the sum of the x_i chosen so far is too low, we make x_j=1 to compensate; if too high, we make x_j=0. I don't know how to estimate the amount of reduction in mean absolute (or squared) difference, however.

Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2

This is an interesting problem, which I need to consider for a while. As a first step, what happens when there are only two random variables? If you can figure that out, how about three? Do these indicate a pattern?