Card shuffling and harmonic numbers

Question

Below is a simple proof of one connection between card shuffling and harmonic numbers. I'm interested in references for this if it's already known, as well as alternative methods of proof. (Can the result be obtained from the fact that the expected number of cycles in a random $n$-permutation equals the $n$th harmonic number?)

---

For a deck of $n\ge 1$ distinct playing cards, define a top shuffle to be the operation of moving the top card down to one of the $n-1$ other positions, choosing this target position uniformly at random.

Let $T$ denote the number of top shuffles needed to make every card occupy the top position at least once.

Claim: The expected value of $T$ is given by the following formula: $$\mathbb{E}(T)=(n-1)\,\left({1\over 1}+{1\over 2}+{1\over 3}+\cdots+{1\over n-1}\right).$$

Proof: WLOG, represent the shuffled deck by a permutation of $(1,\ldots,n)$, the leftmost position being the "top". Let $s_x$ denote the expected number of top shuffles needed to make card $n$ occupy the top position, given that the deck is initially the permutation $x$. Now, if the deck is initially $(1,2,..,n)$, then every card will visit the top position iff card $n$ visits the top position, so we seek $s_{1,2,..,n}=\mathbb{E}(T).$

The following system of equations is immediate from the definitions:

$$\begin{align}s_{n,1,..,n-1}&=0\\[2ex] s_{1,n,2,3,..,n-1}&=1+{1\over n-1}\left(\underbrace{s_{n,1,2,3,..,n-1}+s_{n,2,1,3,..,n-1}+\ldots+s_{n,2,3,..,n-1,1}}_{n-1}\right)\\[2ex] s_{1,2,n,3,..,n-1}&=1+{1\over n-1}\left(\underbrace{s_{2,1,n,3,..,n-1}}_{1}+\underbrace{s_{2,n,1,3,..,n-1}+\ldots+s_{2,n,3,..,n-1,1}}_{n-2}\right)\\[2ex] s_{1,2,3,n,..,n-1}&=1+{1\over n-1}\left(\underbrace{s_{2,1,3,n,..,n-1}+s_{2,3,1,n,..,n-1}}_{2}+\underbrace{s_{2,3,n,1,..,n-1}+\ldots+s_{2,3,n,..,n-1,1}}_{n-3}\right)\\[2ex] \cdots\\[2ex] s_{1,2,3,..,n-1,n}&=1+{1\over n-1}\left(\underbrace{s_{2,1,3,..,n-1,n}+s_{2,3,1,..,n-1,n}+\ldots+s_{2,3,..,n-1,1,n}}_{n-2}+\underbrace{s_{2,3,..,n-1,n,1}}_{1}\right)\\[2ex] \end{align}$$

Note that these $n$ equations actually involve only $n$ unknowns, due to the fact that $s_x$ depends only on the position of $n$ in the permutation $x$. Therefore, let us define $t_k$ to be the expected number of top shuffles needed to make card $n$ occupy the top position, given that the deck has card $n$ in position $k$. Then we can rewrite the above system as follows:

$$\begin{cases}t_1&=0\\[2ex] t_k&=1+{1\over n-1}\left((k-2)\,t_k+(n-k+1)\,t_{k-1}\right)\quad (k=2,..,n)\\[2ex] \end{cases}$$ and hence, rearranging the equations, $$\begin{cases}t_1&=0\\[2ex] t_k&={n-1\over n-k+1}+t_{k-1}\quad (k=2,..,n)\\[2ex] \end{cases}$$ giving $$\begin{align}\mathbb{E}(T)=t_n&={n-1\over 1}+t_{n-1}\\[2ex] &={n-1\over 1}+{n-1\over 2}+t_{n-2}\\[2ex] &\cdots\\[2ex] &={n-1\over 1}+{n-1\over 2}+\cdots+{n-1\over n-1}+t_1\\[2ex] &=(n-1)\,\left({1\over 1}+{1\over 2}+{1\over 3}+\cdots+{1\over n-1}\right) \end{align}$$

Answer 1

This is way too complicated. When card $n$ is in position $k+1$, the probability that a top shuffle moves it up to position $k$ is $\frac{n-k}{n-1}$. Thus the expected number of shuffles required to move it up from position $k+1$ to position $k$ is $\frac{n-1}{n-k}$, so the expected number of shuffles required to move it up from position $n$ to position $1$ is

$$ \sum_{k=1}^{n-1}\frac{n-1}{n-k}=\sum_{k=1}^{n-1}\frac{n-1}k=(n-1)\sum_{k=1}^{n-1}\frac1k\;. $$

You may also want to take a look at the coupon collector's problem.