3
$\begingroup$

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$ ?

$\endgroup$
  • 3
    $\begingroup$ 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)$. $\endgroup$ – Neal Young Nov 20 '12 at 21:36
  • $\begingroup$ @NealYoung it is weird and logical. But fyi, simulation results match your results. $\endgroup$ – AJed Nov 20 '12 at 23:57
7
$\begingroup$

$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)$.

$\endgroup$

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.