who’s that travelling salesman path?!

Asher’s enigma

On his Probability and statistics blog, Matt Asher put a funny question (with my rephrasing):

Take a unit square. Now pick two spots at random along the perimeter, uniformly. For each of these two locations, pick another random point from one of the three other sides of the square and draw the segment. What is the probability the two segments intersect? And what is the distribution for the intersection points?

The (my) intuition for the first question was 1/2, but a quick computation led to another answer. The key to the computation is to distinguish whether or not both segments share one side of the square. They do with probability

in which case they intersect with probability 1/2. They occupy the four sides with probability 1/6, in which case they intersect with probability 1/3. So the final answer is 17/36 (as posted by several readers and empirically found by Matt). The second question is much more tricky: the histogram of the distribution of the coordinates is peaked towards the boundaries, thus reminding me of an arc-sine distribution, but there is a bump in the middle as well. Computing the coordinates of the intersection depending on the respective positions of the endpoints of both segments and simulating those distributions led me to histograms that looked either like beta B(a,a) distributions, or like beta B(1,a) distributions, or like beta B(a,1) distributions… Not exactly, though. So not even a mixture of beta distributions is enough to explain the distribution of the intersection points… For instance, the intersection points corresponding to segments were both segments start from the same side and end up in the opposite side are distributed as

where all u‘s are uniform on (0,1) and under the constraint . The following graph shows how well a beta distribution fits in that case. (Not perfectly, though!)
The R code is

u=matrix(runif(4*10^5),ncol=4)
u[,c(1,3)]=t(apply(u[,c(1,3)],1,sort))
u[,c(2,4)]=-t(apply(-u[,c(2,4)],1,sort))
y=(u[,1]*(u[,4]-u[,3])-u[,3]*(u[,2]-u[,1]))/(u[,1]+u[,4]-u[,2]-u[,3])

Similarly, if the two segments start from the same side but end up on different sides, the distribution of one coordinate is given by

under the constraint . The outcome is once again almost distributed as a beta:
The corresponding R code is

u=matrix(runif(4*10^5),ncol=4)
u[,c(1,3)]=-t(apply(-u[,c(1,3)],1,sort))
y=(u[,1]*(1-u[,3])-u[,3]*u[,4]*(u[,2]-u[,1]))/(1-u[,3]-u[,4]*(u[,2]-u[,1]))

Le Monde rank test (corr’d)

Since my first representation of the rank statistic as paired was incorrect, here is the histogram produced by the simulation

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

when . It is obviously much closer to zero than previously.

An interesting change is that the regression of the log-mean on produces

> lm(log(memean)~log(enn))
Call:
lm(formula = log(memean) ~ log(enn))
Coefficients:
(Intercept)     log(enn)
 -1.162        1.499

meaning that the mean is in rather than in or :

> summary(lm(memean~eth-1))
Coefficients:
      Estimate Std. Error t value Pr(>|t|)
eth 0.3117990  0.0002719    1147   <2e-16 ***

with a very good fit.

Le Monde rank test

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,

where the difference between the ranks of the paired random variables and 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 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 against the covariates and , I obtain the uninspiring formula

which does not translate into a nice polynomial in !

Another interesting probabilistic/combinatorial problem issued from an earlier Le Monde puzzle: given an urn with white balls and black balls that is sampled without replacement, what is the probability that there exists a sequence of length with the same number of white and black balls for ? If , the answer is obviously one (1), but for some values of , it is less than one. When goes to infinity, this is somehow related to the probability that a Brownian bridge crosses the axis in-between and but I have no clue whether this helps or not! Robin Ryder solved the question for the values and 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

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

and ,

such that

is a multiple of .

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

and then the a next solution is (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

such that

Hence, solving the second degree equation,

which implies that

is one of the integral factors of . If we write

with

we get

and thus

.

We thus deduce that is an integer, meaning that and thus that is an integer factor of . This obviously restricts the choice of , especially when considering that implies . Furthermore, the solutions to the second degree equations are then given by

.

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

,

,

,

,

,

,

,

we see (without any R programming) that is the smallest solution (in ). is the smallest solution with a possible solution in ( 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 implies that and share a largest common divider , i.e.

which implies

,

thus that divides (because both other terms are prime with ). Eliminating dividers common to and actually leads to , hence to the same conclusion as before.