Coupon collector problem and Markov chains The coupon collector problem is well known, but there is something troubling me about it.
There are $N$ coupons to be drawn at random, with replacement. Let $p_n=(N-n)/N$. This is the chance of drawing a new coupon when you have $n$ of them. I wish to solve the problem is two different ways.
1) Let $t_n$ be the time to collect the $n$th coupon after $n-1$ of them have been collected. This treats the number of coupons collected as given and the required time as a random variable.
Then, $t_n$ has distribution $p_n(1-p_n)^{t_n}$, with average $1/p_n$.
Expected time for collecting all $N$ coupons is thus $\sum_{n=1}^N1/p_n=NH_N$, where $H_N$ is the harmonic number.
2) I want to approach the problem via a Markov chain in which $P_t(n)$ is the probability that at time $t$ we have $n$ coupons. This is somewhat complementary to the previous approach in that it treats the required time  as given and the number of coupons collected as a random variable.
The evolution equation is $P_t(n)=P_{t-1}(n-1)p_n+P_{t-1}(n)(1-p_n)$. The Markov transition matrix is easy to write down and it is easy to see that its eigenvalues are precisely the numbers $p_n$.
So, finally, the question is: Can I recover the result that the expected time for collecting all $N$ coupons is $NH_N$ from knowledge of the eigenvalues of the Markov matrix? They should control the time evolution, right?
 A: In the context of Markov chains your question boils down to that of finding the expected hitting time of a given state of the Markov chain.
You correctly identified that we can define the transition matrix to be
$$
P = \left(
\begin{array}{ccccc}
0 & 1 & 0 & 0 & \cdots & 0 & 0 \\
0 & q_1 & p_1 & 0 & \cdots & 0 & 0  \\
0 & 0 & q_2 & p_2 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \cdots & q_{N-1} & p_{N-1} \\
0 & 0 & 0 & 0 & \cdots & 0 & 1
\end{array}
\right)
$$
where $p_n$ is the probability of obtaining a new coupon when you have $n$ of them, and $q_n = 1-p_n$, and the transition matrix is $(N+1) \times (N+1)$ with $P(m,n)$ denoting the probability that you have picked $m$ of the coupons up to now, and you have $n$ coupons in the next step; $m, n \in \{0,1,\ldots, N\}$.
Let $\mathbf E_{m,n}$ denote the expected hitting time of site $n$ starting from site $m$; so we will be interested in the special case $\mathbf E_{0,N}$. One can show by conditioning on the next step, that
$$ \mathbf E_{m,n} = \begin{cases}
0, & \text{if m = n,} \\
1 + \sum_{k}\mathbf E_{k,n}P_{m,k}, & \text{else.}
\end{cases}
$$ 
For the particular case we have, this becomes
\begin{align*}
\mathbf E_{0,N} & = 1 + \mathbf E_{0,N}P_{0,0} +  \mathbf E_{1,N}P_{0,1} \\
 \mathbf E_{0,N}(1 -P_{0,0}) & = 1 + \mathbf E_{1,N}P_{0,1} \\
 \mathbf E_{0,N}p_0 & = 1 + \mathbf E_{1,N}p_0 \\
\mathbf E_{0,N}& = \frac1{p_0} + \mathbf E_{1,N}\\
\end{align*}
Similar calculation gives
$$\mathbf E_{k,N} = \frac{1}{p_k} + \mathbf E_{k+1,N}$$
And so we derive the same Harmonic series expression
$$\mathbf  E_{0,N} = \frac1{p_0} +\mathbf  E_{1,N} = \cdots = \sum_{k=0}^{N-1}\frac{1}{p_k}.$$
The formula we started with `hints' at there being a matrix algebra approach; if there was not the condition that $\mathbf E_{m,m} = 0$ then we could write $E = J + PE$ (with $J$ the matrix of all $1$s), unfortunately the additional condition gets in the way!
This is not the case if you ask for $G_{m,n}$ the expected number of visits to state $n$, starting from $m$; this matrix satisfies the identity $G =I + GP$, which leads to the identity $G = (I-P)^{-1}$ so long as the matrix is invertible (which occurs when there is an absorbing state); in this context $G_{m,n}$ can be interpreted as the total number of draws of coupons required when you have $n$ to get to $n+1$, when $m \leq n$.
Mixing Times and Spectral Gap
Eigenvalues of transition matrices do play a role in describing convergence of Markov chains to their stationary distributions: in your context the stationary distribution is achieved once all $N$ coupons have been collected.
The theory is simpler in the context of reversible Markov chains (which yours is not).
We consider the value
$$d(t) = \max_{m} \frac12 \sum_n \left( P^t_{m,n} - \pi_n \right),$$
where $\pi_n$ denotes the stationary distribution of the Markov chain. In your context, $\pi_n = \delta_N(n)$, i.e. equals $1$ if $n = N$ and is $0$ otherwise.
$d(t)$ is a measure of the distance of a Markov chain from its stationary distribution: it is equivalent to the maximum (over states $m \in \{0,1,\ldots,N\}$) total variation distance of the Markov Chain at time $t$ to the stationary distribution.
The mixing time $t_{\text{mix}}(\epsilon)$, at level $\epsilon > 0$, is then the smallest $t \geq 0$ such that $d(t) < \epsilon$. This indicates the shortest time $t$ required before you can be confident (up to the level $\epsilon$) that the Markov chain has reached stationarity.
In the case of a reversible transition matrix (again: your situation is not reversible) we have the inequality
$$t_{\text{mix}}(\epsilon) \leq \log \left( \frac{1}{\epsilon \pi_{\min} } \right) \frac{1}{1 - \lambda^*},$$
where $\pi_{\min} = \min_m \pi_m$, and 
$$\lambda^* = \max\{|\lambda|\, \colon \, \lambda \in \text{Spec}(P), \, \lambda \neq 1\},$$
the value $1 - \lambda^*$ is known as the spectral gap of the Markov chain. Note that the reversibility assumption is really essential here: the coupon collector is a perfect example that this cannot hold for all Markov chains, since for the coupon collector $\pi_{\min} = 0$, and the above bound is ill-defined.
The theory of mixing times for non reversible Markov chains is less well established, though there are some results. This paper states a lower bound on the mixing time in the absence of reversibility [Note: The paper has been redacted as the bound was in fact previously known; I could not find an alternate source on a quick web search however].
So in conclusion: yes, there is a way to connect the spectrum to the time to collect all of the coupons, but the machinery is heavy, and explicit results can be achieved much more simply.
... Of course it would be very elegant if we could  relate the time to collect all coupons to the trace $\text{Tr}(P^{-1}) = \sum p_m^{-1}$, but I haven't looked at this.
