[Webkit-unassigned] [Bug 137396] New: Bias in first few random numbers generated by WeakRandom

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=137396

           Summary: Bias in first few random numbers generated by
                    WeakRandom
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: Macintosh Intel
        OS/Version: Unspecified
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: JavaScriptCore
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: ajith at optimizely.com


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

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.