Notices
Results 1 to 7 of 7
Like Tree1Likes
  • 1 Post By anticorncob28

Thread: Probability Question

  1. #1 Probability Question 
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    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...


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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?


    Reply With Quote  
     

  4. #3  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    Quote Originally Posted by MagiMaster View Post
    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!
    Reply With Quote  
     

  5. #4  
    Forum Junior anticorncob28's Avatar
    Join Date
    Jun 2013
    Location
    Nebraska, USA
    Posts
    291
    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.
    TridentBlue likes this.
    Reply With Quote  
     

  6. #5  
    Forum Junior anticorncob28's Avatar
    Join Date
    Jun 2013
    Location
    Nebraska, USA
    Posts
    291
    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.
    Reply With Quote  
     

  7. #6  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    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.
    Reply With Quote  
     

  8. #7  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    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!
    Reply With Quote  
     

Similar Threads

  1. A Probability Question
    By mecnun9 in forum Mathematics
    Replies: 6
    Last Post: March 26th, 2013, 04:58 PM
  2. Probability Question
    By ThomasEE in forum Mathematics
    Replies: 4
    Last Post: January 21st, 2013, 04:03 AM
  3. Another probability question
    By leohopkins in forum Mathematics
    Replies: 4
    Last Post: January 19th, 2013, 06:45 AM
  4. Probability Question:
    By ClaimingLight in forum Mathematics
    Replies: 3
    Last Post: October 25th, 2012, 07:35 PM
  5. Probability Question
    By Drewau2005 in forum Mathematics
    Replies: 1
    Last Post: April 5th, 2007, 04:21 AM
Bookmarks
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
  •