1
$\begingroup$

A box contains $2n$ balls of $n$ different colors, with 2 of each color. Balls are picked at random from the box with replacement until two balls of the same color have appeared. Let $X$ be the number of draws made.

a) Find a formula for $P(X>k)$ $k=2,3,...$

b) Assuming $n$ is large, use an exponential approximation to find a formula for $k$ in terms of $n$ such that $P(X>k)$ is approximately 1/2. Evaluate $k$ for n equal to one million.

My thought: For part a)

$P(X>k) = 1-P(X\le k) = 1-P(X=0)-P(X=1)-P(X=2) = 1-0-0-\dfrac{1}{2n-1} = 1-\dfrac{1}{2n-1} $

I get stuck on the part b because of the answer for part a.

Could someone help me out?

1 Answers 1

2

This is the generalized birthday problem with the colors of balls being the available birthdays. The first ball can't match anything. The second matches the first with probability $\frac{1}{n}$. Assuming the first two don't match, the third matches one of the first two with probability $\frac{2}{n}$. The chance you get through $3$ draws is then $\frac{n(n-1)(n-2)}{n^3}$

For very large $n$, a good approximation is that each pair matches with probability $\frac{1}{n}$ and in $k$ draws you have $\frac{k(k-1)}{2}$ pairs, so the chance of no match is $(1-\frac{1}{n})^{(\frac{k(k-1)}{2})}$. A more accurate calculation is in the Wikipedia article.

  • 0
    Very good reference, +1.2011-11-02