# Expectancy of number of trials

• Dec 28th 2017, 07:50 AM
hedi
Expectancy of number of trials
Five cards are drawn out of a stock of cards. If the cards that have been drawed contain four cards of the same type (Ace, King,same number,queen,etc.),we say we have a a quartet. Repeating the process until all 13 possible quartets are received, what is the expected number of repetitions required?

• Dec 28th 2017, 08:30 AM
SlipEternal
Re: Expectancy of number of trials
I assume there are 52 cards, because if there are more or less than 52, we would need to know the number of cards of each type in the "stock". I assume that each time the process is repeated, the five cards pulled the previous time are replaced (otherwise, we would never be able to get all 13 quartets).

It is impossible to achieve all 13 quartets in less than 13 repetitions. So, if we are to have a chance at succeeding on the 13th pull, we must have 12 of the quartets already pulled and the 13th quartet will be the 13th pull. Similarly, if we pull the 13th quartet on the 14th pull, then in the first 13 pulls, we got only 12 of the quartets, but not the 13th. Let's consider the probability that in n pulls, we pull 12 of the quartets, but not the 13th:

$\dbinom{13}{12}\dbinom{n}{12} \left( \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{12} \left(1 - \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{n-12}$

Then the probability that the next pull is the 13th quartet is: $\dfrac{ \dbinom{5}{4} }{ \dbinom{52}{5} }$

So, the expected value is given by:

\displaystyle \begin{align*} & \sum_{n \ge 12}\dbinom{13}{12}\dbinom{n}{12} \left( \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{13} \left(1 - \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{n-12}(n+1) \\ = & \dbinom{13}{12} \left( \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{13} \sum_{n \ge 12} \dbinom{n}{12} \left(1 - \dfrac{ 48\dbinom{5}{4} }{ \dbinom{52}{5} } \right)^{n-12}(n+1) = 1830101\end{align*}

http://www.wolframalpha.com/input/?i...infinity%7D%5D

Edit: I missed a factor of 48.
• Dec 28th 2017, 08:53 AM
hedi
Re: Expectancy of number of trials
I also got this expression but i suppose we have to multiply by 12! for permutations on the 12 quarters.For the same reason the probability for a quarter in one trial is
13*bin(5,4)*4!*(52-4)/(bin(52,5)*5!).
Do you see a way of computing the expectancy by using indicators?
• Dec 28th 2017, 08:57 AM
SlipEternal
Re: Expectancy of number of trials
Quote:

I also got this expression but i suppose we have to multiply by 12! for permutations on the 12 quarters.For the same reason the probability for a quarter in one trial is
13*bin(5,4)*4!*(52-4)/(bin(52,5)*5!).
Do you see a way of computing the expectancy by using indicators?

I apologize. I missed a factor of 48 for the 5th card that was not part of the quartet. I do not understand what you mean by "indicators". I updated my calculations.
• Dec 28th 2017, 09:04 AM
SlipEternal
Re: Expectancy of number of trials
Also, you can try the experiment with a smaller deck to see if the formula is correct. For example, suppose you have a deck with 24 cards: 4x2, 4x3, 4x4, 4x5, 4x6, 4x7. Find the expected number of pulls to get all six quartets. According to my formula, that would be:

\displaystyle \begin{align*} & \sum_{n \ge 5}\dbinom{6}{5}\dbinom{n}{5} \left( \dfrac{ 20\dbinom{5}{4} }{ \dbinom{24}{5} } \right)^{6} \left(1 - \dfrac{ 20\dbinom{5}{4} }{ \dbinom{24}{5} } \right)^{n-5}(n+1) \\ = & \dbinom{6}{5} \left( \dfrac{ 20\dbinom{5}{4} }{ \dbinom{24}{5} } \right)^{6} \sum_{n \ge 5} \dbinom{n}{5} \left(1 - \dfrac{ 20\dbinom{5}{4} }{ \dbinom{24}{5} } \right)^{n-5}(n+1) = 15301.44\end{align*}

Wolfram|Alpha: Computational Knowledge Engine
• Dec 28th 2017, 09:26 AM
hedi
Re: Expectancy of number of trials
Yes, but the 12 quarters in the first n trials can be permutated so there must be a factor of 12!.Similar consideration in computing the probability of a quarter in a single trial.
• Dec 28th 2017, 10:21 AM
SlipEternal
Re: Expectancy of number of trials
Quote:

Yes, but the 12 quarters in the first n trials can be permutated so there must be a factor of 12!.Similar consideration in computing the probability of a quarter in a single trial.

It is still not correct. I just tried it for the 24 card deck that I showed above, and it turns out that the expected number should be MUCH lower. I ran it 50 times and got an average of 412.611111 repetitions. So, I will need to rethink my solution. It is obviously not correct. Multiplying by 5! certainly would not help, as that would make it an even larger number.
• Dec 28th 2017, 11:22 AM
hedi
Re: Expectancy of number of trials
It must be the stock with 52 cards not less.This experiment shouid be repeatedly run and see if the first time all quartets appear is close to our result.If you take less cards the expectancy will obvioulisly be smaller.
• Dec 28th 2017, 12:13 PM
SlipEternal
Re: Expectancy of number of trials
Quote:

It must be the stock with 52 cards not less.This experiment shouid be repeatedly run and see if the first time all quartets appear is close to our result.If you take less cards the expectancy will obvioulisly be smaller.

You misunderstand my point. I calculated a NEW expected value using a 24 card deck (4 of each card in the deck). I used the same method, but smaller numbers. The expected value was WAYYY too high. A computer program running a monte carlo simulation of this problem would take a long time. I used a smaller subset of the problem to be able to actually run the simulation. The fact that the method is wrong for a 24-card deck shows that it is wrong for a 52-card deck. There is no reason to run the simulation for the 52-card deck to prove the same results. The method I used was flawed.
• Dec 28th 2017, 01:49 PM
SlipEternal
Re: Expectancy of number of trials
Let's try to solve this using recursion:
P(n,r) = Probability of getting r distinct quartets in n repetitions (the multiplicity of each of the r quartets is at least 1)
p = Probability of getting a specific quartet (for example, 4 aces and another card) in a single repetition. We know that $p = \dfrac{48\cdot 5}{ \dbinom{52}{5} }$.
P(r) = Probability of getting any of r distinct quartets in a single repetition. We know that $P(r) = rp$
P(!r) = Probability of not getting any of r distinct quartets in a single repetition. We know that $P(!r) = 1-rp$

Then, we have the following recursion:
$P(n,r) = P(n-1,r)P(!(13-r))+P(n-1,r-1)P(14-r) = (1-(13-r)p)P(n-1,r)+(14-r)pP(n-1,r-1)$
where
$\forall n<r: P(n,r) = 0$
$\forall r>13: P(n,r) = 0$
$\forall 0 \le n \le 13: P(n,n) = \dfrac{13!}{n!}p^n$

We are trying to calculate the expected value:
$\displaystyle \sum_{n\ge 12}(n+1)pP(n,12)$
• Dec 28th 2017, 03:32 PM
SlipEternal
Re: Expectancy of number of trials
I tried working through this a little. It is messy as could be. I doubt you will find a closed solution. You may be able to find the answer using a statistics engine like R.
• Dec 28th 2017, 04:06 PM
hedi
Re: Expectancy of number of trials
The expectancy can be computed as the sum of geometric expectancies of the geometric variables counting the number of experiments needed to obtain the next different quartet.This gives:

(1/48)*bin(52,5)Sum(1/n) from 1 to 13
• Dec 29th 2017, 03:17 AM
SlipEternal
Re: Expectancy of number of trials
Quote:

The expectancy can be computed as the sum of geometric expectancies of the geometric variables counting the number of experiments needed to obtain the next different quartet.This gives:

(1/48)*bin(52,5)Sum(1/n) from 1 to 13

That is still not correct unfortunately.
• Dec 29th 2017, 06:42 AM
SlipEternal
Re: Expectancy of number of trials
Quote:

That is still not correct unfortunately.

Never mind. It turns out that my random function suffered from a predictability issue. It was generating far more "quartets" that in should have. I give up. Maybe Plato can help with this one. Now, I am getting ridiculously large expected values (several orders of magnitude larger). I tried using R to calculate the correct expected value. It did not work out.
• Dec 29th 2017, 07:08 AM
Plato
Re: Expectancy of number of trials
Quote:

Never mind. It turns out that my random function suffered from a predictability issue. It was generating far more "quartets" that in should have. I give up. Maybe Plato can help with this one. Now, I am getting ridiculously large expected values (several orders of magnitude larger). I tried using R to calculate the correct expected value. It did not work out.

No help from here. I simply have no idea what you all have been doing.
Because the question seems to me to be asking the same as the coupon collector problem.
Therefore, I must not understand the setup.