2
$\begingroup$

This question already has an answer here:

A particular professor is known for his arbitrary grading policies. Each paper receives a grade from the set {A, A-, B+, B, B-, C+}, with equal probability, independently of other papers. How many papers do you expect to hand in before you receive each possible grade at least once?

$\endgroup$

marked as duplicate by Did, Adriano, Lord_Farin, Jared, azimut Aug 3 '13 at 8:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Search for "coupon collector's problem"; you'll find loads of related questions on this site, and a Wikipedia article. $\endgroup$ – joriki Mar 1 '13 at 13:37
1
$\begingroup$

If a series of independent events each have probability $p$, then the expected duration until the first occurrence is $$ \begin{align} &1\overbrace{p}^{\text{$1$ success}}+2\overbrace{(1-p)p}^{\begin{array}{l}\text{$1$ failure}\\\text{$1$ success}\end{array}}+3\overbrace{(1-p)^2p}^{\begin{array}{l}\text{$2$ failures}\\\text{$1$ success}\end{array}}+4\overbrace{(1-p)^3p}^{\begin{array}{l}\text{$3$ failures}\\\text{$1$ success}\end{array}}+\dots\\ &=\sum_{k=1}^\infty k\color{#C00000}{p}\color{#00A000}{(1-p)}^{k-1}\\ &=\frac{\color{#C00000}{p}}{(1-\color{#00A000}{(1-p)})^2}\\ &=\frac1p \end{align} $$ The probability of getting a new grade after you have already gotten $k$ grades is $\frac{6-k}{6}$.

Thus, the expected duration to get your first new grade is $\frac66$; the expected duration to get your second new grade is $\frac65$; the expected duration to get your third new grade is $\frac64$; etc.

$\endgroup$
  • $\begingroup$ Necessary, five months after one comment and two answers got posted? $\endgroup$ – Did Aug 3 '13 at 6:59
  • $\begingroup$ @Did: You know, I really should have checked the date on the question when it showed up on the front page. My bad. $\endgroup$ – robjohn Aug 3 '13 at 7:07
0
$\begingroup$

Before the first point at which you have received all 6 grades, you must have passed the first point at which you have received 5 different grades, which occurs after the first point at which you have received 4 different grades, and so on. Due to the linearity of expectation, you can break up your random variable $X$ (number of papers turned in before having received all 6 grades) into the sum of 6 geometric random variables (number of papers turned in before receiving a grade that you haven't received before).


Edit: As joriki and Louis mentioned, this is the Coupon Collector's Problem. I had forgotten what it was called.

$\endgroup$
0
$\begingroup$

This called the "coupon collectors problem". You can search for it.

The way to see the expectation is the following. Break up the process into a sequence of rounds that end each time you get a new paper. Let $N$ be the total number of grades. The length of the $i$th round has geometric distribution with parameter $(N - i + 1)/N$. You can probably take it from here.

$\endgroup$

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