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
    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
    Jun 16, 2016 at 15:48
  • $\begingroup$ sorry I wrote it in a rush... fixing it now. $\endgroup$
    – Maurizio Monge
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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