Probability of getting 3 specific characters from a pool of 400, with 200 attempts, with repetitions

Question

I'm playing a game where you can get characters from a pool of 400, if you get one character and dismiss it you can get that character again in another attempt, but if you take the character with you, you can't get it again. Also, you can only get one character per attempt. So, what is the probability of getting 3 specific characters after 200 attempts? Consider I would only get those 3 and dismiss all the rest.

I came to a result, but I'm not sure if I'm right:

Assuming they're all equally probable, and I already have 7 characters, the chances of getting the first one is $1 - (1 - 1/393)^{200} = 0.3992$. The chances for the second are $1 - (1 - 1/392)^{199} = 0.3985$, since I would take the first one, and I'd have to find it in the other 199 attempts. The chances for the third would be $1 - (1 - 1/391)^{198} = 0.3977$.

So, the chances of getting those 3 events in the same 200 attempts would be the multiplication of the probabilities of those 3 events alone:

$0.3992 * 0.3985 * 0.3977 = 0.0632$

Is this correct? It's been some years since I last did something like this in university, so it's likely that I'm missing something.

Answer 1

Let's look at possible outcomes. In each outcome, you have 200 attempts. Each attempt can be broken down as follows:

Let $a_1$ be the number of the attempt where you obtain the first desired character. Let $a_2$ be the number of the attempt where you obtain the second desired character. Let $a_3$ be the number of the attempt where you obtain the final desired character.

Then the probability of not getting one of the three desired characters prior to attempt $a_1$ is $\dfrac{390}{393}$. Between $a_1$ and $a_2$, it is $\dfrac{390}{392}$. Between $a_2$ and $a_3$, it is $\dfrac{390}{391}$.

So, your total probability of obtaining all three characters is:

$$\begin{align*} & \sum_{a_1 = 1}^{198} \sum_{a_2 = a_1+1}^{199} \sum_{a_3 = a_2 + 1}^{200} \left(\dfrac{390}{393}\right)^{a_1-1}\left(\dfrac{3}{393} \right)\left(\dfrac{390}{392}\right)^{a_2-a_1-1}\left(\dfrac{2}{392} \right) \left(\dfrac{390}{391}\right)^{a_3-a_2-1} \left(\dfrac{1}{391} \right) \\ = & 6\sum_{a_1 = 1}^{198} \sum_{a_2 = a_1+1}^{199} \sum_{a_3 = a_2+1}^{200} \dfrac{(390)^{a_3-3}}{(393)^{a_1}(392)^{a_2-a_1}(391)^{a_3-a_2}}\end{align*}$$

To get an answer, you will need a computer algebra system, such as Mathematica.

Here is how I got an answer from Wolframalpha:

I started change the summation to the following:

$$\sum_{a=1}^{n-2}\sum_{b=a+1}^{n-1}\sum_{c=b+1}^n \dfrac{k^{c-3}}{(k+3)^a(k+2)^{b-a}(k+1)^{c-b}}$$

Here, $k=390, n=200$.

This was still too complex for Wolframalpha, so I just used the innermost sum and simplified to:

$$\dfrac{6}{k^2}\sum_{a=1}^{n-2}\sum_{b=a+1}^{n-1}\left(\dfrac{k^b(k+1)^n-k^n(k+1)^b}{(k+3)^a(k+2)^{b-a}(k+1)^n}\right)$$

Again, this was too complex, so again, I just used the innermost sum and simplified to:

$$\dfrac{3}{k^2}\sum_{a=1}^{n-2}\left(\dfrac{k^{n+1}\big((k+1)^n(k+2)^{a-n}-2(k+1)^a\big)+k^{a+1}(k+1)^n+k^n\big(2(k+1)^n(k+2)^{a-n}-2(k+1)^a)\big)}{(k+3)^a(k+1)^n}\right)$$

Finally, this was easy enough for Wolframalpha to calculate:

$$3k^{n-1}\left( -2(k+1)^{-n}+4(k+2)^{-n}-2(k+3)^{-n}\right)+k^n\left(-3(k+1)^{-n}+3(k+2)^{-n}-(k+3)^{-n}\right) + 1-\dfrac{3}{k^2}\left(\dfrac{k}{k+1}\right)^n+\dfrac{12}{k^2}\left(\dfrac{k}{k+2}\right)^n-\dfrac{9}{k^2}\left(\dfrac{k}{k+3}\right)^n$$

To make this a little more legible, let $p_1 = \dfrac{k}{k+1}, p_2 = \dfrac{k}{k+2}, p_3 = \dfrac{k}{k+3}$.

$$1-3p_1^{n-2}+3\left(\dfrac{(k+3)(k+1)}{(k+2)^2}\right)p_2^{n-2}-p_3^{n-2}$$

Now, plugging in $k=390, n=200$:

$$0.063475849312166152635769452237666622299692139359480965745$$

Answer from Wolframalpha

Using this final formula, you can fix $k=390$, but let $n$ vary as the number of attempts you wish to try. Now, you can calculate the value of $n$ that will give you a certain probability of achieving the three characters you desire:

$$1-3\left(\dfrac{390}{391}\right)^{n-2}+3\left(\dfrac{153,663}{153,664}\right)\left(\dfrac{195}{196}\right)^{n-2}-\left(\dfrac{130}{131}\right)^{n-2} \ge p$$

Here are some calculations for $p=0.5, p=0.75, p=0.9$ respectively:

$$n \ge 618, n\ge 936, n\ge 1317$$

Answer 2

My earlier answer using inclusion-exclusion was incorrect, because it didn't take account of the changing size of the player pool. I'll try a different way.

The probability that none of the three players is chosen is $$\left(\frac{390}{393}\right)^{200}.$$

To compute the probability that exactly one of the three players is chosen, let us says he is chosen on turn $n$. The probability that exactly one player is chosen is $$\begin{align} p_1&=3\sum_{n=1}^{200}\left(\frac{390}{393}\right)^{n-1}\left(\frac{1}{393}\right)\left(\frac{390}{392}\right)^{200-n}\\ &=3\left(\frac{390}{392}\right)^{200}\frac1{390} \sum_{n=1}^{200}\left(\frac{390}{393}\right)^n \left(\frac{392}{390}\right)^n\\ &=3\left(\frac{390}{392}\right)^{200}\frac1{390} \sum_{n=1}^{200}\left(\frac{392}{393}\right)^{200}\\ &=\frac3{390}\left(\frac{390}{392}\right)^{200}\left(\frac{\frac{392}{393}-\left(\frac{392}{393}\right)^{201}}{1-\frac{392}{393}}\right)\\ &=\frac{292}{130}\left(\left(\frac{390}{392}\right)^{200} -\left(\frac{390}{393}\right)^{200}\right) \end{align}$$ after some arithmetic.

In the same way, we can compute the probability that exactly two players are chosen. There are $3$ ways to choose the first player and $2$ ways to choose the second, and if we say that the first is chosen on turn $n$, and the second on turn $m$, we get $$ 6\sum_{n=1}^{199}\sum_{m=n+1}^{200} \left(\frac{390}{393}\right)^{n-1} \left(\frac{1}{393}\right) \left(\frac{390}{392}\right)^{m-n+1} \left(\frac{1}{392}\right) \left(\frac{390}{391}\right)^{200-m}$$

In the same way as above, this can be simplified into a compact expression by using geometric series, but I leave that for someone more ambitious than I.