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?
 A: This is exactly as it should be. A nice illustration of how our intuition can go wrong.
Let's start by considering the case of having only two entries per array:
$$ (a_1, a_2)\quad\text{and}\quad(b_1, b_2). $$
We will disregard ties, which make stuff only more complicated, not more interesting.
Suppose $a_1<b_1$ (so your Boolean is TRUE). By construction, we know that $a_1<a_2$ and $b_1<b_2$. We are interested in how $a_2$ and $b_2$ relate. We have two possible cases:

*

*If $a_1<a_2<b_1$, then we definitely have $a_2<b_2$, simply because $b_1<b_2$. Your second Boolean is again TRUE.

*If $b_1<a_2$, then we know that both $a_2$ and $b_2$ are greater than $b_1$. Since they are IID, the probability of $a_2<b_2$ and of $a_2>b_2$ is equal, and we have equal chances of your second Boolean being TRUE or FALSE.

The asymmetry thus stems from case 1. Simply said, if the first Boolean is TRUE, then there is more "space" for $a_2$ to fall between $a_1$ and $b_1$, and all this "space" results in the second Boolean being TRUE. Thus, conditional on the first Boolean being TRUE, the probability of the second being TRUE is higher than for the second to be FALSE.
And then we can repeat the process for later realizations. The particular probabilities will depend on the distributions of your $a$ and $b$.
And of course the same argument holds if we start with a FALSE.
A: 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
