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: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
