Skip to content

Instantly share code, notes, and snippets.

@josejuan
Last active June 5, 2022 20:39
Show Gist options
  • Save josejuan/b19a2a772675b14b975a1cd8743b7b40 to your computer and use it in GitHub Desktop.
Save josejuan/b19a2a772675b14b975a1cd8743b7b40 to your computer and use it in GitHub Desktop.
/*
The following function
public static long rand(int min, int max) {
return (System.nanoTime()%(max-min)) + min;
}
does not generate random numbers with a known distribution;
the properties (randomness) of the output depend on factors that modify it.
The following example shows how the same function used in EXACTLY
the same way but at different times generates different random distributions.
Given the same statistic, for the same sample on the "same" random distribution
(the `rand` function), we can see that we get totally different values (they should
coincide at 50% but there is a 70% 30% bias).
trues: 70
falses: 30
*/
package com.computermind.sandbox.algorithms;
import java.util.Arrays;
public class RandomTest {
public static long rand(int min, int max) {
return (System.nanoTime()%(max-min)) + min;
}
public static float diff(long[] arr, int loops, int sz) {
// check counting is exactly loops * sz
int s = 0;
for (long l : arr) s += l;
if(s != loops * sz)
throw new IllegalStateException();
Arrays.sort(arr);
return (1.0f * arr[0]) / arr[arr.length - 1];
}
// uniform distribution |_|_|_|_|....|_|
public static long [] test1(int loops, int sz) {
long [] xs = new long[sz];
for(int i = 0; i < loops * sz; i++)
xs[(int) rand(0, sz)] += 1;
return xs;
}
// discrete distribution with holes |_|_|_._._._|_|_|_._._.
public static long [] test2(int loops, int sz) {
long [] xs = new long[sz];
int r = 0;
for(int i = 0; i < (loops * sz) / 10; i++) {
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
for(int j = 0; j < 1_000; j++)
r += j % 0x1013;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
xs[(int) rand(0, sz)] += 1;
}
if(r % 12371 == 0)
System.out.printf("ops%n");
return xs;
}
public static void main(String... args) {
int loops = 1000, sz = 1000;
// hypothesis; (x1 + x3) > (x2 + x4) (with high P) when should be all equals (for long runs)
int trues = 0, falses = 0;
for(int i = 0; i < 100; i++) {
float x1 = diff(test1(loops, sz), loops, sz);
float x2 = diff(test2(loops, sz), loops, sz);
float x3 = diff(test1(loops, sz), loops, sz);
float x4 = diff(test2(loops, sz), loops, sz);
if(x1 + x3 > x2 + x4)
trues += 1;
else
falses += 1;
}
System.out.printf("trues: %d%nfalses: %d%n", trues, falses);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment