an inverse permutation test

A straightforward but probabilistic riddle this week in the Riddler, which is to find the expected order of integer i when the sequence {1,2,…,n} is partitioned at random into two sets, A and B, each of which is then sorted before both sets are merged. For instance, if {1,2,3,4} is divided in A={1,4} and B={2,3}, the order of 2 in {1,4,2,3} is 3. An R rendering of the experiment is

m=rbinom(1,n,.5)
if (m*(n-m)>0){
fist=sort(sample(1:n,m))
return(order(c(fist,sort((1:n)[-fist])))[i])
}else{
return(i)}

It is rather easy to find that the probability that the order of i takes the value j is

{i-1 \choose j-1}(1/2)^i

if j<i (i is in A) and

{n-i \choose n-j}(1/2)^{n-i+1}

if $j>i$ (i is in B), the case i=j being the addition of both cases, but the mean can be found (almost) immediately by considering that, when i is in A, its average value is (i+1)/2 and when it is in B, its average value is (n+i)/2 [by symmetry]. Hence a global mean of (2i+n+1)/4….

3 Responses to “an inverse permutation test”

  1. You might want to consider adding a note to your blog entries that contain latex that visiting your blog directly is better than viewing on rbloggers since the latex doesn’t display properly there.

    • Thank you Dason, I can see the extent of the problem on R-bloggers as indeed LaTeX formulas end up as literal black boxes! However, I feel that writing a warning about LaTeX fomulas each time I use one in a post would quickly turn bothersome. Whenever I can, I use HTML special symbols to bypass the use of embedded LaTeX, as it does not look very nice. Other media like Stack Exchange manage much better. (Or it may just be the WordPress theme I use that prevents nice rendering…)

  2. […] article was first published on R – Xi'an's Og, and kindly contributed to […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s