Exponential approximation help

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.

For part a), I got that P(X>k) = (2n-2)/2n * (2n-4)/2n *...* (2n-2k+2n)/2n for k terms.

For part b), how do I set up an exponential approximation? To get started, I think that it would be e^(-1) + e^(-2) +...+ e^(1-k)... am I on the right track?

sillybuffalo said:

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.

For part a), I got that P(X>k) = (2n-2)/2n * (2n-4)/2n *...* (2n-2k+2n)/2n for k terms. To make this a "formula," use factorials and powers.

For part b), how do I set up an exponential approximation? To get started, I think that it would be e^(-1) + e^(-2) +...+ e^(1-k)... am I on the right track?

Click to expand...

The probability of drawing a specified color is is 2 out of 2n, or \(\displaystyle p_1 = 1/n\). If \(\displaystyle k\) unique (no matches) colors have already been drawn, then the probability that the next draw is a match is \(\displaystyle p_k = k/n\) and the probability of not matching is \(\displaystyle q_k = 1 - p_k = \dfrac{n-k}{n}\)

The probability of drawing \(\displaystyle k\) colors without a match is the product of \(\displaystyle q_1\) through \(\displaystyle q_{k-1}\).

\(\displaystyle P(X>k) = \dfrac{n}{n}\times\dfrac{n-1}{n}\times\dfrac{n-2}{n}\ \cdot\ \cdot \ \cdot \ \dfrac{n-k+1}{n} = \dfrac{n!}{(n-k)!\ n^k}\),,.....\(\displaystyle k \in [2, 3, ... n]\)

By this formula, we can also see \(\displaystyle P(X>1) = 1\) and \(\displaystyle P(X>n+1) = 0\).

I have spent more time than I intended on part (a), without touching part (b). Perhaps continuing the formalism I started will help you make another step in part (b) ... I wish!

EDIT: hint for part b: set P(X>k) = 0.5, and try to solve for the value of k, which will be the Expectation value (mean) of X. Then use that mean value to define an exponential distribution.