[math-fun] vector domination probability problem (insanely annoying)
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") My original incorrect answer was 2^(-N). Complete with wrong proof. My new correct answer is 1/(N+1). I proved this for N=1,2,3,4,5,6. It presumably is true for N=7,8,9... too. But what is the proof? Surely something this simple must have a simple proof?
On 19/11/2014 23:03, Warren D Smith wrote:
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")
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. -- g
Neat proof! WFL On 11/19/14, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 19/11/2014 23:03, Warren D Smith wrote:
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")
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.
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It seems neither Gareth McCaughan's proof nor my problem are really new... Wm.Feller: Probabillity Theory, vol I, section III.9 (see also III.1) discusses "Galton's rank order test" and gives essentially the same result & proof, plus a bit more, although I like G.McC's proof's details more. It seems some version of this result has been rediscovered at least 4 times. Apparently Francis Galton in 1876 was looking at some data of Ch.Darwin and deduced a totally unjustified conclusion from it because he did not understand that, due to G.McC's proof, the vector domination probability is actually quite large. His name was then immortalized in honor of his stupid error. J.L.Hodges Jr: Galton's rank order test, Biometrika 42 (1955) 261-262. Balazs Montagh: A simple proof and a generalization of an old result of Chung and Feller, Discrete Mathematics 87,1 (Jan. 1991) 105-108. K.L. Chung and W. Feller: Fluctuations in coin tossing, Proc. Nat. Acad. Sci. USA 35 (1949) 605-608. Montagh proves it using this CYCLIC LEMMA: For any k with 1<=k<=N, if a1,a2,...,aN is a sequence of integers with sum=1, then there is exactly one cyclic shift of this sequence having exactly k positive partial sums. Lemma attributed to G.N.Raney, Trans.Amer.Mathl Soc. 94 (1960) 441-451. A more general version of the cycle lemma is given by Nachum Dershowitz & Shmuel Zaks: The Cycle Lemma and Some Applications, European J. Combinatorics 11,1 (1990) 35-40 http://www.cs.tau.ac.il/~nachum/papers/CL.pdf http://www.sciencedirect.com/science/article/pii/S0195669813800534 who also give references showing it too has been rediscovered some ghastly number of times. So anyhow, in Gareth McCaughan's proof, we could at some point consider the 2N-character strings over the 2-letter alphabet "(" and ")" having exactly N of each, regard bigrams ((=2, ()=)(=0, ))=-2 to get a N-integer sequence, adjoin the number "1" to said sequence, apply cyclic lemma to deduce exactly 1 cyclic shift of each sequence has all partial sums positive and hence yields balanced parentheses in original problem.
participants (3)
-
Fred Lunnon -
Gareth McCaughan -
Warren D Smith