home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2611 < prev    next >
Encoding:
Internet Message Format  |  1992-09-15  |  1.1 KB
  1. Xref: sparky comp.programming:2611 comp.theory:1924
  2. Newsgroups: comp.programming,comp.theory
  3. Path: sparky!uunet!s5!sethb
  4. From: sethb@fid.morgan.com (Seth Breidbart)
  5. Subject: Re: Proving fair shuffles (was: FULL HOUSE)
  6. Message-ID: <1992Sep15.160009.6091@fid.morgan.com>
  7. Organization: Morgan Stanley & Co., New York, NY
  8. References: <schnitzi.716563018@eola.cs.ucf.edu>
  9. Date: Tue, 15 Sep 1992 16:00:09 GMT
  10. Lines: 19
  11.  
  12. In article <schnitzi.716563018@eola.cs.ucf.edu> schnitzi@cs.ucf.edu
  13. (Mark Schnitzius) writes:
  14. >I've been wondering...
  15. >
  16. >Assuming you have a true random number generator, is there
  17. >a way to _prove_ that a particular algorithm performs an
  18. >honest shuuffle (i.e. each card has equal possibility of 
  19. >being in each place)?  Are there any order(n) shuffling
  20. >routines?
  21.  
  22. An honest shuffle gives each permutation an equal probability, not
  23. just each card/position pair.  For instance, a fair _cut_ gives each
  24. card a 1/52 chance of being in each position.
  25.  
  26. There are shuffles, some O(n), that can easily be proven to be fair.
  27. In general, it is not possible to tell whether a function computes a
  28. fair shuffle.
  29.  
  30. Seth        sethb@fid.morgan.com
  31.