<p>$E[m]$ equals $n(H_n-1)$.  </p>

<p>Here's a more complete proof sketch, following the argument suggested in my comment.</p>

<p>We start by showing that each permutation of the first $k-1$ elements is equally likely.</p>

<p>More precisely, let $X^*=(X_1,X_2,\ldots,X_K, \ldots)$ be an infinite random sequence where each $X_i$ is drawn independently and uniformly from $S$.  Let r.v. $K$ be the first index at which all elements of $S$ have been seen. Let r.v. $X'=(X_1,X_2,\ldots,X_{K-1})$.</p>

<p>Let $i$ denote any positive integer. Let $s$ denote any element of $S$.
Let $x=(x_1,x_2,\ldots,x_{i-1})$ denote any value of $X'$ that can occur,
given that $K=i$ and $X_K = s$.  (That is, $x$ is any length-$(i-1)$ sequence in which
each element of $S-\{s\}$ occurs, and $s$ does not occur.)</p>

<p>Let $\pi$ be any permutation of $[i-1]$.
Let $\pi(x)$ denote sequence $x$, permuted by $\pi$.</p>

<p><strong>Lemma:</strong> <em>Fix any such $i$, $s$, $x$, and $\pi$. Conditioned on $K=i$ and $X_k=s$, the probability that $X' = x$ is the same as the probability that $X' = \pi(x)$.</em></p>

<p><em>Proof.</em>  To save typing, let $(i,s)$ denote the event that $K=i\wedge X_K=s$.</p>

<p>We want to show $\Pr[X'=x ~|~ (i,s)] = \Pr[X'=\pi(x) ~|~ (i,s)]$.</p>

<p>Let $x\prec X^*$ denote that $x$ is a prefix of $X^*$. 
Let $x,s\prec X^*$ denote that $(x_1,\ldots,x_{i-1},s)$ is a prefix of $X^*$. 
Note that 
$$\Pr[X' = x ~|~ (i,s)]\,\Pr[(i,s)] ~=~ \Pr[X' = x \wedge (i,s)] ~=~ \Pr[x,s\prec X^*] ~=~ \frac{1}{n^i}.$$
Thus, 
$$\Pr[X' = x ~|~ (i,s)] ~=~ \frac{1}{n^i \Pr[(i,s)]}.$$
Since the right-hand side is independent of $x$,
and $\pi(x)$ is also a possible value of $X'$,
$\Pr[X' = \pi(x) ~|~ (i,s)]$ also equals the right-hand side above.  QED</p>

<p><strong>Corollary:</strong> <em>Randomly permuting the first $k-1$ elements of $X$
(as described in the question) does not change the distribution of $X$.</em></p>

<p>This implies that the distribution of the r.v. $m$ as defined in the question
(with permutation of the first $k-1$ elements)
is the same as the distribution of $m$ if the elements are not permuted.
That is, $m$ is distributed as the first index at which $n-1$ distinct
elements in $S$ have been seen.  By a standard calculation, 
<em>$E[m]$ equals $n(H_{n}-1)$.</em></p>

CC BY-SA 3.0
2012-11-21T06:25:00.690Z
2012-11-21T06:38:53.887Z
2012-11-21T06:38:53.887Z
Neal Young
<p>Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x _i$ is the element drawn at the $i^{th}$ draw. In here, $k = n H_n$ following the standard solution of the coupon collector problem. </p>

<p>Note that $x _k$ have been seen only once. We create the $S'$ = $\{S - x _k\}$ and $X' = \{X - x _k\}$. We shuffle $X'$ and get a shuffled series $\{p(x'_1), ..., p(x' _{k-1})\}$, where $p(x' _i)$ is the $i^{th}$ drawn element from the shuffled set $X'$. What is the smallest index $m$ such that the sequence $\{p(x' _1), ..., p(x' _m)\}$ contains all elements in $S'$ ? </p>

<p>Can we simply assume that $m = (n-1) H _{n-1}$ following the same logic of coupon collector ?  or is $k$ is too small to assume that the distribution of $X'$ is uniform ? </p>

<p>If not, then what is the expected value of $m$ ?</p>

CC BY-SA 3.0
2012-11-20T21:36:29.287Z
I guess randomly permuting the first $k-1$ elements of $X$ does not change the distribution of $X$.  So, $m$ is distributed the same as the number of draws until $n-1$ distinct elements have been seen.  By the standard argument, that gives $E[m]$ equals $n(H_n-1)$.
Neal Young
CC BY-SA 3.0
2012-11-20T23:57:11.727Z
@NealYoung it is weird and logical. But fyi, simulation results match your results.
AJed
<ds.algorithms><pr.probability><randomness><randomized-algorithms>
Coupon collector - the effect of randomization
AJed
# Coupon collector - the effect of randomization

(Asked by: username_0 on 2012-11-20)

Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x \_1, ..., x \_k\}$ until all elements of $S$ are seen, where $x \_i$ is the element drawn at the $i^{th}$ draw. In here, $k = n H\_n$ following the standard solution of the coupon collector problem.

Note that $x \_k$ have been seen only once. We create the $S'$ = $\{S - x \_k\}$ and $X' = \{X - x \_k\}$. We shuffle $X'$ and get a shuffled series $\{p(x'\_1), ..., p(x' \_{k-1})\}$, where $p(x' \_i)$ is the $i^{th}$ drawn element from the shuffled set $X'$. What is the smallest index $m$ such that the sequence $\{p(x' \_1), ..., p(x' \_m)\}$ contains all elements in $S'$ ?

Can we simply assume that $m = (n-1) H \_{n-1}$ following the same logic of coupon collector ? or is $k$ is too small to assume that the distribution of $X'$ is uniform ?

If not, then what is the expected value of $m$ ?

**Tags:** ds.algorithms, pr.probability, randomness, randomized-algorithms
> **Comments:**
> **username_1**: I guess randomly permuting the first $k-1$ elements of $X$ does not change the distribution of $X$.  So, $m$ is distributed the same as the number of draws until $n-1$ distinct elements have been seen.  By the standard argument, that gives $E[m]$ equals $n(H_n-1)$.  
> **username_0**: @NealYoung it is weird and logical. But fyi, simulation results match your results.  

---

## 1 answers

### Answer by username_1 on 2012-11-21. Score: 7 | Accepted answer

$E[m]$ equals $n(H\_n-1)$.

Here's a more complete proof sketch, following the argument suggested in my comment.

We start by showing that each permutation of the first $k-1$ elements is equally likely.

More precisely, let $X^\*=(X\_1,X\_2,\ldots,X\_K, \ldots)$ be an infinite random sequence where each $X\_i$ is drawn independently and uniformly from $S$. Let r.v. $K$ be the first index at which all elements of $S$ have been seen. Let r.v. $X'=(X\_1,X\_2,\ldots,X\_{K-1})$.

Let $i$ denote any positive integer. Let $s$ denote any element of $S$.
Let $x=(x\_1,x\_2,\ldots,x\_{i-1})$ denote any value of $X'$ that can occur,
given that $K=i$ and $X\_K = s$. (That is, $x$ is any length-$(i-1)$ sequence in which
each element of $S-\{s\}$ occurs, and $s$ does not occur.)

Let $\pi$ be any permutation of $[i-1]$.
Let $\pi(x)$ denote sequence $x$, permuted by $\pi$.

**Lemma:** *Fix any such $i$, $s$, $x$, and $\pi$. Conditioned on $K=i$ and $X\_k=s$, the probability that $X' = x$ is the same as the probability that $X' = \pi(x)$.*

*Proof.* To save typing, let $(i,s)$ denote the event that $K=i\wedge X\_K=s$.

We want to show $\Pr[X'=x ~|~ (i,s)] = \Pr[X'=\pi(x) ~|~ (i,s)]$.

Let $x\prec X^\*$ denote that $x$ is a prefix of $X^\*$.
Let $x,s\prec X^\*$ denote that $(x\_1,\ldots,x\_{i-1},s)$ is a prefix of $X^\*$.
Note that
$$\Pr[X' = x ~|~ (i,s)]\,\Pr[(i,s)] ~=~ \Pr[X' = x \wedge (i,s)] ~=~ \Pr[x,s\prec X^\*] ~=~ \frac{1}{n^i}.$$
Thus,
$$\Pr[X' = x ~|~ (i,s)] ~=~ \frac{1}{n^i \Pr[(i,s)]}.$$
Since the right-hand side is independent of $x$,
and $\pi(x)$ is also a possible value of $X'$,
$\Pr[X' = \pi(x) ~|~ (i,s)]$ also equals the right-hand side above. QED

**Corollary:** *Randomly permuting the first $k-1$ elements of $X$
(as described in the question) does not change the distribution of $X$.*

This implies that the distribution of the r.v. $m$ as defined in the question
(with permutation of the first $k-1$ elements)
is the same as the distribution of $m$ if the elements are not permuted.
That is, $m$ is distributed as the first index at which $n-1$ distinct
elements in $S$ have been seen. By a standard calculation,
*$E[m]$ equals $n(H\_{n}-1)$.*


---

