4
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ "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, ...). $\endgroup$
    – bers
    Commented Jun 16, 2016 at 14:25
  • 3
    $\begingroup$ 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. $\endgroup$
    – user83457
    Commented Jun 16, 2016 at 15:48
  • $\begingroup$ sorry I wrote it in a rush... fixing it now. $\endgroup$
    – Maurizio Monge
    Commented Jun 16, 2016 at 16:44
  • $\begingroup$ @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. $\endgroup$
    – Maurizio Monge
    Commented Jun 16, 2016 at 17:42
  • 2
    $\begingroup$ 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. $\endgroup$
    – Aaron Meyerowitz
    Commented Jun 16, 2016 at 23:44

1 Answer 1

Reset to default
1
$\begingroup$

See A balls-and-colours problem and Another colored balls puzzle although those don't talk about the two-dimensional distribution. These suggest looking at the count of pairs of pebbles in different buckets.

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.)

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.