A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

Question

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:

Randomly assign (with replacement) $N$ balls to $M$ urns. Afterwards, for any urn with more than one ball assigned to it, extract one at random.

The total number of matches (urn-ball pairs) will be $M(1-(1-\frac{1}{M})^N)$ in expectation. To see this, fix an urn. The probability of this urn being matched is the probability that at least one ball arrives. Since the probability that no ball arrives is $(\frac{M-1}{M})^n$, we get the expected number of matches above. From a given ball's perspective, the probability of being matched is $\frac{M}{N}(1-(1-\frac{1}{M})^N)$.

We care what happens when there is a measure $N$ of balls and a measure $M$ of urns, so we take the limit of these expressions as $\theta=\frac{M}{N}\rightarrow \infty$ and get the matching function $\mathcal{M}(M,N)=M(1-e^{-\frac{M}{N}})$ and the ball's matching probability $\frac{\mathcal{M}(M,N)}{N}:=p(\theta)=\theta(1-e^{-\frac{1}{\theta}})$.

We generalize this in the following way: introducing heterogeneity in the sizes (weights) of the balls, which leaves static the assignment probability for a given urn but changes the probability of extraction--now, instead of randomly extracting a ball from an urn, we extract each ball with probability equal to its relative weight within the urn.

To fix ideas, let $n_i$ be the number of balls of size $U_i$ in the "population" of balls, and let $N$ be the number of types of ball ($M$ is still the number of urns).

With a small bit of effort it's not hard to see that the probability of a given ball of size $U_i$ being extracted is given by:

$P_i (\textbf{n},\textbf{U};M,N) =\sum \limits_{k_1 = \delta_{i,1}} ^{n_1}\cdots\sum \limits_{k_N=\delta_{i,N}} ^{n_N}\prod \limits_{j=1}^N \dbinom{n_j-\delta_{i,j}}{k_j-\delta_{i,j}}\frac{M(M-1)^{\sum \limits_{j=1}^N (n_j-k_j)}}{M^{\sum \limits_{j=1}^{N} n_j}}\frac{U_i}{\sum \limits_{j=1}^N k_j U_j}$

Where $\delta_{i,j}$ is Dirichlet: 1 if $i=j$, 0 otherwise, $i \in \{1,\ldots,N\}$.

To see why, note that any possible arrangement in a given urn is fully characterized by the total number of each type of ball present. Thus this expression sums over the possible total numbers of each ball in a given urn--these are the indices $k_j$, which range over $\{0,\ldots,n_j\}$ except when $j=i$, because we know there is at least one ball of type $i$.

The term $\prod \limits_{j=1}^N \dbinom{n_j-\delta_{i,j}}{k_j-\delta_{i,j}}M(M-1)^{\sum \limits_{j=1}^N (n_j-k_j)}$ multiplies by the number of urns $M$ the number of ways to choose $k_j$ balls from the $n_j$ of each type (and $k_i-1$ from $n_i-1$ other type $i$ balls) multiplied by the number of ways to distribute the remaining $n_j-k_j$ balls to the other $M-1$ urns. The denominator $M^{\sum \limits_{j=1}^{N} n_j}$ is the total number of possible assignments of the balls to the urns.

Lastly the term $\frac{U_i}{\sum \limits_{j=1}^N k_j U_j}$ gives the probability of $U_i$ being taken from the urn with $k_j$ of each type of ball.

My problem concerns finding something tractable here (as above) for what happens in the limit when we have a measure $M$ of urns and a measure $\eta = \sum \limits_{j=1}^N n_j$ of balls, sending $N\rightarrow \infty$ keeping $\frac{M}{\eta}$ fixed. In the limit there will be a density function associated with each ball size $f_U$ which gives the relative presence of balls of size $U$ for all $U$ in its support. So that denominator should become an integral like $\intop f_U(u) du$

Also note that: $\sum \limits_{k_1 = \delta_{i,1}} ^{n_1}\cdots\sum \limits_{k_N=\delta_{i,N}} ^{n_N}\prod \limits_{j=1}^N \dbinom{n_j-\delta_{i,j}}{k_j-\delta_{i,j}}\frac{M(M-1)^{\sum \limits_{j=1}^N (n_j-k_j)}}{M^{\sum \limits_{j=1}^{N} n_j}}=1$ (which can be seen via repeated application of the binomial theorem quite quickly once you see how the $N=1$ case works).

Any ideas on how to proceed would be awesome!! I'm not facile enough with the binomial coefficients to simplify this expression to the point where I could take a limit.

Answer 1

The following solves my problem, but not the question stated above, exactly.

I managed to sort of sidestep the intractable sum above by changing the rules of the generalization a little bit.

Fix the assignment of the balls to the urns. However, instead of pulling out balls from overmatched urns with probability proportional to their weight within the urn, we ONLY select from the LARGEST type of ball. So if there are balls of size 1, 3 and 5 in an urn, the size 1 and 3 balls are never chosen and a size-5 ball is always chosen. WITHIN the largest type, we select at random--if there are 10 size-5 balls, each is chosen with probability 1/10, regardless of the frequencies of the size 1 and 3 balls.

Note that this generalization also simplifies to the simple case when all balls are of equal size.

However, we are able to get a simple expression under this new rule, basically because we set a bunch of the terms above to 0.

Specifically, we find that:

$\begin{eqnarray*} \hat{P}_{i}(\textbf{n},\textbf{U};M,N) & = & \sum\limits _{k_{1}=0}^{n_{1}}\cdots\sum\limits _{k_{i-1}=0}^{n_{i=1}}\sum_{k_{i}=1}^{n_{i}}\prod\limits _{j=1}^{i-1}\dbinom{n_{j}}{k_{j}}\dbinom{n_{i}-1}{k_{i}-1}\frac{M(M-1)^{\sum\limits _{j=1}^{i}(n_{j}-k_{j})+\sum\limits_{j>i}n_{j}}}{M^{\sum\limits _{j=1}^{N}n_{j}}}\frac{1}{k_{i}}\\ & = & \frac{M\left(M-1\right)^{\sum\limits_{j>i}n_{j}}}{M^{\sum\limits_{j=1}^{N}n_{j}}}\sum_{k_{1}=0}^{n_{1}}\dbinom{n_{1}}{k_{1}}\left(M-1\right)^{n_{1}-k_{1}}\cdots\sum_{k_{i}=1}^{n_{i}}\dbinom{n_{i}-1}{k_{i}-1}\frac{1}{k_{i}}\left(M-1\right)^{n_{i}-k_{i}}\\ & = & \frac{M\left(M-1\right)^{\sum\limits _{j>i}n_{j}}}{M^{\sum\limits _{j=1}^{N}n_{j}}}\sum_{k_{1}=0}^{n_{1}}\dbinom{n_{1}}{k_{1}}\left(M-1\right)^{n_{1}-k_{1}}\cdots\sum_{k_{i-1}=0}^{n_{i-1}}\dbinom{n_{i-1}}{k_{i-1}}\frac{1}{n_{i}}\left(M-1\right)^{n_{i-1}-k_{i-1}}\left(M^{n_{i}}-\left(M-1\right)^{n_{i}}\right)\\ & = & \frac{M\left(M-1\right)^{\sum\limits_{j>i}n_{j}}M^{\sum_{j=1}^{i-1}n_{j}}\left(M^{n_{i}}-\left(M-1\right)^{n_{i}}\right)}{n_{i}M^{\sum\limits_{j=1}^{N}n_{j}}}\\ & = & \boxed{\left(1-\frac{1}{M}\right)^{\sum\limits _{j>i}n_{j}}\left(1-\left(1-\frac{1}{M}\right)^{n_{i}}\right)\frac{M}{n_{i}}} \end{eqnarray*}$

(The second line is simple rearrangement of terms; the third relies on the observations that $\dbinom{n_{i}-1}{k_{i}-1}\frac{1}{k_{i}}=\dbinom{n_{i}}{k_{i}}\frac{1}{n_{i}}$ and the Binomial Theorem which implies that $\sum\limits_{k_{1}=1}^{n_{1}}\dbinom{n_{i}}{k_{i}}\left(M-1\right)^{n_{i}-k_{i}}=M^{n_{i}}-\left(M-1\right)^{n_{i}}$--which, by the way, is the number of ways to end up with at least one size $i$ ball in a given urn; the fourth line again uses the Binomial theorem repeatedly (and more directly); and the fifth line is rearrangement/simplification)

Note that this can be seen as

$\hat{P}_{i}(\textbf{n},\textbf{U};M,N)=M\cdot ABC$

Where $A=\left(1-\frac{1}{M}\right)^{\sum\limits _{j>i}n_{j}}$ is the probability that all larger balls end up in other urns, $B=\left(1-\left(1-\frac{1}{M}\right)^{n_{i}}\right)$ is the probability of getting at least one size $U_{i}$ ball, and $C=\frac{1}{n_{i}}$ is the probability of a given ball being selected conditional on at least one size-$U_{i}$ ball being in the urn (which can be seen by the binomial expansion used above).

If we fix $\frac{n_{i}}{M}=\frac{1}{\theta_{i}}$ and send $M\rightarrow\infty$, we get a somewhat familiar expression:

$p=\frac{1}{\theta_{i}}e^{-\sum\limits_{j>i}\frac{1}{\theta_{j}}}\left(1-e^{-\frac{1}{\theta_{i}}}\right)$

I'm still not quite clear how to extend this to a continuum of types ($N \rightarrow \infty$).

Also, if this exposition helps anyone gain some traction on the original expression, let me know.