First let me state the problem.
If you randomly and uniformly divide k units of water into n buckets what is the probability that none of the buckets has more than $\frac{k}{2}$units of water? (Note that as water is continuous, you can divide it into any real proportion)
It's kind of like bins-and-balls but unlike balls which are discrete, water is continuous.
The problem is although I am familier with probability, I haven't encountered a similar problem before.
Is it even solvable using just probability or should I try reducing it to some other problem?
Thanks in advance!

Edit: By 'randomly' and 'uniformly' I mean each possible n-tuple $a_1 , a_2 , ... , a_n$ s.t. $a_1 + a_2 + ... + a_n = k$ is equally probable, where $a_1, a_2, ... , a_n$ are nonnegative real numbers.

  • $\begingroup$ Much of advanced probability theory involves integration. If you want to make use of what you already know, how about dividing the $k$ units of water into $p$ parts, each with $\dfrac{k}{p}$ units of water in it. Then, determine the probability that no bucket receives more than $\dfrac{p}{2}$ of these parts. Take the limit as $p \to \infty$. This will work similar to how Riemann integration works. It is not trivial to prove that it works this way for probability theory, but it should be possible with cylinder sets (I think). Anyway, ignoring the proof for now, that might be a decent approach. $\endgroup$ – InterstellarProbe Jul 10 '18 at 18:58

Comment: Perhaps this is easier to visualize if you have a rope that is $k$ units long. Then you cut it at $n-1$ "randomly chosen" points to make $n$ pieces of rope. The key to getting an answer is to say exactly what you mean by "randomly chosen" points. One method would be to choose a 'continuous' uniform distribution.

If $n = 2$ it is essentially impossible that the one cut would be exactly in the center. So one of the two pieces of rope has to be longer than $k/2.$

If $n = 3,$ the problem is more interesting. To avoid getting into the math for now, I will simulate the locations of the two cuts using the continuous uniform distribution. Here is how one iteration of the simulation would go: For simplicity, I will let $k = 1.$ If the cuts come at points $U_1$ and $U_2,$ let $X_1$ be the smaller so that $X_1 = min(U_1, U_2).$ And let $X_2$ be the larger. Then the three pieces have lengths $X_1 - 0,\, X_2 - X_1,$ and $1 - X_2.$ Then we can check whether the longest of the three pieces of rope has length $G$ greater than $1/2.$

Here is how one iteration of the process looks in R statistical software:

u = runif(2); u
## 0.23527570 0.09365067             # positions of 2 cuts
## 0.09365067 0.23527570             # put smallest 1st
diff(c(0, sort(u), 1))
## 0.09365067 0.14162502 0.76472430  # lengths of 3 pieces, last > 1/2

By doing a huge number of iterations, we can get a good approximation to $P(G > 1/2).$ Below is a simulation using a million iterations. In 749,858 of the million pieces of rope 1 meter long, randomly cut into three pieces, the longest piece was longer than 500cm. Each run of a million will give a slightly different answer; another run had 750,011. So it seems $P(G > 1/2) \approx 3/4.$ [The $95\%$ margin of simulation error for the probability is $\pm 0.00087.$]

g = replicate( 10^6, max(diff(c(0,sort(runif(2)),1))) )
mean(g > .5)
## 0.749858

Of course, as the number of cuts get larger, the chances that one of the pieces is longer than $k/2$ decreases. For five cuts (six pieces) I got a probability of about $0.19,$ maybe $3/16.$

A rigorous mathematical solution to this version of your problem (with random cutting according to the continuous uniform distribution) is possible. If observations are sorted from smallest to largest, they are called 'order statistics'. It is possible to write probability density functions for differences between neighboring order statistics and that would be one way to derive an exact solution. (Someone on this site has already done something like that).

Note: Back to your original problem with a volume of water: You could imagine the water in a transparent cylindrical tank full to $k$ units in height. Then use the uniform numbers to put marks along the side of the tank to show how much water to put into each of the $n$ buckets.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks @BruceET, that really helped. It's a nice empirical explanation, but I was more interested in a rigorous mathematical solution for which your link helped! $\endgroup$ – Fenil Jul 11 '18 at 3:57
  • $\begingroup$ @Fenil. I was pretty sure I'd seen this on the site before, so I tried to search for it instead of repeating the proof. Trick was to remember 'stick', not 'rope'. $\endgroup$ – BruceET Jul 11 '18 at 4:59

Not a full answer, but an important question. Too long to put into comments.

Well, you first need to be clearer (excuse the pun) on the precise probability model here. Does the probability of one molocule of water ending up in Bucket $i$ independent of where another molocule of water ends up? Maybe like n containers collecting mist.

Or are there instead $n-1$ numbers $a_1,\ldots, a_{n-1}$ each $a_i$ drawn according to the uniform distribution on $[0,k]$, where bucket $i$ gets $a_i-a_{i-1}$ units of water (and bucket $n$ gets $k-a_n$ units of water and bucket 1 gets $a_1$ units of water).

The former is $\lim_{k \rightarrow \infty} \mathbb{P}[$ $\frac{k}{2}$ out of $k$ balls land in any one bin$]$, which is 0 (for $n \geq 3$).

The latter can be easily calculated too.

| cite | improve this answer | |
  • 1
    $\begingroup$ You are correct @InterstellarProbe. I should have written "...for $n \geq 3$. $\endgroup$ – Mike Jul 10 '18 at 20:26
  • $\begingroup$ You are right @Mike, I have tried to make it more clear. $\endgroup$ – Fenil Jul 11 '18 at 4:10

As others have stated, the problem here is being rigorous about what you mean with "randomly and uniformly" assigning the water in a continuous, rather than discrete setting. A natural way to interpret it is to think of the continuous case as the limit of the discrete case for the number of discrete elements going to infinity. In your case, if I have $k$ units of water, and $1$ "unit" is $m$ molecules assigned uniformly and independently at random to $n$ buckets, what is the probability that none of the $n$ buckets gets more than $k/2$ units, i.e. $mk/2$ molecules?

The answer in this case is almost trivial: the probability is $0$ if $n\leq 2$, and $1$ if $n\geq 3$. That's because, as the number of trials $m$ goes to $\infty$, the deviation from the average grows as something like $\sqrt{m}$, and the probability of seeing a divergence that grows infinitely larger, or infinitely smaller, than $\sqrt{m}$ is $0$. So, with $1$ bucket, you obviously have everything there, so more than $k/2$. With $2$, on average you have exactly $k/2$, but you really can expect to see a "little imbalance". This imbalance goes to $0$ in relative terms (how many units), but to $\infty$ in absolute terms (how many molecules). With $n\geq 3$, the probability of seeing more than $k/n+\epsilon$ units per bucket goes to $0$ for any $\epsilon>0$.

This highlights the problem with using independent "continuous" trials: the law of large numbers flattens everything to the average (or more precisely, it makes the probability of more than an arbitrarily small relative deviation from the average $0$, but also the probability of getting exactly the average $0$).

| cite | improve this answer | |
  • $\begingroup$ You are correct @Anonymous. I have tried to be more specific about what I meant by 'uniformly' and 'randomly'. $\endgroup$ – Fenil Jul 11 '18 at 4:14
  • $\begingroup$ @Fenil it's still tricky :) What people do when they talk about these things is ask for measurability: non-trivial with sets of real numbers :) But the essence of the problem is another: if you assume continuity, and you assume that every "infinitesimal" behaves independently, by the law of large numbers you will have almost the perfect average. With "almost" I mean: choose an arbitrarily small but positive $\epsilon$ - then you will end up in an interval within $1\pm\epsilon$ of the average with probability $1$ (though you will end up at exact average with probability $0$). $\endgroup$ – Anonymous Jul 11 '18 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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