| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Simple question:
If all I have is a fair two-sided coin, how can I choose among n
alternatives such that each of the alternatives has a 1-in-n chance
of being selected?
/Dwayne
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 794.1 | SMURF::DIKE | Wed Dec 02 1987 20:07 | 5 | ||
Flip the coin to make a binary number (eg 1 for heads, 0 for tails)
with enough digits to make a number lager than n. If the generated
number is < n, that's it. If not, try again.
Jeff
| |||||
| 794.2 | Not as general as .1, but more elegant | SQM::HALLYB | Khan or bust! | Thu Dec 03 1987 01:15 | 4 |
If the coin is, say, an MS65 $5 Gold Liberty, then you could trade
it in for a very large table of random numbers.
John :-)
| |||||
| 794.3 | CLT::GILBERT | Builder | Thu Dec 03 1987 14:38 | 41 | |
| 794.4 | divide choices in half, flip, discard, repeat til done | VIDEO::OSMAN | type video::user$7:[osman]eric.vt240 | Fri Dec 04 1987 12:03 | 18 |
If I understand you correctly, you want to select just ONE out of n choices, with equal probability, and you want to use just one coin. First, arrange your choices from left to right, and draw a line down the middle. Flip the coin, and heads mean you through away the left choices, and tails means you through away the right half. Then repeat: Divide the remaining choices into a left and right half, flip, through one half away. This method will let you choose amongst thousands of choices in less than 20 flips, although dividing them in half each time might be time-consuming. /Eric | |||||
| 794.5 | 2^i=n ? | BLITZN::ROBERTS | Peace .XOR. Freedom ? | Fri Dec 04 1987 15:10 | 7 |
RE: .4
Eric, I'm interested in both cases. Your method, though, would
seem to work only when n is an integral power of two.
/Dwayne
| |||||