Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
Very good reference, +1. –  Emmad Kareem Nov 2 '11 at 4:37
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.