I have $ B $ bins and $ G $ balls, and each of the balls has a weight. I toss the balls uniformly into the bins. I select the $ K $ bins that have the highest weights as determined by the weights of the balls that are in them, and I then record the total number of balls that appear in these $ K $ bins.

I want to model the sum of the number of balls that appear in these $ K $ bins. Can I create a "worst-case" model of this quantity? E.g., can I say that this quantity's variance can be no worse than some other computable value?

Intuitively, I believe that I can because, as $ K \rightarrow B $, this quantity's expected value becomes $ G $ and its variance goes to 0.

  • $\begingroup$ When you say "then select K of these bins using some non-uniform selection criterion" do you mean you choose the bins non-randomly, or they are chosen randomly according to some non-uniform distribution? $\endgroup$ – Patty Jul 7 '17 at 1:57
  • $\begingroup$ @Patty Non-randomly. Suppose that each ball has a weight. After tossing the balls, I weigh the bins and select the $ K $ heaviest. Thus there is some correlation between the probability that a bin is selected and the number of balls that are tossed into a bin. $\endgroup$ – Jess Smith Jul 7 '17 at 2:06
  • $\begingroup$ Can you be clearer about what you mean by "the distribution's variance"? What quantity are you finding the distribution and the variance of? Note that if you're looking at the number of balls in each bin, that would be a vector-valued random variable. Do you mean the variance-covariance matrix of that distribution, or are you constructing some other (possibly univariate) random variable from the bin-counts? (e.g. are you adding together all of the counts among the K bins?) $\endgroup$ – Glen_b Jul 7 '17 at 2:11
  • $\begingroup$ Further, when you say that the K bins are not uniformly selected -- does this selection in any way relate to the contents of the bins, or it it more like "choose the first K bins in the list without regard to what ended up in them". $\endgroup$ – Glen_b Jul 7 '17 at 2:15
  • $\begingroup$ @Glen_b I've edited the question. Let me know if anything is still unclear. $\endgroup$ – Jess Smith Jul 7 '17 at 5:08

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.