1
$\begingroup$

Suppose there are $n$ elements with value 1 initially.

In each iteration, two elements will be randomly selected and merged together. The values are added up and the total element size shrinks by 1. For example, after the 1st iteration, there are $(n-2)$ 1s and 1 element with value 2.

My question is how to estimate/approximate the distribution of the $(n-i)$ values after the $i$-th iterations. Here $n$ is at least 100k. From my intuitive, I think it would be like a normal distribution. Could anyone help me?

Thanks!

$\endgroup$
1
  • $\begingroup$ I recommend writing some code to simulate this. You could start by plotting the results for $i=n/2$. $\endgroup$
    – almagest
    Jan 16, 2020 at 18:42

1 Answer 1

Reset to default
2
$\begingroup$

Not an answer but too messy for a comment.

This will certainly not be Normal. Suppose you go from $n$ to $n/2$, which requires $n/2$ rounds. Consider a particular element. It has prob $\frac2n$ of being picked in the first round, prob ${2 \over n-1}$ of being picked in the second round, etc. So the prob $p$ that it was never picked during all those $n/2$ rounds is:

$$ \begin{array}{} p &=& (1 - \frac2n)(1 - {2 \over n-1}) \cdots (1 - {2 \over n/2 + 1}) \\ &=&{n-2 \over n}{n-3 \over n-1}{n-4 \over n-2} \cdots {n/2 - 1 \over n/2 +1}\\ &=&{(n/2)(n/2 -1) \over n(n - 1)}\\ &\approx& \frac14 \end{array} $$

So you can expect about $\frac14$ of all numbers to still be $1$, which agrees with some simulations I've run.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .