137396 2014-10-03 12:19:32 -0700 Bias in first few random numbers generated by WeakRandom 2016-06-16 01:22:02 -0700 1 1 1 Unclassified WebKit JavaScriptCore 528+ (Nightly build) Mac (Intel) Unspecified NEW P2 Normal --- 1 ajith webkit-unassigned ap bastien ggaren oldest_to_newest 1039289 0 ajith 2014-10-03 12:19:32 -0700 The first few random numbers generated after WeakRandom is initialized show a bias. While this is may not be an issue for a web-page calling Math.random many more times (the random stream has good uniformity properties), it is a problem in the following scenario. Consider a web-app that runs experiments and shows different content dynamically based on 2 successive random numbers returned by Math.random. The first number decides if that page load is eligible for the experiment or not; if eligible, the second number decides on showing one of two content variations with 50-50 probability. The attached file 'RandomBucketingBias.cpp' simulates these bucketing trials 100,000 times, initializing WeakRandom at each iteration to simulate a distributed scenario where many different end-users load the page independently. Compile 'RandomBucketingBias': g++ -o RandomBucketingBias RandomBucketingBias.cpp Running 'RandomBucketingBias': ./RandomBucketingBias shows something like: Running bucketing tests: Of 100000 tests, 50004 ignored, 49996 not ignored Bucket counts 31235 18761, ratio = 1.664890 PASS: Ignores trials as expected FAIL: First bucket count as expected FAIL: Second bucket count as expected One can skip the first k random numbers after initializing WeakRandom. Interestingly, skipping 3 numbers seems to get rid of the bias. RandomBucketingBias takes 2 arguments. The first is the ignore percentage, an integer between 0 and 100 to specify what percentage of the trials must proceed to the second bucketing stage. The second is the number of random numbers to skip before running the experiment. So, ./RandomBucketingBias 50 3 shows: Running bucketing tests: Of 100000 tests, 50020 ignored, 49980 not ignored Bucket counts 24841 25139, ratio = 0.988146 PASS: Ignores trials as expected PASS: First bucket count as expected PASS: Second bucket count as expected I also tested this against the Chromium RNG code; it shows no bias. For the full test see: https://gist.github.com/ajithopti/bdd3cb21c89e203f569a 1039291 1 239219 ajith 2014-10-03 12:20:46 -0700 Created attachment 239219 C++ code to reproduce bug. 1041965 2 ajith 2014-10-15 14:20:38 -0700 Any progress on this? There's a blog post in the works about this, so in the ideal case, am hoping for a fix before that is published. 1042271 3 ggaren 2014-10-16 19:18:19 -0700 Looks like initializeSeed can correct for bias by using a different constant. Can your experiment work around this limitation by explicitly skipping the first few random numbers? 1042846 4 ajith 2014-10-20 09:56:39 -0700 We currently have a fix that avoids the bucketing issues. If a different constant does indeed fixes this issue, it'd be great to have this fix in. Thanks for checking this. 1047098 5 ajith 2014-11-07 09:43:00 -0800 Geoffrey, Just checking. Will you or someone else be applying a fix for this? 1202165 6 bastien 2016-06-14 06:46:45 -0700 It seems that we have this particular issue with our a/b test algorithm. We have this kind of repartition between test versions on safari: Version 0: 800 Version 1: 11 000 Version 2: 35 000 Version 3: 24 000 We observe this behavior with all safari versions with significant traffic: 9.x, 8.0, 7.0, 6.1.6 However, Safari 4.0 does not seem to have this issue. We have reproduced this behavior on all safari versions available on saucelabs with this piece of code : https://gist.github.com/bcaudan/bfab026fa2416af9fc48dfacc4a59938 Do you have any news on this issue? 1202227 7 ggaren 2016-06-14 10:50:00 -0700 Have you tested Safari Technology Preview? 1202544 8 bastien 2016-06-15 05:54:07 -0700 No. Is it supposed to be fixed? 1202657 9 ggaren 2016-06-15 12:36:59 -0700 Yes. 1202891 10 bastien 2016-06-16 01:22:02 -0700 Great, then! Thx. 239219 2014-10-03 12:20:46 -0700 2014-10-03 12:20:46 -0700 C++ code to reproduce bug. RandomBucketingBias.cpp text/plain 2639 ajith Ly8gVGVzdHMgU2FmYXJpIGFuZCBDaHJvbWl1bSdzIFBSTkcgZm9yIGV4cGVyaW1lbnQgYnVja2V0 aW5nIGJpYXMuCgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUg PGNzdGRsaWI+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8 Y21hdGg+CgojZGVmaW5lIE15UmFuZG9tKCkgKGFyYzRyYW5kb20oKSAlICgodW5zaWduZWQpUkFO RF9NQVggKyAxKSkKCi8vIFdlYmtpdChTYWZhcmkpJ3MgUk5HLgpjbGFzcyBXZWFrUmFuZG9tIHsK ICBwdWJsaWM6CiAgICBXZWFrUmFuZG9tKHVuc2lnbmVkIHNlZWQpCiAgICB7CiAgICAgIGluaXRp YWxpemVTZWVkKHNlZWQpOwogICAgfQoKICAgIGRvdWJsZSBnZXQoKQogICAgewogICAgICByZXR1 cm4gYWR2YW5jZSgpIC8gKFVJTlRfTUFYICsgMS4wKTsKICAgIH0KCiAgICB1bnNpZ25lZCBnZXRV aW50MzIoKQogICAgewogICAgICAgIHJldHVybiBhZHZhbmNlKCk7CiAgICB9CgogIHByaXZhdGU6 CiAgICB1bnNpZ25lZCBhZHZhbmNlKCkKICAgIHsKICAgICAgbV9oaWdoID0gKG1faGlnaCA8PCAx NikgKyAobV9oaWdoID4+IDE2KTsKICAgICAgbV9oaWdoICs9IG1fbG93OwogICAgICBtX2xvdyAr PSBtX2hpZ2g7CiAgICAgIHJldHVybiBtX2hpZ2g7CiAgICB9CgogICAgdm9pZCBpbml0aWFsaXpl U2VlZCh1bnNpZ25lZCBzZWVkKQogICAgewogICAgICBtX2xvdyA9IHNlZWQgXiAweDQ5NjE2RTQy OwogICAgICBtX2hpZ2ggPSBzZWVkOwogICAgfQoKICAgIHVuc2lnbmVkIG1fbG93OwogICAgdW5z aWduZWQgbV9oaWdoOwp9OwoKdm9pZCBjaGVja0FsbW9zdEVxdWFsKGRvdWJsZSBnb3QsIGRvdWJs ZSB3YW50LCBzdGQ6OnN0cmluZyBtZXNzYWdlKSB7CiAgaWYgKGZhYnMod2FudCAtIGdvdCkgPiAx ZS0yKSB7CiAgICBwcmludGYoIkZBSUw6ICVzXG4iLCBtZXNzYWdlLmNfc3RyKCkpOwogIH0gZWxz ZSB7CiAgICBwcmludGYoIlBBU1M6ICVzXG4iLCBtZXNzYWdlLmNfc3RyKCkpOwogIH0KfQoKLy8g UnVucyBidWNrZXRpbmcgdHJpYWxzLgovLyBTa2lwcyBza2lwSW5pdGlhbCBudW1iZXIgb2YgcmFu ZG9tIHZhbHVlcy4KLy8gSWdub3JlcyBpZ25vcmVQZXJjZW50YWdlIG9mIHRyaWFscy4Kdm9pZCBy dW5UZXN0cyhpbnQgc2tpcEluaXRpYWwsIGludCBpZ25vcmVQZXJjZW50YWdlKSB7CiAgY29uc3Qg aW50IE5VTV9UUklBTFMgPSAxMDAwMDA7CiAgLy8gU2ltdWxhdGUgYnVja2V0aW5nIGludG8gT3Jp Z2luYWwgYW5kIFZhcmlhdGlvbiAjMS4KICBpbnQgYnVja2V0c1syXSA9IHswLCAwfTsKICBpbnQg bnVtTm90SWdub3JlZCA9IDA7CiAgZm9yIChpbnQgaT0wOyBpIDwgTlVNX1RSSUFMUzsgKytpKSB7 CiAgICBXZWFrUmFuZG9tIHBybmcoTXlSYW5kb20oKSk7CiAgICBmb3IgKGludCBqPTA7IGogPCBz a2lwSW5pdGlhbDsgKytqKSB7IHBybmcuZ2V0KCk7IH0KICAgIGlmIChpZ25vcmVQZXJjZW50YWdl ID4gaW50KGZsb29yKHBybmcuZ2V0KCkgKiAxMDApKSkgewogICAgICBjb250aW51ZTsKICAgIH0K CiAgICArK251bU5vdElnbm9yZWQ7CiAgICBkb3VibGUgcnZhbCA9IHBybmcuZ2V0KCk7CiAgICBh c3NlcnQoMCA8IHJ2YWwgJiYgcnZhbCA8IDEpOwogICAgLy8gQnVja2V0IHdpdGggNTAgLSA1MCBk aXN0cmlidXRpb24gaW50byBPcmlnaW5hbCBhbmQgVmFyaWF0aW9uICMxLgogICAgaWYgKHJ2YWwg PCAwLjUpIHsKICAgICAgYnVja2V0c1swXSsrOwogICAgfSBlbHNlIHsKICAgICAgYnVja2V0c1sx XSsrOwogICAgfQogIH0KCiAgaW50IG51bUlnbm9yZWQgPSBOVU1fVFJJQUxTIC0gbnVtTm90SWdu b3JlZDsgCiAgcHJpbnRmKCJPZiAlZCB0ZXN0cywgJWQgaWdub3JlZCwgJWQgbm90IGlnbm9yZWRc biIsIE5VTV9UUklBTFMsIG51bUlnbm9yZWQsIG51bU5vdElnbm9yZWQpOwogIHByaW50ZigiQnVj a2V0IGNvdW50cyAlZCAlZCwgcmF0aW8gPSAlZlxuIiwgYnVja2V0c1swXSwgYnVja2V0c1sxXSwg ZmxvYXQoYnVja2V0c1swXSkvYnVja2V0c1sxXSk7CiAgcHJpbnRmKCJcblxuIik7CiAgY2hlY2tB bG1vc3RFcXVhbChudW1JZ25vcmVkL2RvdWJsZShOVU1fVFJJQUxTKSwgaWdub3JlUGVyY2VudGFn ZS8xMDAuMCwgIklnbm9yZXMgdHJpYWxzIGFzIGV4cGVjdGVkIik7CiAgY2hlY2tBbG1vc3RFcXVh bChidWNrZXRzWzBdL2RvdWJsZShudW1Ob3RJZ25vcmVkKSwgMC41LCAiRmlyc3QgYnVja2V0IGNv dW50IGFzIGV4cGVjdGVkIik7CiAgY2hlY2tBbG1vc3RFcXVhbChidWNrZXRzWzFdL2RvdWJsZShu dW1Ob3RJZ25vcmVkKSwgMC41LCAiU2Vjb25kIGJ1Y2tldCBjb3VudCBhcyBleHBlY3RlZCIpOwp9 CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqKmFyZ3YpIHsKICBpbnQgaWdub3JlUGVyY2VudGFn ZSA9IDUwOwogIGlmIChhcmdjID4gMSkgewogICAgaWdub3JlUGVyY2VudGFnZSA9IGF0b2koYXJn dlsxXSk7CiAgfQogIGludCBza2lwSW5pdGlhbCA9IDA7CiAgaWYgKGFyZ2MgPiAyKSB7CiAgICBz a2lwSW5pdGlhbCA9IGF0b2koYXJndlsyXSk7CiAgfQoKICBwcmludGYoIlJ1bm5pbmcgYnVja2V0 aW5nIHRlc3RzOlxuIik7CiAgcnVuVGVzdHMoc2tpcEluaXRpYWwsIGlnbm9yZVBlcmNlbnRhZ2Up OwoKICByZXR1cm4gMDsKfQo=