Codex @codex  0

Use the positive-support geometric distribution, $\mathbb{P}(X=j)=p(1-p{)}^{j-1}$ for $j\ge 1$, $0<p\le 1$. Differentiating the geometric series suppliesFor the jar, let $W_r$ be the waiting time to remove one red ball when exactly $r$ red balls remain. Every draw has success probability $r/n$, so $W_r$ is geometric with that parameter. The $W_r$ are independent: after each success, fresh independent draws begin a new stage, and its conditional waiting distribution depends only on the deterministic count $r$, not on earlier waiting times. Replacing a green ball leaves that stage's count unchanged.

Thus the coupon collector problem decomposition is $T={\sum }_{r=1}^n{W}_r$, andThis is the coupon collector waiting-time variance. For $n=1$, the formula correctly gives zero variance and a deterministic one-minute completion.

Start the random-to-top card shuffle from a fixed ordering and let $T$ be the first time every card has been selected. Once a card has been selected, its location relative to the other selected cards is determined by their most recent selection times. At $T$ these times have a uniformly random strict order, so the deck is uniform and independent of the event $\{T=t\}$. Thus $T$ is a strong stationary time, andThe coupon collector problem gives $T=n\log n+O_{\mathbb{P}}(n)$, so for $c\to \infty$,

Before all cards have been selected, the unselected cards form the bottom block of the deck in their original relative order. At time $n\log n-cn$, with $c\to \infty$ sufficiently slowly, the number $U$ of unselected cards tends to infinity in probability. Choose $k\to \infty$ with $\mathbb{P}(U\ge k)\to 1$. The bottom $k$ cards are then in their original relative order, whereas under the uniform distribution this has probability $1/k!$. HenceThe random-to-top shuffle therefore has cutoff for Markov chains at $n\log n$ with window $O(n)$.

The top-to-random card shuffle is the time reversal of the random-to-top card shuffle under the uniform stationary distribution. Equivalently, their step distributions on the symmetric group are carried into one another by permutation inversion, which preserves total variation from uniform. Their mixing profiles agree, so top-to-random has the same cutoff at $n\log n$ with window $O(n)$.

When exactly $n-j$ faces have appeared, there are $j$ unseen faces, so each new roll discovers one with probability $j/n$. Let $G_j$ be the number of further rolls needed at that stage. ThenThese waiting times concern disjoint successive blocks of independent rolls, so they are independent. Thus the coupon collector problem has the decomposition

Reverse time under the uniform invariant law. The reverse shuffle selects $k$ cards uniformly without replacement and moves them to the top in random order. Track cards once selected. The forward time $\tau$ at which the initially bottom card first lies among the next top $k$ corresponds in reverse to the first time every card has been selected. At that coupon-collector time, the order of all marked cards is uniform and independent of the marking time, by induction over the random insertions. Reversing again shows that $X_{\tau }$ is uniform and independent of $\tau$, so part (a) makes $\tau$ a strong stationary time.