[Jprogramming] Comparing pairs of random permutations

[Henry Rich]

The question was, Is this a well-known problem?  The answer
is, Yes.  I don't think the discussion that has appeared
here so far constitutes a proof that the expected number of
matches is 1, but I have found one:

http://www.math.uni-bielefeld.de/~sillke/PUZZLES/fixpoints-expected

a useful preliminary is

http://faculty.wheelock.edu/dborkovitz/articles/ngm6.htm



The problem of finding the probability of no match was one that
was assigned in one of my statistics courses 35 years ago, and
I never worked out how to do it, so I am glad to have been provided
the occasion of finally understanding the solution.

Henry Rich

> -----Original Message-----
> From: programming-bounces at jsoftware.com 
> [mailto:programming-bounces at jsoftware.com] On Behalf Of Devon 
> McCormick
> Sent: Saturday, August 30, 2008 1:46 PM
> To: J-programming forum
> Subject: [Jprogramming] Comparing pairs of random permutations
> 
> Members of the Forum -
> 
> I had a blind-tasting last night where we sampled five 
> different wines.
> After two rounds of tasting the wines in the same order, we 
> had a round
> where we sampled them in a random, unknown order. Afterwards, 
> we tried to
> guess which wines from the random order corresponded to their original
> numbering. On average, we were able to do this only once each.
> 
> Not knowing how this shakes out by chance, I did the 
> following to simulate
> comparing pairs of random permutations of five items to see 
> how our results
> compared to random selection.
> 
>    ?~5      NB. 5-permutation
> 0 4 3 1 2
>    $rs=. ?~2 1000$5    NB. 1000 pairs of 5-permutations
> 2 1000 5
>    0{=/rs                NB. Look at the first comparison
> 1 0 0 0 0
>    0{"2 rs               NB. and permutation pair.
> 1 0 4 3 2
> 1 3 2 0 4
>    +/,=/rs                NB. How many total matches?
> 992                       NB. Average of 1.
> 
> So, our ability to recognize the wines we'd just tasted twice 
> is no better
> than random. It occurred to us that perhaps five is too many 
> to distinguish
> and maybe we should taste only two at a time if we do this again.
> 
> So, what would be the random match if we did this with only two wines?
> 
>    +/,=/?~2 1000$2
> 986
> 
> Huh? It's the same: about one on average. Try this for other 
> permutation
> lengths....
> 
>    +/,=/?~2 1000$3
> 992
>    +/,=/?~2 1000$10
> 982
> 
> Try larger sample size too.
> 
>    +/,=/?~2 10000$5
> 9886
>    +/,=/?~2 10000$10
> 10185
>    +/,=/?~2 10000$20
> 10058
>    +/,=/?~2 10000$100
> 10049
> 
> No matter what size the permutation, the average chance of a 
> match is about
> one. This seems counter-intuitive to me. Am I doing something 
> wrong in my J
> code or is this one of those well-known theorems of 
> statistics about which
> I'm completely ignorant?
> 
> You decide.
> 
> Regards,
> 
> Devon McCormick
> ^me^ at acm.
> org is my
> preferred e-mail
> ----------------------------------------------------------------------
> For information about J forums see 
> http://www.jsoftware.com/forums.htm