Re: A Question on Balls and Bins

On Mar 16, 3:08 pm, matt271829-n...@xxxxxxxxxxx wrote:
On Mar 16, 2:17 pm, "jmorr...@xxxxxxxxxxx" <jmorr...@xxxxxxxxxxx>
wrote:





On Mar 16, 5:48 am, nivekkos...@xxxxxxxxx wrote:

Here's a seemingly simple question about balls and bins that I've been
struggling with. I'm hoping someone can help shed some light on this
problem:

Given k balls with m BLUE balls and (m-k) RED balls. Toss them
independently and uniformly at random into n bins. What is the
probability that there are no bins with both a BLUE and a RED ball?

I can express the probability as an messy sum involving Stirling
numbers of the second kind. But I can't seem to simplify it any
further. Is there a nice way to count things to yield a nice
expression at the end? Or is there an easy way to (non-trivially)
bound this probability?

Thanks.

Here's a method I use for this type of problem. It <seems> correct...

First mix together all the balls and a bunch of dividers, one divder
less than the number of bins. This means there are k + n - 1 items,
to be arranged in (k + n - 1)! ways.(Call this X).

But (n-1)! (call it Y) of these come from rearranging the dividers, m!
(call it Z) from rearranging the blue balls, and (k-m)! (call it W)
from rearanging the red balls.

So the total number of distinct distributions, without restriction, is
X/(Y Z W)

Now, glue a red ball and a blue ball together! This means that

Now you have k-2 individual balls (m-1 blue and k-m-1 red), one double
ball, and n - 1 dividers.

So now repeat the previous calculation: factorial(number of items)/
(factorial(# of red)*factorial(# of blue)*factorial(# of dividers))

This will be the number of distributions with at least one red/blue
color pair (the glued pair) in at least one bin.

The difference is the number with no red/blue colors pairs anywhere.

IMHO, anyway...

Perhaps I am misunderstanding something, but I don't really see how
this works. Take the very simple example of one red ball, one blue
ball and one bin. According to your terminology, you have two
"distinct" distributions: RB in bin 1, and BR in bin 1. With the glued
ball in place you have just one possibility: glued ball in bin 1.
Therefore the probability of having at least one blue/red pair in at
least one bin comes out as 1/2, while the correct answer is obviously
1. More complex examples seem to go similarly awry, with under-
counting and multiple counting abounding.

.... and, even if the counting could be done correctly, you seem to be
treating each of your "distinct distributions" as equally probable,
which they aren't.

(FWIW I also ended up with a sum involving Stirling numbers, and can't
see how to simplify further.)

.

Relevant Pages

  • Re: Lottery facts for Sherry
    ... Totally incorrect. ... Six balls are to be drawn from a "bin" that contains 49 balls that are ... The probability that any ball will be picked first is 1/49. ...
    (rec.gambling.lottery)
  • Re: A Question on Balls and Bins
    ... probability that there are no bins with both a BLUE and a RED ball? ... color pair in at least one bin. ... counting and multiple counting abounding. ...
    (sci.math)
  • Re: Lottery facts for Sherry
    ... Every ball in a lottery bin has precisely the same ... Six balls are to be drawn from a "bin" that contains 49 balls ... The probability that any ball will be ...
    (rec.gambling.lottery)
  • Re: A Question on Balls and Bins
    ... probability that there are no bins with both a BLUE and a RED ball? ... color pair in at least one bin. ...
    (sci.math)
  • Re: Logarithm of transfinite numbers
    ... Since, by rule, no ball with an non-finite label is allowed to be put ... finite natural numbered Iteration is run and so these balls would have ... no non-finite numbered ball is ever added to the bin. ...
    (sci.math)
Quantcast