Tricky Multivariate Urn Model Problem

[crbazevedo]

Hi all,

I'm working towards my Msc dissertation and I've ran into a tricky problem which I've figured it out to be modeled as the following urn problem: there are m balls and m urns U_1, ..., U_m with capacities C(U_1) = m, C(U_2) = m-1, ..., C(U_m) = 1. Knowing that each urn U_i is only allowed to store balls iff urn U_(i-1) has at least 1 ball, what is the joint probability mass function of (N_1 ... N_m) if m balls are assigned to the urns at random, where N_i is the number of balls in urn U_i?

I've tried a few different approaches to solve this problem but none of them turned out to be successful. Specifically, I've worked out a few basic cases, but I couldn't find a general formula. Any hint, suggestion or advice will be very much appreciated.

 

[bpet]

May be possible (or at least to derive other properties of the distribution). But first, exactly what happens when the (m+1)th ball is added?

 

[crbazevedo]

Hi @bpet, thanks for the reply.

Actually, the total capacity of all urns is simply the sum of their individual capacities, i.e., C(U_1, ..., U_m) = Sum_i=1^m C(U_i) = m + (m-1) + ... + 1 = m*(m + 1)/2. Thus, adding the (m+1)th ball would not be an issue. I'm generally interested in the specific case of m urns and m balls, though. The most tricky part is the constraint over adjacent urns, I believe. Suppose that only the first a > 1 urns turned out to be used in a random trial. Then, the input vector has the form (N_1 ... N_a N_(a+1) ... N_m), with N_1, ..., N_a > 0 and N_(a+1), ..., N_m = 0.

In the end of the day, this distribution would be useful for finding the probability that an arbitrary ball will belong to a given urn U_i.

I'm looking forward to hearing any suggestion you may have.
Thanks,
Carlos.

 

[bpet]

The m balls aren't placed one at a time then?

 

[crbazevedo]

@bpet Yes, they are. So, what happens is that if one urn turns out to be full just after adding the j-th ball (j < m), that urn is simply removed and all the (j+1), ..., m-th balls need to be allocated to urns with available slots. But I'm not sure whether the order of placement will afect the general formula or not, since all orders are equally likely. It's indeed very interesting to analyze this model by considering the placement order.

Carlos

 

[bpet]

Ok. If the placement order of the particular ball is unknown then the probability that urn i contains it is E[N_i / m]. It might be possible to get a neat recurrence relation by conditioning N(m+1)_i on N(m)_i.