A “two-dimensional” generalization of coupon collectors problem Suppose we have colored balls with numbers. There are $m$ colors and $n$ numbers (so there are $mn$ different kind of balls, appearing with equal probability). What’s the expectation of balls we need to draw to get each number and each color? (For example, when there are two colors and two numbers, a ball with red 1 and blue 2 will do the job).
The ordinary linearity of expectation method no longer works for this variation, and I have not found any obvious related documents or questions related.
 A: The basic idea is to represent the process of drawing "colored balls with numbers" as an absorbing Markov chain.  Then the fundamental matrix gives us the expected number of steps to reach an absorbing state:
$$ N = \sum_{k=0}^\infty Q^k = (I - Q)^{-1} $$
when the probability transition matrix $P$ is written in block form with all absorbing states grouped at the end:
$$ P = \begin{bmatrix} Q & R \\ 0 & I \end{bmatrix} $$
That is, the expected number of steps needed to reach an absorbing state starting from a specified transient (non-absorbing) state will be the entry corresponding to that state in the row vector $N \mathbf{1}$ where $\mathbf{1}$ is the vector of all ones.
States that are not absorbing are called transient states, and one can think of the similarity of the general formula above to the limit of a geometric series as result of moving among the transient states until an absorbing state is reached.
In any case using the case $m = 2$ colors and $n = 2$ numbers described in the Question will illustrate the computation.  Any first step always give us one color and one number, which state we label $(1,1)$.  The absorbing state, both colors and both numbers, we label $(2,2)$.  The transition matrix thus involves three transient states and one absorbing state:
$$ P = \begin{bmatrix}
 1/4 & 1/4 & 1/4 & 1/4 \\
  0  & 1/2 &  0  & 1/2 \\
  0  &  0  & 1/2 & 1/2 \\
  0  &  0  &  0  &  1  \end{bmatrix} $$
$$ I - Q = \begin{bmatrix}
 3/4 & -1/4 & -1/4 \\
  0  & 1/2 &  0  \\
  0  &  0  & 1/2 \end{bmatrix} $$
$$ (I - Q)^{-1} \mathbf 1 = [ 8/3 \;\; 2 \;\; 2 ]^T $$
After one step, giving one color and one number, the expected number of steps until hitting the absorbing state is $8/3$.  In total we expect $1 + 8/3 = 11/3$ steps to reach the absorbing state with two colors and two numbers.
The uniform probabilities among colors as well as among numbers allows us to represent the transient states in a concise fashion, $(i,j)$ where $i$ is the count of distinct colors sampled so far and $j$ is the count of distinct numbers sampled.  Immediately after the first sample is drawn we have $i,j = 1$, so only the states with $1 \le i \le m, 1 \le j \le n$ need to be represented.  Of those $mn$ states, the state $(m,n)$ is absorbing and the other $mn-1$ states are transient.  So $Q$ will be size $(mn-1)\times(mn-1)$, and the fact that sampled counts can never decrease means that $Q$ is upper triangular if we order the states naturally (lexicographically).
Evaluating $(I-Q)^{-1} \mathbf 1$ can therefore be done by backsolving the system $(I-Q) \mathbf v = \mathbf 1$.  This is very efficient in that the matrix is not explicitly inverted and has complexity $O(m^2n^2)$ arithmetic operations.
Once that is done, adding one to the first entry of $\mathbf v$ (accounts for taking the first step) results in the expected number of steps to finish the "two dimensional coupon collector" task.
