4 ms·
Ah, I think I've figured it out (nothing to do with JS's RNG, sadly). It's simpler when you ignore Jeremy (sorry). For this case, we can assume `Math.random()
by RKoutnik 10y ago
Ah, I think I've figured it out (nothing to do with JS's RNG, sadly). It's simpler when you ignore Jeremy (sorry). For this case, we can assume `Math.random()` will output uniformly random numbers. `Array.prototype.sort` works as so:
If the function returns > 0, the first param should be sorted to a higher index than the second.
If the function returns < 0, the first param should be sorted to a lower index than the second.
If the function returns exactly zero, the parameters are left as they are.
So what we've got is a 1/3 of Erin 'winning', 1/3 of Thomas 'winning' and a 1/3 chance of a tie which leaves Erin ahead. So she's got a 2/3 chance of being first.
Additionally (but not in any consequential fashion), generating a random number between 1 and 100 (inclusive) gives you 100 possibilities (duh). With three outcomes:
100 / 3 = 33.333333333333336
The first option has slightly more chance to be picked. If Erin wanted to be fair(er), she'd multiply by 99.
Here's a Python solution showing it's not just JS:
link: http://paste.ubuntu.com/23222240/ http://paste.ubuntu.com/23222240/
results:
{
'Erin Ptacek': 6523,
'Thomas Ptacek': 1951,
'Jeremy Rauch': 1526
}
(with apologies to
ShaneWilton, I've completely rewritten this comment so the following comments are out of date)
- ShaneWilton 10y agoThe output of Math.random also doesn't seem to be very uniform. With the original code, I'm consistently seeing Erin appear first 60% of the time, and Thomas first 30% of the time. Jeremy is left with 10%. Even after changing the code to multiply by 99 instead of 100, the results don't change very much at all.
- RKoutnik 10y agoInteresting, running just the number generation under node v6.5.0 gives: { '0': 340364, '1': 330093, '-1': 329543 } So we see a slight bias for zero (elements are equal) there. ~Lemme try it in Chrome and get back to you.~ AHA, repro'd in Chrome latest: http://jsbin.com/cefuqi/edit?js,console http://jsbin.com/cefuqi/edit?js,console Also repros in node. Fascinating. There goes my afternoon...
- ShaneWilton 10y agoHa, I was starting to think I was crazy.
- thethirdone 10y agoThe problem is in the sort function. It expects the comparison to be deterministic and thus does not give the fully randomized list. Instead giving each name a distinct value (between 0 and 1) and sort based on those values.
- RKoutnik 10y agoPosting this to trigger HNReplies - See my first comment response to you for the full story.
- teraflop 10y agoThis implicitly assumes that Array.sort is stable: that is, if the comparison function returns 0 then sorting leaves the array elements in their original relative positions. That's not guaranteed by the JavaScript specification, see e.g. https://bugs.chromium.org/p/v8/issues/detail?id=90 https://bugs.chromium.org/p/v8/issues/detail?id=90 It just so happens that in V8, the built-in sort uses an unstable quicksort for large arrays but a stable insertion sort for small ones, so the rest of your analysis is correct.