Inspired by this question.

Inside a hat there are $n$ slips of paper with the integers $1$ through $n$ on them. The numbers on slips $\{1,2,\ldots,r\}$ are erased and replaced with the numbers $\{r+1,r+2,\ldots,2r\}$ respectively $\left(\text{assume }r\leq\frac{n}{2}\right)$. What is the expected value of papers that need to be picked out of the hat for all the numbers in the hat (without replacement) to be unique? (For each element of $\{r+1,r+2,\ldots,2r\}$, at least one paper containing that element has been chosen).

I have tried to use similar logic to the linked question, but I do not know how to incorporate repeats into the calculations.

  • $\begingroup$ "ro be unique" seems to be contradicted by the next sentence. Let us start with the numbers $1$ to $30$, and let $r=7$. After the deleting and adding, we have two copies of each of $8$ to $14$, and $16$ "singles", $15$ to $30$. Do we want to sample with replacement until we have at least one copy of each of $8$ to $30$? I can look at it (tomorrow) once things are clear. $\endgroup$ – André Nicolas Feb 29 '16 at 7:16
  • $\begingroup$ @AndréNicolas: The numbers remaining in the hat must be unique, not the numbers picked out of the hat. This is indeed equivalent to the next sentence: The numbers in the hat will be unique once at least one instance of each of the duplicated numbers has been picked. The sampling is without replacement. $\endgroup$ – joriki Feb 29 '16 at 8:20
  • $\begingroup$ @AndréNicolas In that scenario, it would be the expected number of papers being drawn until at least one copy of each number $8$ through $14$ has been picked. $\endgroup$ – Arcturus Feb 29 '16 at 15:54

For notational convenience let's assume the numbers $1,\ldots r$ are the duplicated ones. Let $T$ be the number of draws required before everything remaining in the hat is unique. Then $$ E(T)=\sum_{k=0}^n P(T>k)=\sum_{k=0}^n P\left(\bigcup_{i=1}^r B_{i,k}\right)\tag1 $$ where $B_{i,k}$ is the event that no slips labeled $i$ have been seen by the time $k$ draws have been made (and therefore both copies of $i$ are among the remaining $n-k$ slips in the hat). By inclusion-exclusion, we have $$ P\left(\bigcup_{i=1}^rB_{i,k}\right)=\sum_{i=1}^r(-1)^{i-1}{r\choose i}P(B_{1,k}\cap B_{2,k}\cap\cdots\cap B_{i,k}) =\sum_{i=1}^r(-1)^{i-1}{r\choose i}{{n-k\choose 2i}\over{n\choose 2i}}.\tag2 $$ Plugging (2) into (1) looks like a mess, but we can simplify by interchanging the summations and using the "upper summation" identity $$ \sum_{m=0}^n{m\choose a}={n+1\choose a+1}\tag3$$ to obtain $$ E(T) = \sum_{i=1}^r(-1)^{i-1}{r\choose i}{{n+1\choose 2i+1}\over{n\choose 2i}}=\sum_{i=1}^r(-1)^{i-1}{r\choose i}{n+1\over2i+1}.\tag4 $$ This can be simplified further. Introduce an $i=0$ term in (4) and rearrange to obtain $$ {E(T)\over n+1}=1-\sum_{i=0}^r(-1)^i{r\choose i}\frac1{2i+1}.\tag5 $$ Finally apply the identity $$ \sum_{k=0}^n(-1)^k{n\choose k}\frac1{k+\frac12}={1\over\frac12{n+\frac12\choose n}}:={n!\over(\frac12)(\frac32)\cdots(n-\frac12)(n+\frac12)}\tag6 $$ (where ${n+\frac12\choose n}$ is a generalized binomial coefficient) to (5) and get $$ {E(T)\over n+1}=1-\frac1{{r+\frac12\choose r}}. $$ With $r=0$ this gives $E(T)=0$, as expected. With $r=1$ we get $E(T)=\frac13(n+1)$, and with $r=2$ we get $E(T)=\frac7{15}(n+1)$.

Note: Identity (6) can be derived by considering the binomial expansion of $$ t^{-1/2}(1-t)^n = \sum_{k=0}^n(-1)^k{n\choose k}t^{k-1/2} $$ and then integrating over $t$ from $0$ to $1$. It is the $x=1/2$ case of the more general identity $$ \sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k+x} = \frac{1}{x\binom{n+x}{n}} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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