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?

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.
