Compute the expected number of tiles needed filled to fill a row in a grid

Question

I want to compute the expected number of tiles I would have to fill to fill a row of $n$ tiles in a $n\times k$-grid. No tiles can be filled more than once. In other words, if we fill a tile in a $n\times k$-grid each turn with uniform probability and if $X$ is the number of turns needed to fill a row of $n$ tiles in the grid, what is $E[X]$?

I have tried with some small examples. For example for a $2\times 3$-grid, I reason as follows: It does not matter which tile we fill first. Then it is a one in five chance to pick the same row as the first one, so the probability of filling a row in two turns is $\frac{1}{5}$. To complete a row in three turns, we need to fill a tile in a different row, and then in one of the same. To complete a row in four turns, we need to fill a tile in each different row, then any tile we fill will complete a row. We get the following table: $$\begin{array}{c|c|} & \text{Probability to fill a row in $x$ turns} \\ \hline \text{P(X=2)} & \frac{1}{5} \\ \hline \text{P(X=3)} & \frac{4}{5}\cdot\frac{2}{4} \\ \hline \text{P(X=4)} & \frac{4}{5}\cdot\frac{2}{4}\cdot1 \end{array}$$ From here we can calculate the expected value as $E[X] = 2\cdot\frac{1}{5}+3\cdot\frac{2}{5}+4\cdot\frac{2}{5} = \frac{16}{5}$, so we expect to complete a row in a little more than 3 turns.

It quickly gets convoluted with larger examples though, and I can't find a pattern. I know factorials in the denominators are involved in probabilities, because the number of tiles to choose to fill decreases by one each time.

I have not been able to find any similar sounding questions. In this question they answer something related, namely what the probability of filling a row of 10 after 20 turns in a $7\times10$-grid. I feel like this might be of some help, but I am not able to generalize the solution provided there. Furthermore this does not answer what the expected number of turns to fill a row in a given grid is.

It would also be interesting to see what kind of probability distribution this process has. Intuitively I think this shares some similarities with the geometric distribution, but not directly.

I thought of this problem when doing a picture puzzle, and wondered how many puzzle pieces one would need to expect a row to be filled.

Answer 1

Going through the steps from start to finish will prove hard for larger grids as we would have to, I think, in each of $O(nk)$ turns keep track of how many combinations have the same amount of rows filled to the same degree giving us $O(n^k)$ terms to calculate and $O(n^{k+1}k)$ complexity will only allow solving for very small grids.

However, skipping to the end like in the other question's answer we can say that in turn $t$ there are $\binom{kn}t$ combinations of choosing filled tiles and we only need to find those with exactly one full row and identify how we got there.

Let $f(t,m)$ denote the combinations of filled tiles in turn $t$ with exactly $m$ full rows.

Choosing a full row and tiles outside of it $\binom k1\binom{kn-n}{t-k}$ counts one or more full row and it counts combinations with two full rows twice, combinations with three full rows thrice and so on.

$f(t,1)=\binom k1\binom{kn-n}{t-n}-2f(t,2)-3f(t,3)-\dotsb$

Choosing two full rows and tiles outside of them counts combinations with three rows $\binom 32$ times and so on.

$f(t,2)=\binom k2\binom{kn-2n}{t-2n}-\binom 32f(t,3)-\binom 42f(t,4)-\dotsb$

There can be at most $\lfloor \frac tn\rfloor$ full rows, and $f(t,\lfloor \frac tn\rfloor)$ doesn't overcount anything.

$$f(t,m)=\binom km\binom{kn-mn}{t-mn}-\sum_{i=m+1}^{\lfloor\frac tn\rfloor}\binom imf(t,i)$$

For each of the combinations with exactly 1 full row there were $t$ combinations of how the grid looked in previous turn, and one of the $n$ tiles in our single full row had to be filled last.

$$P(X=t)=\frac nt\frac {f(t,1)}{\binom{kn}t} \text{for $t\in\{1,\dotsc,kn-k+1\}$}$$

Recursion can be eliminated to achieve a sum of sums and a different approach might yield that answer. Now the solution is $O(nk^3)$ and I think that's the complexity of the problem. I won't hazard a guess as to the characteristics of any distributions involved.