On the coupon collector problem

Question

Originally from Proposition 8 of Tao's note: https://terrytao.wordpress.com/2015/10/23/275a-notes-3-the-weak-and-strong-law-of-large-numbers/comment-page-1/#comment-682885.

Let ${N}$ be a natural number, and let ${Y_1, Y_2, \dots}$ be an infinite sequence of “coupons”, which are iid and uniformly distributed from the finite set ${\{1,\dots,N\}}$. For each ${i=0,\dots,N}$, let ${T_{i,N}}$ denote the first time one has collected ${i}$ coupons out of ${N}$, thus ${T_{i,N}}$ is the first non-negative integer such that ${\{Y_1,\dots,Y_{T_{i,N}}\}}$ has cardinality ${i}$, with

$\displaystyle 0 = T_{0,N} < T_{1,N} < \dots < T_{N,N} = T_N$.

Write ${X_i := T_{i,N} - T_{i-1,N}}$ for ${i=1,\dots,N}$. For any choice of natural numbers ${j_1,\dots,j_N}$, it is stated that "in order for the event ${X_1 = j_1 \wedge \dots \wedge X_N = j_N}$ to hold, the first coupon ${Y_1}$ can be arbitrary, but the coupons ${Y_2,\dots,Y_{j_1}}$ have to be equal to ${Y_1}$; then ${Y_{j_1+1}}$ must be from one of the remaining ${N-1}$ elements of ${\{1,\dots,N\}}$ not equal to ${Y_1}$, and ${Y_{j_1+2},\dots,Y_{j_1+j_2}}$ must be from the two-element set ${\{Y_1,Y_{j_1+1}\}}$; and so on and so forth up to ${Y_{j_1+\dots+j_N}}$."

Question: The statement in bold seems to hold for $T_{i,N}$ defined to be the last time one has collected $i$ coupons out of $N$, rather than the first time. What do I misunderstand?

Answer 1

There is indeed an error, but it’s not that the $T_{i,N}$ should be defined as you suggest. They’re defined correctly, and your suggested definition wouldn’t work, not least because there’s no last time at which one has collected all $N$ coupons.

Rather, in the statement in bold the indices are wrong, and the segmentation by semicolons confusingly groups factors from different terms in the sum together. A correct version with more natural segmentation would be:

In order for the event $X_1=j_1\land\cdots\land X_N=j_N$ to hold, we must have $j_1=1$ and the first coupon $Y_{j_1}$ can be arbitrary; then the coupons $Y_{j_1+1},\ldots,Y_{j_1+j_2-1}$ have to be equal to $Y_{j_1}$, and $Y_{j_1+j_2}$ must be from one of the remaining $N-1$ elements of $\{1,\ldots,N\}$ not equal to $Y_{j_1}$; then $Y_{j_1+j_2+1},\ldots,Y_{j_1+j_2+j_3-1}$ must be from the two-element set $\{Y_{j_1},Y_{j_1+j_2}\}$, and $Y_{j_1+j_2+j_3}$ must be from the remaining $N-2$ elements of $\{1,\ldots,N\}$; and so on and so forth up to $Y_{j_1+\cdots+j_N}$.