1. If n items are randomly distributed to b boxes, what's the probability that no box will have more than m items?

For example, if 40 items are randomly distributed in to 10 boxes, what's the probability that no box will end up with 8 or more items?

I am having a tough time figuring this out for some reason, but it can't be as complex as I'm making it. Thanks for ideas...  2.

3. I think (without having actually tried it) this becomes a much simpler question if you turn it around. What's the probability that a box will end up with m or more items?  4. Originally Posted by MagiMaster I think (without having actually tried it) this becomes a much simpler question if you turn it around. What's the probability that a box will end up with m or more items?
Hey, thanks for your response. I can figure it out the odds for a given box vs. the rest of the boxes. The Binomial Distribution gives the probability of exactly k successes for in n succeed/fail trials. I plug in probability of success = 1/10 (for ten boxes) and failure = 9/10, and ask it the probability that one box gets k items and the rest get (n-k), and it tells me. There's a also a cumulative binomial distribution that tells me the probability that one chosen box gets k or less items in it, and that answers the question for a single box.

But it doesn't work for multiple boxes. My original thought was, calculate the odds a given box gets m or less items, and multiply that by the number of boxes, for instance if the odds are .9 that a given box gets less than the max amount using the above, then the odds of that all 10 boxes having less should be (.9)^10. But that doesn't work. To see why, consider the case where 11 items are distributed to 10 boxes, and I want know the odds that every box will have 1 or less items. There's a substantial (non zero) chance that any given box will have 0 or 1 items, but a non zero number raised to the power of 10 is still non zero. This makes no sense, as there is a 0% chance of 11 items fitting into 10 boxes without at least one box having 2 or more items in it. So the probability should have been zero.

Anyway, thanks for listening. I'm beginning to think this problem is as big and complicated as it first looked!  5. Hey, I think I have a solution. It's not really "complicated", but it does take a lot of work.
Let's use your specific example. If you can answer these two questions, you can automatically figure out the answer.
1) How many ways are there to add ten whole numbers (order matters) to get 40?
2) How many of these ways use only numbers less than eight?
These questions can be answered using something similar to proof by induction. The number of ways to add x numbers to t, using whole numbers equal to or less than w, will be expressed as x.t.w. The formulas are:
(x.t.w) = (x-1).t.w + (x-1).(t-1).w + (x-1).(t-2).w + (x-1).(t-3).w ... (x-1).(t-w).w
(1.t.w) = 1 (if t <= w) and 0 if otherwise.
Explanation: the number of ways to add only one number to get to a specific number is one. This is obvious and is the explanation for the second formula. Then the first formula is a bit more complex. There are (x-1).t.w ways to add (x-1) numbers to t, and you can just add zero to that, so all those ways count (with the (x-1).t.w way at the front). How many ways are there to add x numbers to get t using only integers less than w? First, take all the ways to add (x - 1) numbers to (t - 1). You can just take each of these ways, and add one at the end to get to t. This is the (x-1).(t-1).w. Then you can take all the ways to add (x - 1) numbers to (t - 2), and add two to each of those, and that's an extra (x-1).(t-2).w ways. And you continue until you get to (x - 1) numbers that sum to (t - w), and add w to that. This is all the solutions.
This can be figured out using a chart. Let's say how many ways are there to add five numbers to ten, using only numbers equal to or less than six. The chart starts like this:
0 1 2 3 4 5 6 7 8 9 10

1 1 1 1 1 1 1 0 0 0 0
1 2 3 4 5 6 7 6 5 4 3
1 3 6 10 15 21 28 33 36 37 36
So the first row is how many ways there are of adding only one natural number to a specific number with numbers equal to or less than six. Obvious. Then the second row is just adding up the numbers above. Take the "5" under the eight for instance. It comes from adding the terms above: 0 + 0 + 1 + 1 + 1 + 1 + 1. You start at the number directly above, and then add on six to the left, because you can only add up to six.
.
If somebody finds an error here or a shortcut, please notify me. I've considered problems like this before and this was my best solution to date.  6. Oops, my numbers in my bottom row got thrown off because this website wouldn't allow you to use multiple spaces. Oh well, you should still be able to figure it out.  7. Thanks for your input anticorncob. Its late for me and I won't get a chance to work through your ideas until tomorrow, but its a really fresh way of approaching it, for what I was doing. I appreciate it, and will post back when I get it all applied.  8. I should post back on this thread, because I said I would. Yeah, those lists of numbers you gave, Pascals Triangle, if you turned it into a table:

Code:
```1  1  1  1  ...
1  2  3  4  ...
1  3  6  10 ...
1  4  10 20 ...
.. ..   ...  ....```
the diagonals going from bottom-left to to right are the outputs of the binomial function (often said out loud as "n choose k"), so to get the entry from the rth row and cth column, its something like:

Code:
`binomial(r+c, c)`
The denominator in the probability will always be an entry in that table, so you can find it that way. The challenge is the numerator in that probability. In Python, here's a recursive function that enumerates all the ways to put a total of t items in b boxes:

Code:
```def enumerate(t, b):
"""enumerates a list of lists, each list being a different way to arrange t items into b boxes"""
if t==0: return [[0 for i in range(b)]] #base case 1: 0 items into b boxes
elif b==1: return [[t]] #base case 2: t items into 1 box
else: #must go deeper
out = []
for i in range(t+1): # for each item i from 0-t
#stick i on the front of each possibility returned from enumerate(t-i, b-1)
out += [[i] + j for j in enumerate(t-i, b-1)]
return out```
So you can tweak that to get it running pretty fast for counting rows with an entry > or < than k, but if there is a simple elegant and fast mathematical solution, I have yet to find it. But I'm still poking around, learning things. I'm also still sure there's something simple I'm missing. If I find the breakthrough, I'll post it here though!   Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement