# Collecting stones in n buckets

There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new empty buckets. Doing this the groups of stones in the differents buckets may merge together.

Now, after $i$ steps we consider the non-empty groups of stones, and I was wondering if there is any information about the (two dimensional) distribution (giving a probability of having at least $\geq b$ buckets with $\geq k$ stones, say), in particular if the problem was studied for big $n$ and big $i$ relative to $n$. Was this model studied before?

The problem arises from simulations of discretized chaotic dynamical systems, where this model (could) provide a comparison model, for long time behaviour and fine discretization.

• "Consequently the stones and up joining and formings groups, that at each step my merge in a smaller number of bigger groups." This sentence has so many typos that I had trouble following. I have an idea what you want to say (add/forming/they), but would you mind correcting it? Also some other things (ofter, ...). – bers Jun 16 '16 at 14:25
• You might have a look at kingman's coalescent. 2 randomly selected buckets are combined at an exponential time rather than the discrete time process you describe. – user83457 Jun 16 '16 at 15:48
• sorry I wrote it in a rush... fixing it now. – Maurizio Monge Jun 16 '16 at 16:44
• @michael: Thanks a lot for the suggestion of the coalecent, it is very similar to the problem I posed. Still, i am curious to know if it is possible to say something about hte 2-dimensional distribution. – Maurizio Monge Jun 16 '16 at 17:42
• When you say "big $i$ relative to $n$", what do you count as big? I'd guess that with high probability all the stones are in one bucket by $i=n\log(n).$ For $n=10000$ with $n\log{n} \gt 92100$ in $50$ random trials achieved 1 bucket in $5653,7502,7991,\cdots,40322, 46880, 47219$ trials with an average of about $18700.$ For $i$ small the distribution of bucket sizes might be interesting. – Aaron Meyerowitz Jun 16 '16 at 23:44

For $a \ne b$ to be sent to different places after $i$ steps, it must be that on each step, their buckets are emptied into different buckets. The probability of that is $\left(\frac{n-1}{n}\right)^i$.
Let the number of pairs of pebbles $a \ne b$ sent to different places after $i$ steps be $P_i$. $E[P_{cn}] ={n \choose 2} \left(\frac{n-1}{n}\right)^{cn} \sim {n \choose 2}e^{-c}$.
If two pebbles are not in the same bucket, then there are at least n-1 pairs of pebbles in different buckets. That means the probability that there are pebbles in different buckets after $cn$ steps is at most $E[P_{cn}]/(n-1) = \frac{n}{2} e^{-c}$. So, by $(1+o(1))n \log n$ steps, the probability that all pebbles are in the same bucket approaches $1$. (The data collected by Aaron Meyerowitz suggests that this might not be sharp.)