How to pick a random number from 1-10 • Hacker News Board

Re: How to pick a random number from 1-10

#31

Post by jancsika » Sun, Jun 30, 2019, 1:45 AM UTC

FabHK wrote: post #19

gizmo686 wrote: post #11

There is a simpler solution if you do not mind leaving entropy on the table. Break the people up into groups of two without regard for their selection. If two people provide the same number, ignore them. Otherwise, output "0" if the first person's number is smaller then the second, and output "1" if the first person's number is larger. From this, you have a sequence of uniformly random bits, from which you can constr…

That works and is perfectly uniform (if the people are i.i.d.), but requires quizzing around 20, 40, 60 or more people for a number before you can deliver one, while the algorithm described only requires one or two. EDIT: Not quite that many, more like around 9, 18, 27 or so, see below.

I'm not sure I understand.

Humans aren't like weighted dice. For example, it's certainly conceivable that a few pairs of these humans misunderstand the goal such that they have a 0% chance of ever choosing numbers that change the respective ordering. Add to that the higher probability that many of these pairs of humans will just toggle their orders each round.

Edit: clarification-- the humans don't even have to misunderstand the rule, just the upshot of the process.

Re: How to pick a random number from 1-10

#32

Post by vntok » Sun, Jun 30, 2019, 1:46 AM UTC

hcs wrote: post #16

umvi wrote: post #8

Earlier quoted context omitted.

Just try it out for yourself. Analyze the distribution of the first billion digits and I think you'll find they will produce a more uniform distribution than this algorithm in the article given 1 billion human responses...

Even taking for granted that the digits are evenly distributed, which digit do you pick?

The next one in the sequence, anytime you need a new number?

Re: How to pick a random number from 1-10

#33

Post by frankmcsherry » Sun, Jun 30, 2019, 1:53 AM UTC

FabHK wrote: post #30

frankmcsherry wrote: post #28

Earlier quoted context omitted.

Nonsense. It requires roughly 1+log(10) bits in expectation and has a geometric tail.

Eh? 4 bits minimum to get a uniform 1-16, and each bit requires requires 2 numbers that are not identical. (Ah yeah, I thought that in turn requires a bit more than 4 numbers, but it requires only a bit more than 2 numbers (probability that numbers coincide is not 1/2, as with bits, but 1/10, or a bit more than that due to non-uniformity)). Thus, I recant "around 20, 40, 60 or more" and replace it by "around 9, 18, 2…

Rejection sampling isn't the best way to go.

With b bits you are subdividing the (0,1) interval into 2^b regions, and only need more bits if one of the 9 multiples of 0.1 land in the interval you've picked. As b increases this probability drops exponentially.

It's a fair point that the number of "numbers" depends on how low the entropy of the source is, but in the link the probability of collision wasn't massive.

Re: How to pick a random number from 1-10

#34

Post by AlphaWeaver » Sun, Jun 30, 2019, 1:53 AM UTC

A few years ago I was stumped by a similar question about generating uniformly random numbers with less than ideal constraints. The helpful minds at MathOverflow solved it [0] but it wasn't something that you could guarantee would always work. (The question explains in more detail... Due to the miniscule probability of a never ending sequence of less than ideal random integers.)

I'm curious whether this technique could be applied to my original problem!

[0]: https://math.stackexchange.com/q/1273214/196899

Re: How to pick a random number from 1-10

#35

Post by yarg » Sun, Jun 30, 2019, 1:53 AM UTC

You could use the biased distribution to build a lookup table for a less biased distribution.

Build a 10^n lookup table with an entry for each of the possible (ordered) n-tuples of values, give each entry a weight of the product of the probabilities of each of the n values making the entry.

Create a set of probabilities for each output and initialise to zero, run through each of the generated tuples in descending order of weight, set the lookup value to the output with the current lowest probability (or the first, or feed in another PRNG - but you have to stop somewhere) and increase the probability according to the weight associated with the tuple.

At the end of this process you'll have a PRNG that's at least as good as the input (and generally better) - although you'll need to query the seed PRNG n times per result. The higher the value of n the better the output (Although the lookup table will become quite large).

Re: How to pick a random number from 1-10

#36

Post by yarg » Sun, Jun 30, 2019, 1:58 AM UTC

yarg wrote: post #35

You could use the biased distribution to build a lookup table for a less biased distribution. Build a 10^n lookup table with an entry for each of the possible (ordered) n-tuples of values, give each entry a weight of the product of the probabilities of each of the n values making the entry. Create a set of probabilities for each output and initialise to zero, run through each of the generated tuples in descending ord…

This solution gives no consideration to security only the distribution of outputs.

Re: How to pick a random number from 1-10

#37

Post by FabHK » Sun, Jun 30, 2019, 1:59 AM UTC

frankmcsherry wrote: post #33

FabHK wrote: post #30

Earlier quoted context omitted.

Eh? 4 bits minimum to get a uniform 1-16, and each bit requires requires 2 numbers that are not identical. (Ah yeah, I thought that in turn requires a bit more than 4 numbers, but it requires only a bit more than 2 numbers (probability that numbers coincide is not 1/2, as with bits, but 1/10, or a bit more than that due to non-uniformity)). Thus, I recant "around 20, 40, 60 or more" and replace it by "around 9, 18, 2…

Rejection sampling isn't the best way to go. With b bits you are subdividing the (0,1) interval into 2^b regions, and only need more bits if one of the 9 multiples of 0.1 land in the interval you've picked. As b increases this probability drops exponentially. It's a fair point that the number of "numbers" depends on how low the entropy of the source is, but in the link the probability of collision wasn't massive.

But the original post described rejection sampling (once you got your bits from the larger/smaller trick).

Re: How to pick a random number from 1-10

#38

Post by leggomylibro » Sun, Jun 30, 2019, 2:01 AM UTC

hcs wrote: post #26

gizmo686 wrote: post #11

There is a simpler solution if you do not mind leaving entropy on the table. Break the people up into groups of two without regard for their selection. If two people provide the same number, ignore them. Otherwise, output "0" if the first person's number is smaller then the second, and output "1" if the first person's number is larger. From this, you have a sequence of uniformly random bits, from which you can constr…

That's pretty good, as long as each person can't hear any of the previous numbers! The article has the same issue, and might even be biased by the second person knowing they're the second person.

Maybe have them write their numbers down and put them in a hat? Or hey, this is 2019, have them connect to a website or bluetooth beacon and enter a number on their phone?

Ooh, or I bet you could make a 10-digit keypad that wirelessly reports to a nearby Raspberry Pi for $2-5 in parts, sort of like those 'clickers' that universities use to quiz large lecture classes.

It's too bad that most cheap radio modules are so short-range, because it would be interesting to make something like that and nail them to telephone poles with notes asking people to press a button. You'd have to control for people doing things like hammering the same button repeatedly for a laugh, but it would be fun to see what happened.

Would you be allowed to use HAM bands in the US for that sort of thing if you made them like beacons which sent a callsign after the number value and device ID?

Re: How to pick a random number from 1-10

#39

Post by sansnomme » Sun, Jun 30, 2019, 2:11 AM UTC

leggomylibro wrote: post #38

hcs wrote: post #26

Earlier quoted context omitted.

That's pretty good, as long as each person can't hear any of the previous numbers! The article has the same issue, and might even be biased by the second person knowing they're the second person.

Maybe have them write their numbers down and put them in a hat? Or hey, this is 2019, have them connect to a website or bluetooth beacon and enter a number on their phone? Ooh, or I bet you could make a 10-digit keypad that wirelessly reports to a nearby Raspberry Pi for $2-5 in parts, sort of like those 'clickers' that universities use to quiz large lecture classes. It's too bad that most cheap radio modules are so…

Just use the unlicensed ISM bands.

Re: How to pick a random number from 1-10

#40

Post by moultano » Sun, Jun 30, 2019, 2:11 AM UTC

justinpombrio wrote: post #25

...or just add up the answers mod 10. This has the property that if even a single person answers uniformly at random, then the final number you compute will be uniformly random, regardless of how everyone else answers.

I'd love to see something written up about how quickly this converges, assuming the variables are i.i.d and distributed according to the distribution in the article.