Element-wise comparisons of sorted subsets of random numbers yield nonrandom results Say we have a random number generator. It generates 2000 numbers that we put in two arrays, 1000 numbers each. Like this (here shorter arrays used to illustrate the point):
[4, 20, 5, 6]
[7, 21, 3, 3]
Then we sort each array and get:
[4, 5, 6, 20]
[3, 3, 7, 21]
Then we compare corresponding numbers in arrays and generate another with true/false (true if the number at position i is higher in the second array from the number in the first array):
[false, false, true, true]
For large arrays I would expect the number of falses to be more or less equal to the number of trues. (Almost exactly as in fair coin toss). However, when I use computer's random number generator (supposedly cryptographically secure) I almost always get large disproportion of one vs the other. Why is that?

We can relate this to Donsker's theorem. The ordered sequence that you generate is similar to an empirical distribution function and will approach a Brownian bridge.
So basically your question is about the distribution of positive and negative values of a Brownian bridge that starts at 0 and ends at 0.
A Brownian bridge is not the same as Gaussian white noise


*

*White noise: each value is independent from the other. The probability that for the k-th sample random number generator A is above random number generator B is independent from the probability that for the (k+1)-th sample random number generator A is above random number generator B is independent.
In this case you would expect the false and true values to follow a binomial distribution.


*Brownian bridge: You will get that the values correlate. If the k-th value is relatively high then the (k+1)-th value will also be high.
In this case you would expect a larger variance for the difference between false and true values. More precisely, the distribution will be a uniform distribution: Distribution of positive and negative values in a Brownian bridge
