home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9586 < prev    next >
Encoding:
Internet Message Format  |  1992-07-27  |  3.3 KB
  1. Path: sparky!uunet!usc!sdd.hp.com!uakari.primate.wisc.edu!ames!agate!dog.ee.lbl.gov!network.ucsd.edu!news.acns.nwu.edu!uicvm.uic.edu!u53644
  2. From: U53644@uicvm.uic.edu
  3. Newsgroups: sci.math
  4. Subject: Re: ? Quick algorithm for random covering sets ?
  5. Message-ID: <92210.014509U53644@uicvm.uic.edu>
  6. Date: 28 Jul 92 06:45:09 GMT
  7. References: <SQUASH.92Jul17215435@bourbaki.msri.org>
  8. Organization: University of Illinois at Chicago
  9. Lines: 47
  10.  
  11. I'm not quite sure of what the original poster is looking for in terms of a
  12. probability distribution on the power set of $1,...,N, but one approach that
  13. comes to mind is the following.......
  14.  
  15.         1. Choose some probability p in the interval (0,1)
  16.         2. Randomly select some number between 1 and N (the tentative number
  17.                of sets chosen). Call it K.
  18.         3. For each number from 1 to K, set up an array (1 x N), and randomly
  19.                fill it with 0's and 1's (latter with probability p).
  20.                   (1 signifies inclusion, 0 exclusion)
  21.         4. To find the intersection of our sets : multiply the arrays
  22.                componentwise. (We now have the array for the intersection).
  23.         5. Take this new array, and subtract each of its' components from 1
  24.                to get the array for the complement of the intersection.
  25.         6. Now, multiply this array (the one for the complement of the
  26.                intersection) by the one for the K-th set to exclude the
  27.                intersection from the K-th set.
  28.         7. Now, take the 'complements' of the arrays for sets 1 through K :
  29.                again, subtract each component of an array from 1 to get the
  30.                corresponding element of the 'complementary array'.
  31.         8. Once again, multiply the 'complementary arrays' together
  32.                componentwise to form the array for the intersection of the
  33.                complements of the sets. We now have an array corresponding to
  34.                the set of all elements of $1,...,N not in any of the K sets.
  35.         9. Add this array componentwise to the one for the K-th set.
  36.  
  37. Then, just use the usual algorithms to pick out which places in our arrays are
  38. filled with 1's (if the n-th element of the m-th array is 1, print n. If not,
  39. let n be replaced by n+1 and repeat. If n>N, replace m by m+1 and n by 1. If
  40. m>K, stop, if not go to first direction in parantheses).
  41.  
  42. No promises are offered as to the uniformity of the resulting sampling
  43. procedure. One might even things out a bit by setting the weights (when one
  44. selects K) for the various values of K proportional to the number of possible
  45. distinct collections of K sets satisfying the conditions. Having done so, one
  46. might also preselect the numbers of elements for sets 1 through K-1, setting
  47. weights in an analagous fashion (randomly setting entries to 1 or 0 until one
  48. either uses up one's allotment of 1's or 0's for a given array, then filling
  49. in the rest of the array with whatever is left (1's if 1 needs more 1's : i.e.
  50. one has already excluded as many elements from the set as one can and still
  51. have the desired number of elements. 0's if one has already included as many
  52. elements as desired). One then fills in set K as before.
  53.  
  54. So I guess that it depends on what one wants, and how much effort is
  55. acceptable.
  56.  
  57.                                              Joseph B. Dunphy
  58.