<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/sampling-by-exhaustion/"></div></div><div><a data-url="https://www.r-bloggers.com/sampling-by-exhaustion/" data-counturl="https://www.r-bloggers.com/sampling-by-exhaustion/" data-count="horizontal" data-text="sampling by exhaustion" 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/11/25/sampling-by-exhaustion/"> 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>T</strong>he riddle set by <a target="_blank" rel="nofollow" href="http://fivethirtyeight.com/features/the-puzzle-of-the-lonesome-king/">The Riddler of last week</a> sums up as follows:</p>
<blockquote>
<p><em><span>Within a population of size N, each individual in the population independently selects another individual. All individuals selected at least once are removed and the process iterates until one or zero individual is left. What is the probability that there is zero individual left?</span></em></p>
</blockquote>
<p><a target="_blank" rel="nofollow" href="https://i1.wp.com/xianblog.files.wordpress.com/2016/11/riddler1118.jpg?ssl=1"><img sizes="(max-width: 367px) 100vw, 367px" alt="" class="wp-image-32050" src="https://i1.wp.com/xianblog.files.wordpress.com/2016/11/riddler1118.jpg?resize=367%2C367&ssl=1" data-recalc-dims="1"></a>While I cannot see a clean analytical solution to this problem, it reminds me of an enveloppe-versus-letter (matches) problem I saw in graduate school. Indeed, the expected number of removed (or selected) individuals is given by</p>
<p><img title="N\left\{1-\frac{N-2}{N-1}\right\}^{N-1}" alt="N\left\{1-\frac{N-2}{N-1}\right\}^{N-1}" class="latex" src="https://s0.wp.com/latex.php?latex=N%5Cleft%5C%7B1-%5Cfrac%7BN-2%7D%7BN-1%7D%5Cright%5C%7D%5E%7BN-1%7D&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>which is equivalent to (1-e⁻¹)N for N large, meaning that the population decreases by an average factor of e⁻¹ at each round. And that it takes on average approximately log(N) iterations to reach a single individual. A simulation of the first probabilities of ending with one individual led me to the above curve, which wiggles in an almost periodic way around the probability ½, equal to the average of those probabilities. Using the R code</p>
<pre>
rad=function(N){#next population size
  ut=sample(rep(2:N,2),1)
  for (i in 2:N)#sampling
   ut=c(ut,sample(rep((1:N)[-i],2),1))
  return(N-length(unique(ut))}
sal=rep(0,m);sal[1]=1
for (N in 3:M){
 prop=0;
 for (t in 1:T){#one single step
   i=rad(N)
   if (i>0) prop=prop+sal[i]}
 sal[N]=prop/T}
</pre>
<p>which exploits the previously computed probabilities. The variability is most interesting if unexpected, but looking back at <a target="_blank" rel="nofollow" href="http://amzn.to/2gsv2S3">Feller</a>‘s sections and exercises on the classical occupancy problem, I could not find a connection with this problem. If it exists. Still, if N is large enough, the exclusion of one index from the selection becomes negligible and the probability of moving from n to m individuals should be approximately <a target="_blank" rel="nofollow" href="http://amzn.to/2gsv2S3">[Feller, eqn (2.4), p.102]</a></p>
<p><img title="p_n(m)={n\choose m}\sum_{v=}^{n-m} (-1)^v {n-m\choose v} \left(1-\frac{m+v}{n}\right)^n" alt="p_n(m)={n\choose m}\sum_{v=}^{n-m} (-1)^v {n-m\choose v} \left(1-\frac{m+v}{n}\right)^n" class="latex" src="https://s0.wp.com/latex.php?latex=p_n%28m%29%3D%7Bn%5Cchoose+m%7D%5Csum_%7Bv%3D%7D%5E%7Bn-m%7D+%28-1%29%5Ev+%7Bn-m%5Cchoose+v%7D+%5Cleft%281-%5Cfrac%7Bm%2Bv%7D%7Bn%7D%5Cright%29%5En&bg=000000&%23038;fg=B0B0B0&%23038;s=0"></p>
<p>This formula approximates quite well the exact probability, but as in a <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/2012/02/01/the-birthday-problem/">previous post about the birthday problem</a>, it proves quite delicate to compute. As already noticed by <a target="_blank" rel="nofollow" href="http://amzn.to/2gsv2S3">Feller</a>.</p>
<p>Filed under: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/books/">Books</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/kids/">Kids</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/r-statistics/">R</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/category/statistics/">Statistics</a> Tagged: <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/birthday-problem/">birthday problem</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/occupancy/">occupancy</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/sampling/">sampling</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/the-riddler/">The Riddler</a>, <a target="_blank" rel="nofollow" href="https://xianblog.wordpress.com/tag/william-feller/">William Feller</a> <a target="_blank" rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/xianblog.wordpress.com/32047/"><img alt="" src="http://feeds.wordpress.com/1.0/comments/xianblog.wordpress.com/32047/" 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/sampling-by-exhaustion/"></div></div><div><a data-url="https://www.r-bloggers.com/sampling-by-exhaustion/" data-counturl="https://www.r-bloggers.com/sampling-by-exhaustion/" data-count="vertical" data-text="sampling by exhaustion" 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/11/25/sampling-by-exhaustion/"> 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/O6hkZhZ9hkU"></a></div>