Percolative process distribution not equivalent to coupon collector problem distribution

Question

I have a process where; given a $n\times 1$ matrix initially empty, an element is inserted in it at a random position, with the possibility of repeating the insertion at a filled cell. Then, after a certain number of iterations, all the matrix elements become filled and the process ends. The goal is to calculate a distribution for the number of iterations the process needs before it ends.

Since this process is equivalent to the coupon collector problem, I can easily use its known distribution as a result (in this case the CDF is used):

$P(\text {process ends at iteration }i\text{th})=\frac{n!}{n^i}\mathcal{S}_i^{(n)}$

The problem is that I'm generalizing the process with a $n\times m$ matrix where the outcome depends on the existence of a path of elements between the first and last rows, and I need to find a distribution for the number of iterations necessary to end the process. The information I´m using in higher order matrices is the expected number of elements at a certain iteration: $E(i)=n\cdot m \left(1-\left(1-\frac{1}{n\cdot m}\right)^x\right)$

The number of possible arrangements of $E(i)$ elements in the matrix containing at least one valid path from top to bottom row, which in the basic case of $n\times 1$ matrix is an array of zeroes except for the nth position, with each entry corresponding with the amount of valid arrangements of $k$ elements, when $k$ goes from $0$ to $n$. Formally, we can use the Kronecker delta function to achieve this behavior $\delta _{E(i),n}$. And the total amount of possible arrangements without path restrictions, which in the basic case equals to $\binom{n}{E(i)}$.

My goal with those elements is to find the distribution, which for $m=2$ seems to work correctly. But for $m=1$, the coupon collector problem case, the formula I use doesn't match with the former.

As you can see above, in blue you have the original coupon collector problem distribution (the good one), and in orange the formula I tried. To summarize, my possible distribution is calculated by dividing the arrangements of $E(i)$ elements with at least 1 path by the total arrangements without path restrictions of $E(i)$ elements. That is, in each iteration, the proportion of states in the entire state space that lead to process completion, so formally it would look like this.

$P(\text {process ends at iteration ith})=\frac{\delta _{E(i),n}}{\binom{n}{E(i)}}$

The problem with this expression is that the Kronecker delta never reaches 1, as $E(i)$ only reaches $n$ when the number of iterations approaches infinity. Then, after trying different alternatives, the closest to the good distribution is built replacing delta function by 1, which coincidentally is the only number of valid arrangements with path restriction possible for the $n\times 1$ case:

$P(\text {process ends at iteration ith})=\frac{1}{\binom{n}{E(i)}}$

This is the distribution painted in orange above. It seems like it's missing some simple (or not so simple😔) terms because of the base case nature. So, if anybody has any idea of how can I fix the distribution for this special case starting with the elements I previously described, it would be appreciated.

Answer 1

Even in the general case, if you have a formula $f(n,m,k)$ for the number of arrangements of $k$ elements with a valid top-to-bottom path, the formula $$\Pr[\text{process ends by iteration }i] = \frac{f(n,m,E(i))}{\binom{nm}{E(i)}}$$ is not going to be valid. You cannot use the expected number of elements in a calculation like that.

Instead, let $$p_{ij} = \frac{(nm)!}{(nm)^i (nm-j)!} \left\{\!{i \atop j}\!\right\}$$ be the probability that when we choose $i$ elements, we get $j$ distinct elements. (Here, $\left\{\!{i \atop j}\!\right\}$ is a Stirling number of the second kind.) Then by the law of total probability, $$\Pr[\text{process ends by iteration }i] = \sum_{j=1}^i \frac{f(n,m,j)}{\binom{nm}{j}} p_{ij}.$$ Or, to put it differently: if $\mathbf X_i$ is the random variable giving us the number of distinct elements chosen after $i$ iterations (so that $E(i) = \mathbb E[\mathbf X_i]$) then $$\Pr[\text{process ends by iteration }i] = \mathbb E\left[\frac{f(n,m,\mathbf X_i)}{\binom{nm}{\mathbf X_i}}\right].$$ It would not be correct to take the expected value of this function of $\mathbf X_i$ by applying the function to $\mathbb E[\mathbf X_i]$.

---

In particular, for the special case of the coupon collector problem, since $f(n,1,k) = \delta_{n,k}$, we will get $$\Pr[\text{process ends by iteration }i] = \sum_{j=1}^i \frac{\delta_{n,j}}{\binom{n}{j}} p_{ij} = \frac1{\binom nn} p_{in} = \frac{n!}{n^i}\left\{\!{i \atop n}\!\right\}$$ which matches the usual formula.