Probabilities: Estimating the probability of overlapping

1. Jan 16, 2007

jksacc

Hi all
I recently ran into this problem:
I have two bins. Each bin contains N numbered balls, from 1 to N.
For both the bins, the probability of the ball numbered k to be
selected equals to P(ball-k-selected)=k/SUM(1:N) (in other versions
this can be any given probability distribution)

Simple case:
Having selected 1 ball from the first bin, and 1 ball from
the second bin, i want to find the probability of the ball
having the same number.

If i am correct, the probability for this is SUM(k=1:N) (P(ball-k-selected)^2).

Complex case:
Having selected m balls from the first bin, and m balls from
the second bin, i need the probability of holding at least
one pair of balls with the same number at the end of the
experiment.

Assumption: The selection is without replacement. However, for
simplicity we can assume that the probability of a ball to be selected
remains stable during the experiment, and is given by
P(ball-k-selected)=k/SUM(1:N)

If something is not clear, please let me know.

Thanks in advance for any contributions!

2. Jan 17, 2007

EnumaElish

Denote integers with lowercase and sets with UPPERCASE. The set of balls in bin i is Ni.

There are C(n, m) = n!/(m!(n-m)!) combinations (subsets) that you can draw from either bin.

Let S1 be a subset of m balls from the 1st bin. Let S2 be the corresponding subset from the 2nd bin. How many subsets of m balls can you form out of the set of the remaining balls in the 2nd bin, S2' = N2\S2? The answer is s2' = |S2'| = C(n-m, m). That's the answer to the question, "for a given S1, how many disjoint subsets of the same size are there?" Since there are C(n,m) ways to construct S1, there are C(n,m)C(n-m,m) ways to construct two disjoint subsets, each with m elements.

Now you need to calculate the probability of obtaining these disjoint subsets.

Last edited: Jan 18, 2007