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

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.

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.