home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / stat / 1771 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  2.2 KB
  1. Path: sparky!uunet!idacrd!desj@ccr-p.ida.org
  2. From: desj@ccr-p.ida.org (David desJardins)
  3. Newsgroups: sci.math.stat
  4. Subject: Re: Probability
  5. Message-ID: <1588@idacrd.UUCP>
  6. Date: 29 Aug 92 16:05:30 GMT
  7. References: <1992Aug29.135404.10393@wuecl.wustl.edu>
  8. Sender: desj@idacrd.UUCP
  9. Organization: IDA Center for Communications Research, Princeton
  10. Lines: 48
  11.  
  12. Peter Pui Tak Chiu <ppc1@cec2.wustl.edu> writes:
  13. >Assume there are m kinds of balls in an infinitely large pool (i.e.
  14. >there are infinitely many balls) and the distributions of different
  15. >kinds of balls are equal.  Find the probability of getting all kinds of
  16. >balls if n balls are picked.
  17.  
  18. >Therefore, the probability is:    (n-1)C(m-1)
  19. >                ---------------
  20. >                                 (n+m-1)C(m-1)
  21.  
  22. Nope.  Suppose N = M.  Obviously the chance of getting one ball of each
  23. color is M!/(M^M).  Your formula reduces to M!(M-1)!/(2M-1)!, which is
  24. obviously not the same thing.
  25.  
  26. Your result is wrong because the arrangements are not equally likely.
  27. The chance of getting M red balls is 1/(M^M), but the chance of getting
  28. one ball of each color is M!/(M^M).  You have given each of these the
  29. same weight.
  30.  
  31. Here is a correct approach based on inclusion-exclusion.  Let P(K) be
  32. the probability that all of the balls are selected from a particular set
  33. of K colors, with every color occurring at least once.  Thus P(M) is the
  34. quantity we want.  Let Q(L) be the probability that all of the balls are
  35. selected from a particular set of L colors, but not necessarily with
  36. every color occurring.  Clearly Q(L) = (L/M)^N.
  37.  
  38. Now, of course,
  39.  
  40.    Q(L) = \sum_{K=0}^L B(L,K) P(K),
  41.  
  42. where B(L,K) is the binomial coefficient L-choose-K.  This just says
  43. that if all of the balls are from a set of L colors, then the set of
  44. colors which actually occur must be some K-set contained within the
  45. L-set.  The number of such K-sets is B(L,K), for each K.
  46.  
  47. The inclusion-exclusion formula expresses P in terms of Q:
  48.  
  49.    P(K) = \sum_{L=0}^K (-1)^(K-L) B(K,L) Q(L).
  50.  
  51. It is a direct consequence of the previous formula.  If it's not
  52. familiar to you, you can look it up in any standard combinatorics text,
  53. or just derive it for yourself.  
  54.  
  55. Thus,
  56.  
  57.    P(M) = \sum_{L=0}^M (-1)^(M-L) B(M,L) (L/M)^N.
  58.  
  59.                                         David desJardins
  60.