Hacker News Reader

>Easily solved by taking the last digit modulo the number of children, but I guess that might be difficult while driving.

Well it's not fair. Take 4 children for example. random 0 to 9 mod 4 does not have an even distribution over 0-4.

It's also more difficult to explain to children.

> random 0 to 9 mod 4 does not have an even distribution over 0-4.

That's true, but only because 4 never appears in the result. The possible results for modulo 4 are 0 - 3.

The first child is numbered zero. Shall I explain it in more detail?

     n  n % 4
    -----------  	
     0  0
     1  1
     2  2
     3  3
     4  0
     5  1
     6  2
     7  3
     8  0
     9  1
    10  2
    11  3
    12  0
    13  1
    14  2
    15  3

> It's also more difficult to explain to children.

And rewarding, unless you want your children to grow up innumerate.

if the stopwatch uses base 10, the last digit will be in the range [0, 9], making n >=10 irrelevant. in this range, 0 and 1 appear 3 times; 2 and 3 appear 2 times.

if the stopwatch uses hex, then 0-3 will appear equally often in this case

The second digits on my digital watches extend to 59, and if a precocious youngster were to correctly object that a limit of 59 produces a bias, I would extend the range by multiplying the minute digit by 60 and adding it to the seconds (thus reducing the bias). We are, after all, most likely using a calculator to produce the result.

> if the stopwatch uses hex ...

I think we're safely in the red herring zone now. :)

EDIT: Yes, of course -- when confronted by a correct and reasoned reply, downvote it to discourage any such mistakes in the future.

i think you're confused on what a 'last digit' is. the seconds digits (plural) contain two digits, which range from 0-59; the last digit (singular) ranges from 0-9

> i think you're confused on what a 'last digit' is.

Digits, not digit, please, and do try to limit the anti-intellectualism and adversarial posture.

The last digit on the clock can only be 0 through 9. If you truncate your chart accordingly, 0 and 1 are represented more than 2 and 3. Or do you mean “the entire seconds value” (for which this idea would work with four children) instead of “the last digit”?

To avoid confusion, I used the expression "last digits".

It actually doesn't matter how many options are in your random number generator. You only get a normal distribution if the number of children you have divides the number of options in your generator. Even if you're using the seconds of a clock, it doesn't work for 7 children.

> It actually doesn't matter how many options are in your random number generator.

It certainly does -- the larger the random number, the fairer the outcome is.

> Even if you're using the seconds of a clock, it doesn't work for 7 children.

For a digits range of 0 - 59? Plus the fallback in the face of a precocious child of adding the number of minutes * 60?

Using modulo would actually bias the results making things slightly less random.

Not so. If the last digit on the clock is random, then the result is also.

     n  n % 4
    ----------- 	
     0  0
     1  1
     2  2
     3  3
     4  0
     5  1
     6  2
     7  3
     8  0
     9  1
    10  2
    11  3
    12  0
    13  1
    14  2
    15  3

EDIT: It must be really, really satisfying to be able to anonymously downvote posts that actually reveal such things as grade-school arithmetic -- thus contributing to the intellectual wasteland that most accurately represents America in the early 21st century.

you're getting upset because you're making a terminology error, you say "digit" but mean "digits". A digit is either a finger, or the numbers 0-9, singular.

I'm getting outraged by the number of brainless cyberlawyers who think downvoting a post constitutes a creative act, on a par with knowing something about the topic of discussion.

The pattern is clear and ubiquitous -- if you actually know something, and if you're foolish enough to post a clear exposition, the morons who never post anything coherent will downvote your posts with a probability approaching certainty.

The modulo operator is the obvious solution to the original question. And if there were't an atmosphere of pervasive anti-intellectualism at HN, this thread would be much shorted than it is.

Well, you are incorrect. The simple use of modulo does result in a bias. See for instance, modulo 7:

From this, you can clearly see that:

    0 appears nine times.
    1 appears nine times.
    2 appears nine times.
    3 appears nine times.
    4 appears *eight* times.
    5 appears *eight* times.
    6 appears *eight* times.

This is not fair, and is an actual problem in real life: Two examples off the top of my head is when drawing cards in electronic poker games (where slight biases in the PRNG can be exploited by those who notice them) and in cryptography.

> Well, you are incorrect. The simple use of modulo does result in a bias.

You're arguing against something I never said. Large numbers reduce the bias, they don't eliminate it. Notice that earlier I considered the objection of a hypothetical clever child by using the minute digits as well. All these steps only minimize the bias in favor of small numbers, that cannot be eliminated. Even a 64-bit random number possesses this property. And the classic remedy for this bias is to apply the modulo operator to get the desired range.

And the classic remedy for eliminating bias is to redraw/reshuffle if the number is outside of the desired range. Note, this completely eliminates all bias. The negative aspect is that in this case, random number generation can take arbitrarily long (with rapidly diminishing probabilities); to make it more efficient, you could first use a modulo operation, but only using a base that divides the original range (e.g. for 7 kids and 60 seconds, do 60 mod 10, then redraw if the result is 7, 8 or 9).

You've failed to acknowledge the trade-offs of using your solution versus the OP's solution (or the solution above), and you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.

> versus the OP's solution (or the solution above)

Would that solution be "multiply by the number of children and divide by ten"? Let's see:

     n  n * 7 / 10
    ---------------
     0  0
     1  0
     2  1
     3  2
     4  2
     5  3
     6  4
     7  4
     8  5
     9  6

Not a very desirable distribution. But then, the OP could have established this fact before posting.

> ... you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.

No, I am being downvoted because I'm right. Being right is simply rude, but being right about something trivially proven is beyond the pale.

>Would that solution be "multiply by the number of children and divide by ten"

No; his/her solution is: If 0-9 couldn't be divided evenly among the kids present, leftover digits would result in a re-roll, exactly as I said above.

> No, I am being downvoted because I'm right

Are you? This is math we're talking about, right and wrong are very precisely defined. For the sake of discussion, can you repeat the question you claim to have the right/correct solution to, and your answer?

> to make it more efficient, you could first use a modulo operation, but only using a base that divides the original range (e.g. for 7 kids and 60 seconds, do 60 mod 10, then redraw if the result is 7, 8 or 9).

This makes it less efficient - in this case, 18/60 chance of having to redraw, versus 4/60. Taking the modulus of the largest range you can leaves less residue (what lutusp is alluding to, without realizing others are describing a simple way of getting an exact uniform distribution).

If you want to make it more efficient (in terms of entropy used), you need to save the 1-of-prime (eg bits, trits, etc) that have been successfully chosen (uniformly). For example, with 6 children and an 8 sided die (3 bits), a roll of 6 or 7 would narrow the choices to only children 0-2 or 3-5 respectively. Your subsequent rolls could then be done with a 4 sided die.

You're right, I don't know what I was thinking... Anyways, about your second paragraph, doesn't that only work if the number of desired outcomes (children) is non-prime?

Even worse - non-coprime with the entropy source. That's why I had to change the example to 6 children.

That's only fair if you have 2, 5, or 10 kids.

What? Have you thought this through?

     n  n % 4
    -----------  	
     0  0
     1  1
     2  2
     3  3
     4  0
     5  1
     6  2
     7  3
     8  0
     9  1
    10  2
    11  3
    12  0
    13  1
    14  2
    15  3

"Last digit" only goes to 9, so you end up with 0 & 1 more represented than 2 & 3

"Digits", not digit.

Only N first digits are accepted, whereby N is a number of children. Otherwise you re-draw.

Another way to say it is that if a glance at the last clock digit turns out to be equal to to less than the number of children, it's accepted as the result, otherwise the operator looks away for a suitable interval and tries again.

In other words, digit(s) modulo children.

> " tries again.... In other words, digit(s) modulo"

"Try again" and "modulo" do not mean the same thing.

Try again means you discard a result outside of the range, and then generate a new number without any reference to the value of the first try. If you have 7 kids and you're picking 0-9, you discard any results of 7-8-9 (or 8-9-0) and try again.

Modulo means you take a result outside of the range, divide it by the range, and use the remainder (which is guaranteed to be in the range) as your new answer. The problem with this approach is that it's not evenly distributed -- if you have 7 kids and digits 0-9, three of your kids will get double chances. Even if you use 0-59 as your range, some of the kids will have 9 chances and others will have 8 chances.

You don't want to modulo. You want to multiply the last digit by the number of children and divide by ten.

> You don't want to modulo.

You haven't thought your reply through:

> You want to multiply the last digit by the number of children and divide by ten.

That doesn't produce the result you think it does. Think a bit harder. If the last digit is 20, and there are four children, the result is 4 * 20 / 10 = 8. There is no eighth child.

Yeah, I was joking. The point is that either way you get a non-uniform distribution for n children unless n divides 10. I think the part you are misunderstanding in your responses is that the last digit of a clock has only ten options: 0 through 9. In the tables you have posted, children 0 and 1 each win 30% of the time, while children 2 and 3 each win only 20% of the time.

With a single generation, you can't uniformly choose from a set of n options with a random number generator that outputs m options, unless n divides m.

> I think the part you are misunderstanding in your responses is that the last digit of a clock ...

Digits, not digit. I doubt this fact will limit the number of airheads who downvote posts containing useful content.

Your last comment said

> If the last digit is 20, and there are four children, the result is 4 * 20 / 10 = 8.

Singular "digit."

Do you actually think the point is to argue with people who actually know things, like a lawyer instead of a scientist? Using a modulo operator is the obvious solution to the original question, and cowardly anonymous downvotes can't erase simple facts -- but they eventually make them have so little contrast on the display that they become unreadable. What an achievement.

Nearly everytime you mention downvotes: the reason is tone and attitude. I don't know if you are aware just how much your tone influences the downvotes.

> Nearly everytime you mention downvotes: the reason is tone and attitude.

Look -- I posted the obvious solution to a common problem. Everything else depends on those who can't stand the unwelcome intrusion of simple, easily stated facts.

My "attitude" is that this problem is easily solved, using simple arithmetic. Imagine you're a scientist -- as such, do you object to a useful result because of its source?

I say this to help you, feel free to ignore it.

When you get a downvote, ignore it. It's probably accidental or meaningless and these tend to self correct over a day.

When people downvote a bunch of your posts in a thread IGNORE THE DOWNVOTES. Vindictive downvote sprees are usually corrected over the course of the day. Mentioning the downvotes will usually prevent those corrective upvotes. Me tioning the downvotes in the unpleasant way that you do will attract downvotes.

You may wish to consider how you're presenting the information. If the first table of numbers gets downvotes posting the same table again without more information is going to get the same downvotes.

You could argue that it should not be this way, but it is.

> You could argue that it should not be this way, but it is.

Indeed it is. State facts, back up what you say with evidence, get downvoted. As certain as sunrise.

> If the first table of numbers gets downvotes posting the same table again without more information is going to get the same downvotes.

The alternative is to adopt the standards of religion instead of science. In religion, if you start losing followers, you change the mythology. In science, evidence is evidence, and how people feel about it has no standing.

> When you get a downvote, ignore it. It's probably accidental or meaningless ...

Easily proven false. My downvotes inevitably accompany anything I post that has evidence and/or links to references. If I offer an uncorroborated opinion or philosophical remark, however irrelevant or baseless, it's treated neutrally. This is how science works -- you observe things dispassionately and don't let yourself to be swayed by what people think is true.

Well, judging from your usual quality of comments (you're one of the users I remember for good contributions in science threads) I think there's an disagreement here that is not stated explicitly.

Do you disagree with any of the following statements, and if yes, where and why?

- original stopwatch solutions gives equal probability for any of the kid to get picked

- your modulo solution does not give equal probability for any of the kid to get picked

- you argue that the non-uniformness of your solution is not relevant in practice, because number of kids is likely to be an order of magnitude smaller than the readout from the stopwatch (i.e. last two digits)

> Do you disagree with any of the following statements, and if yes, where and why?

Okay. I usually expect people to locate the errors in their own thinking, but in this case, I'll make an exception. Here's one of the suggestions: "multiply the last digit by the number of children and divide by ten". Let's see how this works out:

     n  n * 7 / 10
     ----------------
     0  0
     1  0
     2  1
     3  2
     4  2
     5  3
     6  4
     7  4
     8  5
     9  6

The OP could have tested his suggestion before posting. I certainly would have.

I'm going to avoid your straw men, with this exception:

> you argue that the non-uniformness of your solution is not relevant in practice

I never said that. I said that the error could be minimized. But consider my test of the the alternative listed above. The error inherent with a relatively small number of children and a relatively large original number, say, 0 - 59, is a smaller error than the proposed alternative.

> I'm going to avoid your straw men

Hey, I asked you three simple questions with pretty much boolean answers, in order to try and clarify where exactly you end up disagreeing with everyone. Please be charitable.

> Here's one of the suggestions: "multiply the last digit by the number of children and divide by ten".

Hey, that one was clearly meant as a joke, and is not the suggestion I was referring to. If something is a strawman here, this is. The one I asked about is the "My parents used the last digit on a stopwatch to decide which of the kids got to pick the radio station in the car and similarly trivial decisions. (If 0-9 couldn't be divided evenly among the kids present, leftover digits would result in a re-roll.)".

In light of that, could you provide the answers?

I've been waiting for his answer impatiently. He's been active on other threads but completely ignored your post. Says a lot.

Well, what can one do :(.

Anyway, I must say I found the technique I used above quite effective at figuring out continous disagreements. You state some simple true/false statements describing your assumptions and ask the other party to agree/disagree and explain the points of disagreement. Apply recursively if needed. Kind of a discussion equivalent of git bisect ;).

> "I posted the obvious solution to a common problem"

You posted a solution that was less correct than the solution you were responding to.

The solution I originally posted is fair and practical. Divide the digits as evenly as you can between the kids, and treat any extras as a do-over. While it's technically possible to never end, in practical terms it produces a fair result within ten seconds. (The fact that you're trying to "fix" this solution confuses me; I wonder if perhaps you didn't understand it in the first place and have been arguing based on a misunderstanding ever since.) By contrast, your solution does not produce a fair result for certain numbers of kids. I promise, the kids in my family would have discovered that bias by the time there were 7 of us.

> "can't stand the unwelcome intrusion of simple, easily stated facts"

One of the reasons you've gotten a lot of downvotes here is because of the combination of:

- posting an incorrect solution

- insisting the incorrect solution is correct, in spite of several people showing you why it is not, and

- complaining that people who are downvoting are the ones in the wrong, including several insults (calling people airheads, innumerate, brainless cyberwarriors, saying they can't stand simple facts, etc.)

At times I really enjoy your comments. I've sent a lot of upvotes your way over the years. But in this case you're wrong, and you've taken to insulting the people who are patiently trying to explain to you why you're wrong. I know you're capable of better. Please take the time to reread and understand the original solution, and stop insulting people.

I would say it's a combination of a factually incorrect comment and the arrogant tone in which it is presented.

> You don't want to modulo. You want to multiply the last digit by the number of children and divide by ten.

Let's see how this turns out:

     n  n * 7 / 10
    --------------
     0  0
     1  0
     2  1
     3  2
     4  2
     5  3
     6  4
     7  4
     8  5
     9  6

It's the same for most other numbers of children. Thanks for playing, no cigar.

Why are you posting examples in base 16? 4 divides 16 evenly, but I bet most people operate in base 10.

Say I have 7 children and I get a number 0-9. If the result is 8, how does doing 8 mod 7 help me at all?

> Why are you posting examples in base 16?

I invite you to locate where I posted an example in base 16.

> Say I have 7 children and I get a number 0-9. If the result is 8, how does doing 8 mod 7 help me at all?

Use both digital watch digits that tally seconds, as in my example.

Can you admit you were wrong yet? Unless the number of kids evenly divides 60, then some kids will have better odds than others. Just some small admission that the odds don't work out perfectly unless N is 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, or 60.

Edit: For instance, if there are 59 kids, the first one has twice as good a chance to win as any of the others, because both 0 % 59 and 59 % 59 are 0. In other words, in the set derived from x % 59, for x in {0, 1, ..., 59}, 0 appears twice, and each other number in the range 0-59 only appears once.

> Can you admit you were wrong yet?

I never made the claim you're objecting to. The modulo operator minimizes the bias, it doesn't eliminate it. And it's the most efficient way to solve the problem.

My suggestion is that you stop thinking like a lawyer and start thinking like a scientist.

But the solution you objected to is perfectly fair. How is yours more scientific?

This is a known problem with C's (and other functions in languages based off C's) "rand" function.

http://stackoverflow.com/questions/10984974/why-do-people-sa...

> "Easily solved"

It's already solved. If there are 3 kids, 1-3 go to kid A, 4-6 to kid B, 7-9 to kid C, and 0 means try again. There's no bias present in this solution. Since it only takes a fraction of a second to generate a new digit with a stopwatch (using the hundredths of seconds digit) it's no big deal if you have to try five times.

Your solution introduces unnecessary arithmetic (what's 47 mod 3?) and unnecessary psychological pressure (will the kids start an argument while you're figuring it out? Will the ones who are better at math start taunting the others?) and it introduces bias in a family as large as ours got (7 or 8 kids can't evenly divide 60; 3, 6, or 7 kids can't evenly divide 100.)

A re-roll is simply a superior solution.

[Appeal to authority: my dad had a math degree and was valedictorian of his engineering college. I have bachelors and masters degrees in applied math. My oldest brother competed at the national level in Mathcounts. We all agree this is the best practical solution for this problem. Based on the votes, so does the bulk of the technically-minded Hacker News community.]