The is a set of 100 bins $\rightarrow \{b_1,...b_{100}\}$

Every bin as an owner $\rightarrow \{p_1,...p_{100}\}$

Every owner selects $x$ bins (but not their own) and throws a ball into them (e.g $p_1$ selects $x$ bins from the set $\{b_2,...,b_{100}\}$, $p_2$ selects from the set $\{b_1,b_3,...b_{100}\}$ and so on).

I now have that the probability of every bin to have more than $x$ balls is equal to $\frac{1}{z}$ and so the expected number of bins with more than $x$ balls is equal to $100 \times \frac{1}{z}$

Is there any inequality (similar to Markov's or Chebyshev's inequality), using this expected value and the way that the balls are distributed, that bounds the probability of the number of bins with $x$ balls being greater or equal than a specific number?


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.