From: Gareth McCaughan <gareth.mccaughan@pobox.com>

...

WDS: I stumbled across this apparently true fact:

Choose N random i.i.d. real numbers (from some fixed probability density) then sort them; result is (a,b,c,d,...,z).

Do it again independently, result is (A,B,C,D,...,Z).

Then what is the chance that a<A, b<B, c<C, ..., and z<Z simultaneously? ("vector domination")

G.McC: Put 'em all together and sort them. Now go through them in order and move north 1 unit when you see an a/b/.../z and east one unit when you see an A/B/.../Z. The "vector domination" criterion is the same as saying that you never go below the line x=y (starting, of course, at the origin). The fact that you chose N of each says that you end up at (N,N).

But now we have a familiar problem with a familiar answer. The number of paths with this property is, e.g., the same as the number of properly-nested sequences of parentheses: the N'th Catalan number, which "as every schoolboy knows" is (2N choose N) / (N+1). There are plenty of proofs of this around; choose your favourite.

--Superb!!! Excellent!! Wow!!! I'd actually just figured out what looked like it was going to be a proof of my own, which was, however, going to be way more horrible than your proof. This is a new kind of "ballot problem"; there is a considerable literature on such problems but I happen to think this particular problem is nicer than most of them. Here's a tutorial by Steven R. Dunbar about various kinds of ballot problems, which is by no means a complete survey... but I did look in a number of such surveys and my problem was not in them... http://www.math.unl.edu/~sdunbar1/ProbabilityTheory/Lessons/BernoulliTrials/... In a sense, your "sort 'em all together / north+east" trick converts my continuous kind of ballot problem into one of the old discrete kinds. Your trick should then also solve the version where one sequence of numbers has N elements and the other has k*N (where k=1,2,3,... is fixed) and your line now has slope=k (or 1/k).