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

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

#11

Post by gizmo686 » Sun, Jun 30, 2019, 1:04 AM UTC

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 construct a uniformly random number between 1 and 10. A simple way (although, again, likely leaving entropy on the table) is to break these bits into groups of 4; interperate them as 4 bit unsigned integers, and discard any result that is not in the range 1-10.

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

#12

Post by peteretep » Sun, Jun 30, 2019, 1:07 AM UTC

RandomBacon wrote: post #5

0-9: Look at the second hand on your watch, what is the last digit? odd/even or heads/tails: is the seconds odd or even?

I bet that has sample bias as there’s a small amount of choice in when they reply

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

#13

Post by moksly » Sun, Jun 30, 2019, 1:08 AM UTC

umvi wrote: post #9

andrewbarba wrote: post #7

Earlier quoted context omitted.

Most people have at least 10 digits memorized? That is one bold claim

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.

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

#14

Post by kevmo314 » Sun, Jun 30, 2019, 1:15 AM UTC

> Ideally we want to preserve as much of the initial distribution (i.e. do as little chopping and changing) as possible.

I was thinking through the post that this sounds like a straightforward problem and it is: https://stackoverflow.com/a/5953133/86433

Except the introduction of an "ideally" optimization condition turns it from a straightforward transform into something requiring a linear programming solver. I wonder if the resultant algorithm is actually any simpler though...

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

#15

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

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)

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

#16

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

umvi wrote: post #8

arkadiyt wrote: post #6

Earlier quoted context omitted.

It's still an unsolved problem whether or not the digits of pi are uniformly distributed.

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?

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

#17

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

I'm from the US and graduated high school in 2014; TI-83s were ubiquitous. I'm not sure if they were the original model or the "plus," though.

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

#18

Post by vzaliva » Sun, Jun 30, 2019, 1:20 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)

I would call this "PHP hacker solution" :)

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

#19

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

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

#20

Post by LeoPanthera » Sun, Jun 30, 2019, 1:21 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)

"But, let’s say you have to do this without access to coins, computers, radioactive material, or other such access to traditional (pseudo) random number generators. All you have is a room of people."

Can you do a SHA1 in your head?