fast track & slow lane

A riddle from the Riddler where N cars going at random (iid) speeds drive a road with a slow and a fast lane, each car choosing the fast lane iff any of the cars ahead in the slow lane is slowerthan them. With the question of the average number of car convoys.

If there were one single lane, the problem would be to determine how many times a smaller realisation and it has been solved in a much older Riddler. Namely

In the two-lane system, the slow one only gathers cars with speeds lowest than the current speed, i.e. a decreasing sequence of speeds, creating single car convoys.  The fast lane thus captures cars that are above the current minimum in the sequence, which, as it converges to the global minimum at some points, means that all following cars are found in the fast lane. i thought this would bring the number of convoys close to twice the above logarithmic sum (which sealed my destiny during an entrance oral exam 40 years ago!), but there are actually more of them for N large enough , which may be due to the possibility of the slow lane to capture more moderate speed cars in the beginning… The above compares the number of convoys for one lane (in red) and two (in gold), as well as the remarkable fit when regressing these numbers against log(N).

Here is the R code I used for that simulation

convoy=function(N,T=1e5){
  for(t in 1:T){
    speed=runif(N)
    slow=fast=NULL
    slow=speed[1]
    for(i in 2:N){
      if(speed[i]<min(slow))slow=c(slow,speed[i]) 
      else fast=c(fast,speed[i])} 
    F=F+length(slow) 
    if(length(fast)>0)F=F+1+sum(fast[-1]<cummin(fast)[-length(fast)])}
  return(F/T)}

self-avoiding random angles

An apparently easy riddle from The Riddler this week: given N random half-lines starting from a N-S segment, what is the probability that none ever intersect? If m ½-lines are on the same side of the segment, they will not intersect when their angle with the segment is decreasing with the longitude of the endpoint of this ½-line on the segment. Assuming that drawing a ½-line at random is akin to uniformely drawing an angle on (0,π), this no X’ing event happens when the m angles are properly ordered, a 1/m! event. Independently, the probability for the segments on the other side is 1/(N-m)! The joint probability is thus

max vs. min

Another intriguing question on X validated (about an exercise in Jun Shao’s book) that made me realise a basic fact about exponential distributions. When considering two Exponential random variables X and Y with possibly different parameters λ and μ,  Z⁺=max{X,Y} is dependent on the event X>Y while Z⁻=min{X,Y} is not (and distributed as an Exponential variate with parameter λ+μ.) Furthermore, Z⁺ is distributed from a signed mixture

conditionally on the event X>Y, meaning that there is no sufficient statistic of fixed dimension when given a sample of n realisations of Z⁺’s along with the indicators of the events X>Y…. This may explain why there exists an unbiased estimator of λ⁻¹-μ⁻¹ in this case and (apparently) not when replacing Z⁺ by Z⁻. (Even though the exercise asks for the UMVUE.)

extinction minus one

The riddle from The Riddler of 19 Feb. is about the Bernoulli Galton-Watson process, where each individual in the population has one or zero descendant with equal probabilities: Starting with a large population os size N, what is the probability that the size of the population on the brink of extinction is equal to one? While it is easy to show that the probability the n-th generation is extinct is

I could not find a way to express the probability to hit one and resorted to brute force simulation, easily coded

for(t in 1:(T<-1e8)){N=Z=1e4 
while(Z>1)Z=rbinom(1,Z,.5)
F=F+Z}
F/T

which produces an approximate probability of 0.7213 or 0.714. The impact of N is quickly vanishing, as expected when the probability to reach 1 in one generation is negligible…

However, when returning to Dauphine after a two-week absence, I presented the problem with my probabilist neighbour François Simenhaus, who immediately pointed out that this probability was more simply seen as the probability that the maximum of N independent geometric rv’s was achieved by a single one among the N. Searching later a reference for that probability, I came across the 1990 paper of Bruss and O’Cinneide, which shows that the probability of uniqueness of the maximum does not converge as N goes to infinity, but rather fluctuates around 0.72135 with logarithmic periodicity. It is only when N=2^n that the sequence converges to 0.721521… This probability actually writes down in closed form as

(which is obvious in retrospect!, albeit containing a typo in the original paper which is missing a ½ factor in equation (17)) and its asymptotic behaviour is not obvious either, as noted by the authors.

On the historical side, and in accordance with Stiegler’s law, the Galton-Watson process should have been called the Bienaymé process! (Bienaymé was a student of Laplace, who successively lost positions for his political idea, before eventually joining Académie des Sciences, and later founding the Société Mathématique de France.)

more breaking sticks

A quick riddle from The Riddler that, when thinned to the actual maths problem, ends up asking for

which is equal to 2/3…. Anticlimactic.