Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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 Nov 20 '12 at 21:36
    
@NealYoung it is weird and logical. But fyi, simulation results match your results. –  AJed Nov 20 '12 at 23:57

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
Thanks a lot Neal ! –  AJed Nov 21 '12 at 13:35
    
You're welcome! –  Neal Young Nov 21 '12 at 15:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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