<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/an-inverse-permutation-test/"></div></div><div><a data-url="https://www.r-bloggers.com/an-inverse-permutation-test/" data-counturl="https://www.r-bloggers.com/an-inverse-permutation-test/" data-count="horizontal" data-text="an inverse permutation test" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2016/09/23/an-inverse-permutation-test/"> R – Xi'an's Og</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><strong><a target="_blank" href="https://i0.wp.com/xianblog.files.wordpress.com/2011/11/pict0265.jpg?ssl=1"><img title="Sceaux, Oct. 31. 2011: my daughter has started a photography project where she takes the same picture of our oak day after day. She was away this week so trusted me with the task and I took extra pictures on the side, as the leaves have just reached their optimal colour..." class="wp-image-13187" src="https://i0.wp.com/xianblog.files.wordpress.com/2011/11/pict0265.jpg?resize=450%2C338&ssl=1" data-recalc-dims="1"></a>A</strong> straightforward but probabilistic riddle this week in <a target="_blank" href="http://fivethirtyeight.com/features/how-high-can-count-von-count-count/">the Riddler</a>, 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</p>
<p>
m=rbinom(1,n,.5)<br>
if (m*(n-m)>0){<br>
fist=sort(sample(1:n,m))<br>
return(order(c(fist,sort((1:n)[-fist])))[i])<br>
}else{<br>
return(i)}<br>
[\sourcecode]</p>
<p>It is rather easy to find that the probability that the order of i takes the value j is</p>
<p><img title="{i-1 \choose j-1}(1/2)^i" alt="{i-1 \choose j-1}(1/2)^i" class="latex" src="https://s0.wp.com/latex.php?latex=%7Bi-1+%5Cchoose+j-1%7D%281%2F2%29%5Ei&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>if j&lt;i (i is in A) and</p>
<p><img title="{n-i \choose n-j}(1/2)^{n-i+1}" alt="{n-i \choose n-j}(1/2)^{n-i+1}" class="latex" src="https://s0.wp.com/latex.php?latex=%7Bn-i+%5Cchoose+n-j%7D%281%2F2%29%5E%7Bn-i%2B1%7D&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>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….</p>
<p>Filed under: <a target="_blank" href="https://xianblog.wordpress.com/category/books/">Books</a>, <a target="_blank" href="https://xianblog.wordpress.com/category/kids/">Kids</a>, <a target="_blank" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a>, <a target="_blank" href="https://xianblog.wordpress.com/category/statistics/">Statistics</a> Tagged: <a target="_blank" href="https://xianblog.wordpress.com/tag/order-statistics/">order statistics</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/permutation-tests/">permutation tests</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/r/">R</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/sorting/">sorting</a>, <a target="_blank" href="https://xianblog.wordpress.com/tag/the-riddler/">The Riddler</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/31553/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/31553/" border="0"></a> <img alt="" src="https://i1.wp.com/pixel.wp.com/b.gif?resize=1%2C1&ssl=1" border="0" data-recalc-dims="1"></p>
<p><div><div><div><div data-width="55" data-show-faces="false" data-send="true" data-layout="box_count" data-height="62" data-href="https://www.r-bloggers.com/an-inverse-permutation-test/"></div></div><div><a data-url="https://www.r-bloggers.com/an-inverse-permutation-test/" data-counturl="https://www.r-bloggers.com/an-inverse-permutation-test/" data-count="vertical" data-text="an inverse permutation test" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://xianblog.wordpress.com/2016/09/23/an-inverse-permutation-test/"> R – Xi'an's Og</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/?s=data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/?s=Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/?s=map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/?s=animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/?s=RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/?s=sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/?s=LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/?s=SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/?s=eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/?s=git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/?s=hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/?s=Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/?s=regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/?s=PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/?s=time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/?s=trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/ZaS5Krhz600"></a></div>