<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/maximal-spacing-around-order-statistics/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://xianblog.wordpress.com/2018/05/17/maximal-spacing-around-order-statistics/"> 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 rel="nofollow" href="https://xianblog.files.wordpress.com/2018/05/riddler0512.png" target="_blank"><img data-orig-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.png" data-orig-size="844,604" data-medium-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.png?w=300" data-attachment-id="36123" data-image-meta="{" data-image-description="" src="https://xianblog.files.wordpress.com/2018/05/riddler0512.png?w=450&h=322&fit=450%2C322&resize=450%2C322" data-permalink="https://xianblog.wordpress.com/2018/05/17/maximal-spacing-around-order-statistics/riddler0512/" data-large-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.png?w=450&amp;h=322&amp;fit=450%2C322&amp;resize=450%2C322" alt="" data-image-title="riddler0512" title="the original paper of Gumbel got published in the Annales de l'Institut Henri Poincaré, in French and in 1935..." sizes="(max-width: 450px) 100vw, 450px" width="450" data-comments-opened="1" class="wp-image-36123" data-recalc-dims="1" height="322"></a>T</strong>he <a rel="nofollow" href="https://fivethirtyeight.com/features/how-hard-is-it-to-find-a-running-buddy/" target="_blank">riddle from the Riddler</a> for the coming weeks is extremely simple to express in mathematical terms, as it summarises into characterising the distribution of</p>
<p><img alt="Delta_n=max_i,min_j,|X_{i}-X_{j}|" title="Delta_n=max_i,min_j,|X_{i}-X_{j}|" src="https://s0.wp.com/latex.php?latex=%5CDelta_n%3D%5Cmax_i%5C%2C%5Cmin_j%5C%2C%7CX_%7Bi%7D-X_%7Bj%7D%7C&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>when the n-sample is made of iid Normal variates. I however had a hard time finding a result connected with this quantity since most available characterisations are for either Uniform or Exponential variates. I eventually found a <a rel="nofollow" href="https://arxiv.org/abs/1702.05910" target="_blank">2017 arXival</a> by Nagaraya et al.  covering the issue. Since the Normal distribution belongs to the Gumbel domain of attraction, the extreme spacings, that is the spacings between the most extreme orders statistics [rescaled by nφ(Φ⁻¹{1-n⁻¹})] are asymptotically independent and asymptotically distributed as (<a rel="nofollow" href="https://arxiv.org/abs/1702.05910" target="_blank">Theorem 5, p.15</a>, after correcting a typo):</p>
<p><img alt="(xi_1,xi_2/2,...)" title="(xi_1,xi_2/2,...)" src="https://s0.wp.com/latex.php?latex=%28%5Cxi_1%2C%5Cxi_2%2F2%2C...%29&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>where the ξ’s are Exp(1) variates. A crude approximation is thus to consider that the above Δ is distributed as the maximum of two standard and independent exponential distributions, modulo the rescaling by  nφ(Φ⁻¹{1-n⁻¹})… But a more adequate result was pointed out to me by Gérard Biau, namely a <a rel="nofollow" href="https://projecteuclid.org/euclid.aop/1176992622" target="_blank">1986 Annals of Probability paper</a> by Paul Deheuvels, my former head at ISUP, Université Pierre and Marie Curie. In this paper, Paul Deheuvels establishes that the largest spacing in a normal sample, M¹, satisfies</p>
<p><img alt="mathbb{P}(sqrt{2log,n},M^1le x) to prod_{i=1}^{infty} (1-e^{-ix})^2" title="mathbb{P}(sqrt{2log,n},M^1le x) to prod_{i=1}^{infty} (1-e^{-ix})^2" src="https://s0.wp.com/latex.php?latex=%5Cmathbb%7BP%7D%28%5Csqrt%7B2%5Clog%5C%2Cn%7D%5C%2CM%5E1%5Cle+x%29+%5Cto+%5Cprod_%7Bi%3D1%7D%5E%7B%5Cinfty%7D+%281-e%5E%7B-ix%7D%29%5E2&bg=000000&%23038;fg=B0B0B0&%23038;s=0" class="latex"></p>
<p>from which a conservative upper bound on the value of n required for a given bound x⁰ can be derived. The simulation below compares the limiting cdf (in red) with the empirical cdf of the above Δ based on 10⁴ samples of size n=10³.<a rel="nofollow" href="https://xianblog.files.wordpress.com/2018/05/riddler0512.jpg" target="_blank"><img data-orig-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.jpg" data-orig-size="480,480" data-medium-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.jpg?w=300" data-attachment-id="36138" data-image-meta="{" data-image-description="" src="https://xianblog.files.wordpress.com/2018/05/riddler0512.jpg?w=334&h=334&fit=334%2C334&resize=334%2C334" data-permalink="https://xianblog.wordpress.com/2018/05/17/maximal-spacing-around-order-statistics/riddler0512-2/" data-large-file="https://xianblog.files.wordpress.com/2018/05/riddler0512.jpg?w=334&amp;h=334&amp;fit=334%2C334&amp;resize=334%2C334" alt="" data-image-title="riddler0512" sizes="(max-width: 334px) 100vw, 334px" width="334" data-comments-opened="1" class="wp-image-36138" data-recalc-dims="1" height="334"></a>The limiting cdf is the cdf of the maximum of an infinite sequence of independent exponentials with scales 1,½,…. Which connects with the above result, <em>in fine</em>. For a practical application, the 99% quantile of this distribution is 4.71. To achieve a maximum spacing of, say 0.1, with probability 0.99, one would need 2 log(n) > 5.29²/0.1², i.e., log(n)>1402, which is a pretty large number…</p>
<p> </p>
	<p>
<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/2018/05/17/maximal-spacing-around-order-statistics/"> 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 rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/rtlTTqtDyx4" height="1"></a></div>