# Taking two sets (A, B) out of the same distribution, merging and then sorting should roughly result in a,b,a,b,a,b?

Suppose I take 2 sets ($A$ and $B$) of 1000 random items out the same distribution; I also suppose that all items are different. I then create a new set $C$ which is the union of $A$ and $B$, since all items are different it has 2000 elements. If $C$ is sorted (ascending or descending), should I roughly end up with a sequence: $a_0,b_1,a_2,b_3,a_4,b_5,...a_i,b_j,...b_{2000}$ ($a_i$ is an element of $A$ and $b_j$ is an element of $B$?

Or alternatively should the number of runs (defined by Wald-Wolfowitz) be almost equal to number of elements in $C$? Here a run is a follow up of elements from the same set. For example:

• $a,b,a,b$ has 4 runs
• $a,a,a,b,b$ has 2 runs
• $a,b,b,b,a,a$ has 3 runs

If this would not be case, what's the reason behind it?

To give a more practical setting, I also implemented this now and asked it on stackoverflow.

• Some or same? Either way there is not information to determine the sequence. Apr 26 '17 at 15:15
• The same distribution, I changed it. Apr 26 '17 at 15:28
• This seems clear enough to me. I'm voting to leave open. Apr 26 '17 at 16:15
• @gung Do you know what the other eliminates in the sets are either before or after they are merged? Apr 26 '17 at 17:29
• @MichaelChernick I'm not sure what you mean, but when the sets are merged, the union is taken and no elements are eliminated. Apr 26 '17 at 20:41

Cool question! If we generalize your framework and let $n$ represent the number of items in each set, then we can make some headway toward finding the solution. In your case $n = 1000$. But what if we let $n = 1$? There are always ${2n} \choose {n}$ total arrangements so in the simplest case where $n=1$, there are just two possibilities. Both have 2 runs. Now, consider $n=2$. There are ${2n} \choose {n}$ $= 6$ arrangements and the average number of runs is exactly 3. Going further, $n=3$ leads to 20 arrangements and an average of 4 runs. At this point, it seems unlikely that the answer will ever differ from $n+1$ as the average number of runs. This can probably be proved by induction pretty easily.
By comparing your problem to the Mann-Whitney test I guess you are correct, in the sense that the run lengths should not be much different from one. This test is based on summing the ranks of each set (a or b in your case) and then looking at the difference.