## Le Monde rank test

Posted in R, Statistics with tags , , , , , , , , on April 5, 2010 by xi'an

In the puzzle found in Le Monde of this weekend, the mathematical object behind the silly story is defined as a pseudo-Spearman rank correlation test statistic,

$\mathfrak{M}_n = \sum_{i=1}^n |r^x_i-r^y_i|\,,$

where the difference between the ranks of the paired random variables $x_i$ and $y_i$ is in absolute value instead of being squared as in the Spearman rank test statistic. I don’t know whether or not this measure of distance has been studied in the statistics literature (although I’d be surprised has it not been studied!). Here is an histogram of the distribution of the new statistics for $n=20$ under the null hypothesis that both samples are uncorrelated (i.e. that the sequence of ranks is a random permutation). Each point in the sample was obtained by

perm=sample(1:20)
saple[t]=sum(abs(perm[1:10]-perm[11:20]))

When regressing the mean of this statistic $\mathfrak{M}_n$ against the covariates $n$ and $n^2$, I obtain the uninspiring formula

$\mathbb{E} [\mathfrak{M}_n] \approx 0.1681 n^2 - 0.3769 n + 11.1921$

which does not translate into a nice polynomial in $n$!

Another interesting probabilistic/combinatorial problem issued from an earlier Le Monde puzzle: given an urn with $n$ white balls and $n$ black balls that is sampled without replacement, what is the probability that there exists a sequence of length $2k$ with the same number of white and black balls for $k=1,\ldots,n$? If $k=1,n$, the answer is obviously one (1), but for some values of $k$, it is less than one. When $n$ goes to infinity, this is somehow related to the probability that a Brownian bridge crosses the axis in-between $0$ and $1$ but I have no clue whether this helps or not! Robin Ryder solved the question for the values $n=50$ and $k=24,25$ by establishing that the probability is still one.

Ps- The same math tribune in Le Monde coincidently advertises a book, Le Mythe Climatique, by Benoît Rittaud that adresses … climate change issues and the “statistical mistakes made by climatologists”. The interesting point (if any) is that Benoît Rittaud is a “mathematician not a statistician”, with a few papers in ergodic theory, but this advocated climatoskeptic nonetheless criticises the use of both statistical and simulation tools in climate modeling. (“Simulation has only been around for a few dozen years, a very short span in the history of sciences. The climate debate may be an opportunity to reassess the role of simulation in the scientific process.”)

## New Le Monde puzzle

Posted in Kids, R with tags , on March 4, 2010 by xi'an

When I first read Le Monde puzzle this weekend, I though it was even less exciting than the previous one: find

$Y>2010$ and $N<(Y-N)$,

such that

$N(Y-N)$ is a multiple of $Y$.

The solution is obtained by brute-force checking through an R program:

$Y=2012, N=1006$

and then the a next solution is $Y=2016, N=504$ (with several values for N).

However, while waiting in the plane to Edinburgh, I thought more about it and found that the problem can be solved with paper and pencil. It goes like this. There exists an integer

$c$ such that $N(Y-N)=cY.$

Hence, solving the second degree equation,

$N = \left(Y\pm\sqrt{Y^2-4cY}\right)/2 = Y \left(1\pm\sqrt{1-4c/Y}\right)/2$

which implies that

$2 / \left(1\pm\sqrt{1-4c/Y}\right)$

is one of the integral factors of $Y$. If we write

$Y=qk$ with $1\pm\sqrt{1-4c/Y}= \dfrac{2}{k},$

we get

$\dfrac{4c}{Y} = \dfrac{4c}{qk} = 1 - \left( 1 - \dfrac{2}{k}\right)^2 = \frac{4}{k}\left(1-\dfrac{1}{k}\right)$

and thus

$c=q-\dfrac{q}{k} = q\,\dfrac{k-1}{k}$.

We thus deduce that $q/k$ is an integer, meaning that $q=pk$ and thus that $k^2$ is an integer factor of $Y$. This obviously restricts the choice of $Y$, especially when considering that $4c\le Y$ implies $k\ge 4$. Furthermore, the solutions to the second degree equations are then given by

$\dfrac{Y}{2} \left( 1 \pm \dfrac{k-2}{k}\right) = \left\{ \begin{matrix} pk\\ pk(k-1)\end{matrix}\right.$.

The conclusion is thus that any $Y$ which can be divided by a squared integer larger than or equal to $4^2$ provides a solution. Now, if we look at the decomposition of

$2010=2\times 3\times 5\times 67$,

$2011=2011\times 1$,

$2012=2^4\times 503$,

$2013=3\times 11\times 61$,

$2014=2\times 19\times 53$,

$2015=5\times 13\times 31$,

$2016=2^5\times 3^2\times 7$,

we see (without any R programming) that $(Y,N)=(2016,504)$ is the smallest solution (in $Y$). $Y=2016$ is the smallest solution with $N=504$ a possible solution in $N$ ($N=168$ being another one). Which makes (at least) for a more bearable diversion in the plane…

An approach avoiding the second degree equation is to notice that $N(Y-N)=cY$ implies that $N$ and $Y$ share a largest common divider $h>1$, i.e.

$Y=hY^\prime\,,\quad N=hN^\prime$

which implies

$N^\prime(Y^\prime-N^\prime)h=cY^\prime$,

thus that $Y^\prime$ divides $k$ (because both other terms are prime with $Y^\prime$). Eliminating dividers common to $c$ and $N^\prime$ actually leads to $Y^\prime=k$, hence to the same conclusion as before.

## Le Monde puzzle

Posted in Statistics with tags , on February 21, 2010 by xi'an

The puzzle in Le Monde is quite straightforward (!) this weekend: it can be rewritten as to figure out the values of the sums

$10! \displaystyle{\left.\left\{1 - \sum_{j_1=1}^{10} \frac{1}{j_1}\left\{1-\sum_{\stackrel{j_2=1}{j_2\ne j_1}}^{10}\frac{1}{j_2}\right\{1-\ldots\right.\right.}$

$\displaystyle{\qquad\ldots\left.\left.\left.\left\{1-\sum_{\stackrel{j_9=1}{j_9\ne j_1,\ldots,j_8}}^{10} \frac{1}{j_9}\right\}\ldots\right\}\right\}\right\}}$

and

$\displaystyle{\left.(49!)^2 \left\{1 - \sum_{j_1=1}^{49} \frac{1}{j_1^2}\left\{1-\sum_{\stackrel{j_2=1}{j_2\ne j_1}}^{49}\frac{1}{j_2^2}\right\{1-\ldots\qquad\right.\right.}$

$\displaystyle{\qquad\ldots\left.\left.\left.\left\{1-\sum_{\stackrel{j_{48}=1}{j_{48}\ne j_1,\ldots,j_{47}}}^{49} \frac{1}{j_{48}^2}\right\}\ldots\right\}\right\}\right\}}$

which are easily displayed and as easily solved.

The first sum can indeed be written as

$\displaystyle{\sum_{i=1}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u}$

for $k=10$. This is simply

$\displaystyle{\sum_{i=0}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u}- (-1)^k = \prod_{i=1}^k (i-1) - (-1)^k$

and the solution is thus $(-1)^{k+1}$, equal to -1 for $k=10$. Once we realise the fact this is a product with one missing term, the second sum is similar: it can be written as

$\displaystyle{\sum_{i=0}^k (-1)^{k-i} \sum_{\stackrel{j_1\ne\cdots\ne j_i}{\in\{1,\ldots,k\}}} \prod_{u=1}^i j_u^2}- (-1)^k$

$\qquad = \prod_{i=1}^k (i^2-1) - (-1)^k = - (-1)^k$

This is equal to 1 for $k=49$. A bit disappointing because it amounts to reformulate the question with the proper algebraic formula…