Thanks for the references, Henry. Using Raul's observation that we can compare i.N to N?N gives a faster function: rpm=: 13 : '(i.y.)+/ . = y?y'"0
Also, we can use this for a proof, not a general one, but if we enumerate the matches thusly: 0,!N-1 NB. Number having a zero in position 0 1,!N-1 NB. Number having a one in position 1 2,!N-1 NB. Number having a two in position 2 ... (N-1),!N-1 NB. Number having (N-1) in position (N-1) we see we'll have (N%!N-1) matches, which is (1%!N-1). Using our faster simulation one million times for matches on 100 items: >./mm=. rpm 1e6$100 9 Looking at the distribution of number of matches: +/mm =/ i.10 367132 367876 184371 61444 15491 3105 508 66 6 1 These ratios match those in Henry's second reference ( http://faculty.wheelock.edu/dborkovitz/articles/ngm6.htm) to limited precision: %(^1)*!i.10 [ 9!:11]4 0.3679 0.3679 0.1839 0.06131 0.01533 0.003066 0.0005109 7.299e_5 9.124e_6 1.014e_6 If we look at the distribution for my original problem of five things, we see mm=. rpm 1e6$5 +/mm =/ i.6 365976 375745 166694 83220 0 8365 This zero near the end is because there can't be only four matches, so this is why this result doesn't agree with the theoretical percentages in the paper mentioned by Henry. On Wed, Sep 3, 2008 at 3:54 PM, Henry Rich <[EMAIL PROTECTED]> wrote: > 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<http://www.math.uni-bielefeld.de/%7Esillke/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 > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
