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

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

#21

Post by corysama » Sun, Jun 30, 2019, 1:22 AM UTC

moksly wrote: post #13

umvi wrote: post #9

Earlier quoted context omitted.

I meant here on Hacker News. I would guess most of us here played with our TI-83s enough to know the first 10

I wonder how many people on HN have even seen a TI-83, I don’t think I’ve seen one since I sold mine when I finished the Danish equivalent of high school in 99. I mean, they were apparently discontinued in 2004, that’s 15 years ago.

In the US TI has established a multi-decade monopoly in schools. Basically, the teachers are only familiar with specifically them, so they require student only use them, so new teachers are only familiar with them.

As a result, a new TI-85 equivalent is only trivially upgraded from what I used 25 years ago and costs exactly as much minus inflation.

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

#22

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

alexandercrohde wrote: post #15

Maybe an easier solution would be to append all the answers, take a hash (e.g. sha1), then convert the last 2 digits from hex to decimal, and mod 10. 1 liner. -- EDIT: I lied, this doesn't work, it biases towards 1-5. I guess you could convert to decimal, and divide by (FFFFFFFFFFFFF / 10)

Would be slightly biased, though (256 is not divisible by 10, you'd have to reject if >=250, say).

EDIT: and don't forget to add 1.

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

#23

Post by [deleted] » Sun, Jun 30, 2019, 1:23 AM UTC

[deleted]

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

#24

Post by alexandercrohde » Sun, Jun 30, 2019, 1:25 AM UTC

vzaliva wrote: post #18

alexandercrohde wrote: post #15

Maybe an easier solution would be to append all the answers, take a hash (e.g. sha1), then convert the last 2 digits from hex to decimal, and mod 10. 1 liner. -- EDIT: I lied, this doesn't work, it biases towards 1-5. I guess you could convert to decimal, and divide by (FFFFFFFFFFFFF / 10)

I would call this "PHP hacker solution" :)

Yeah, there's a few types of "great solutions" in engineering. There are those that run really fast (big O) and those that can be written really fast.

99% of the time the job calls for engineers who can come up with the second type of solution.

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

#25

Post by justinpombrio » Sun, Jun 30, 2019, 1:26 AM UTC

...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.

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

#26

Post by hcs » Sun, Jun 30, 2019, 1:27 AM UTC

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.

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

#27

Post by rbmktechik » Sun, Jun 30, 2019, 1:28 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.

Parents algorithm always works, the one described has a massive failure mode - people slowly learn that they are likely to say 7 and self-censor by picking another number. Or maybe in a different culture the distribution changes (say China and the numbers 4, 8).

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

#28

Post by frankmcsherry » Sun, Jun 30, 2019, 1:37 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.

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

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

#29

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

rbmktechik wrote: post #27

FabHK wrote: post #19

Earlier quoted context omitted.

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.

Parents algorithm always works, the one described has a massive failure mode - people slowly learn that they are likely to say 7 and self-censor by picking another number. Or maybe in a different culture the distribution changes (say China and the numbers 4, 8).

Excellent point. The algorithm in the article is predicated on a specific distribution and iid, GP algorithm is predicated only on iid.

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

#30

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

frankmcsherry wrote: post #28

FabHK wrote: post #19

Earlier quoted context omitted.

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.

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, 27 or more" numbers. Probability that you have to reject any resulting hex digit is obviously 3/8.