Let’s say I have 5 bins with various numbers of balloons in them. one has 2 balloons, another 3, then 4, another 5, and the last one has 6 (20 in all). Each balloon has an equal probability of randomly popping. Which bin is most likely to run out of balloons first? Is it definitely the one with the least number of balloons to start with?
Given any number of bins and balloons, is there a simple formularic way to determine which bin will empty first?
I’m pretty sure that the bin with the fewest balloons will empty first. To see this, think about viewing the events in reverse chronological order. At each time step, you would see a balloon pop into existence in one of the five bins. The probability that a balloon will pop into existence in the first bin is 2/20; in the second bin, 3/20; in the third bin, 4/20; and so on. Looking at it this way, it seems pretty obvious that the last bin to have no balloons in it when watching the events backwards is the smallest bin; and this bin will, of course, be the bin that empties out first when you think of the events in their original order.
This logic should work for any number of balloons & bins; however, actually calculating the probability that the smallest bin empties first, as compared to some other bin, is a little more complicated. I’ll mull it over and see if I come up with anything further.
The bin with the smallest number of balloons to start with is most likely to run out first.
To prove this to yourself, consider one bin with 3 balloons and another with 6. If three balloons in the second bin popped first, it would now be a bin with 3 balloons, and the two would be equally likely to be emptied first. (But probably one of the balloons in the first bin would have popped by then. )
Though the chance of any balloon popping is equal for any of the balloons, the more balloons in a bin, the greater the chance that the popping balloon will be in that bin. The final criteria requires that a bin whith one balloon pop to finish the sequence. I’ve thought it through to this point, but it hasn’t all fallen in place for me yet.
How about this question? If we were to graph the balloon POPulation (he!) of each bin over time, would the graphs tend to converge, such that the higher population bins would lose more balloons more rapidly?
The probability of any one balloon popping starts at .05 or 1/20 the second balloon then is 0.0526 or 1/19 continiues on 1/18, 1/17, 1/16…etc.
The first time no bin can be empty. The second time only 1 bin can be empty. The third time 2 bins, the 4th time 3 bins, the fifth time 4 bins, the sixth time 5 bins. By the fifth time all bins can fulfil the criteria.
One bin has to be empty by the 16th balloon popping, so 2 to 16 balloon poppings will fullfil the criteria.
My thoughts so far. I don’t garantee a solution, but we’ll see.
If you only consider 2 bins (A & B), one with 2 and one with 3, there are 5! ways for the balloons to pop. Since the balloons are indistinguishable, there are really only (5!)/(3!2!) = 10 ways.
It’s easy to see that in 6 of these 10 ways (list them), the A bin empties first.
Now, going up from them gets much more confusing. Even with bins of 2, 3, 4, (A, B & C) there are myriad ways that the A bin empties first, but you can’t just count the cases where the sequence ends BC or CB (you’d exclude the cases that end CBB or BCC, e.g.). And you can’t just exclude the cases where the sequence finishes with an ‘A’ (since a sequence finishing CAB is also a failure). However, the principle is the same.
I was trying to figure a general rule, but couldn’t spend the time.
Still, the ‘A’ bin is definitely most likely to empty first.
That reasoning doesn’t work because you ignore the probability of the condition that you wave away, even though you seem to acknowledge this problem parenthetically.
When starting, every balloon has a 1/20 chance of popping. The first bin has a 2/20 chance of being hit on the first pop, the second bin 3/20, and so on to 5/20. So the chance of a balloon popping in a bin is directly proportional to the number of balloons in the bin at the time. That seems obvious now that I’ve written it down, but it argues against the idea that the bin that starts with the fewest balloons is most likely to empty first. That is, the bin with 2 balloons only has to have two balloons pop to empty, but the bin with 6 balloons is 3 times more likely to have the first balloon to pop.
My *guess * is that it is equally likely for any bin to be emptied first.
Looking at running a simulation of this, will be back.
But even if it were certain that another bin would catch up with the 2-bin, that would still only make it equally likey to win the “race”. In fact, it’s less than certain, therefore the 2-bin is most likely to win.
Is there a simple formula… not that I know of. But it is a problem that can be solved fairly easily with a dynamic programming. I’ll see if I can work out the formulae needed and plug them into excel. Give me a bit of time…
An Excel-based VBA simulation is posted in a ZIP file at www.seigle.net/misc/balloons.zip (1.4M zipped, it has 21 columns x 65,500 rows, expands to 10M; should be available within a few minutes) gave these results consistently:
Bin Emptied First
1 27,136 41%
2 16,297 25%
3 10,170 16%
4 6,976 11%
5 4,921 8%
Total Trials 65,500 100%
If you download the file you can press the Run button to re-run the simulation.
I still don’t know how to figure this out theoretically based on probability theory.
Okay, I put together a spreadsheet that determines the probability of a number of popped balloons for a given total number of popped balloons to have been in a particular bin. Unfortunately, the only way I can figure out how to calculate this is recursively. Let’s say there’s been n pops, and i is the number of pops in a particular bin, and s is the original size of the bin, then
IOW, the probability that we have i pops given there’s been n total pops is the probability that we had i-1 pops in this bin with n-1 total pops times the probability that the current pop was in this bin plus the probability of having had i pops with n-1 total pops times the probability of not having the current pop in this bin.
Anyway, what you’ll see on the chart is the the probability for a bin having it’s size in pops is always higher for smaller bins.
…I’ll see if I can figure out how to post this in a way that you can access it and see the formulae I used…
You could model this as a Markov chain, where the non-absorbing states correspond to configurations with no empty bins, and the absorbing states are configurations with exactly one empty bin. There’s a transition from state m to state n if n has exactly one less balloon than m, and all transitions out of state m are equally likely. Then it’s a bit of matrix algebra and some sums to see what the probability that each bin empties first is.
There’s another possible avenue of attack that may be worth exploring. The graph of the Markov chain I described previously can be interpreted as a lattice, and there’s a form of induction that will apply. In brief, if every minimal element has a property P, and an element has P if every lesser element has P, then every element has P. In this case, the property P is that a bin with fewer balloons has a higher probability of being empty first than a bin with more balloons (to deal with the case where two or more bins have the same number of balloons).