Oleg -
your idea of pairing up the indexes into a table of all the permutation
pairs is very illuminating. This makes it plain that any exhaustive pairing
of n-permutations will be a table of shape 2$!n . The matches correspond to
the major diagonal, so however much the table grows, so will this diagonal.
Since there's a single diagonal element in any row or column, we average a
single hit.
Thanks for the insight,
Devon
On 8/30/08, Oleg Kobchenko <[EMAIL PROTECTED]> wrote:
>
> In wine tasting, you count Each item (+/,) hit between two sets.
> It is different from Any-item (+/+./) or All-items (+/*./) matching.
>
> Let's look at All-items case, similar could applied to other cases.
>
> We have permutations (?~). And when considering All-items match
> permutation can be replaced with its index.
> So what is the universe and match events?
>
> For n=2 items we have:
> 0 : 0 1 indices
> 1 : 1 0
>
> 0 0 0 1 toss pairs
> 1 0 1 1
> There are 2 matches out of 4 tosses, a 0.5 chance.
>
> For number of n=3 items.
> ([EMAIL PROTECTED] A. i.)3
> 0 1 2
> 0 2 1
> 1 0 2
> 1 2 0
> 2 0 1
> 2 1 0
>
> we have 6 = !3 permutations
>
> <"2,"0/~i.6
> +---+---+---+---+---+---+
> |0 0|1 0|2 0|3 0|4 0|5 0|
> |0 1|1 1|2 1|3 1|4 1|5 1|
> |0 2|1 2|2 2|3 2|4 2|5 2|
> |0 3|1 3|2 3|3 3|4 3|5 3|
> |0 4|1 4|2 4|3 4|4 4|5 4|
> |0 5|1 5|2 5|3 5|4 5|5 5|
> +---+---+---+---+---+---+
>
> we notice that total number of pairs is
> (!n)^2 and total matches is !n. So probability
> is 1%!n. Here it's 1%6.
>
>
> $ , /,"0/~i.!3
> 36 2
> +/=/|:,/,"0/~i.!3
> 6
>
> 6%36
> 0.166667
> %!3
> 0.166667
>
> For n=5,
>
> $ , /,"0/~i.!5
> 14400 2
> +/=/|:,/,"0/~i.!5
> 120
>
> (, *:) !5
> 120 14400
> x:(% *:) !5
> 1r120
>
> Experimentally, with All-items compare, matches reduce
> proportional to ! of set size.
>
> (!2)* +/-:"1/?~2 1000$2
> 1032
> (!2)* +/-:"1/?~2 1000$2
> 982
>
> (!3)* +/-:"1/?~2 1000$3
> 1044
> (!3)* +/-:"1/?~2 1000$3
> 906
>
> (!5)* +/-:"1/?~2 1000$5
> 1440
> (!5)* +/-:"1/?~2 1000$5
> 600
>
>
>
>
>
>
> ----- Original Message ----
> > From: Devon McCormick <[EMAIL PROTECTED]>
> >
> > 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
