Archive for order statistics
slice sampling, of course!
Posted in Books, pictures, Statistics with tags cross validated, log-normal distribution, MCMC algorithms, Metropolis-Hastings algorithms, order statistics, simulation, slice sampling, Stack Exchange on November 19, 2024 by xi'an
inference with insufficient statistics #2
Posted in Books, Kids, Statistics with tags conditional sufficiency, cross validated, EM algorithm, Gibbs sampler, implementation, incomplete data, order statistics, truncated normal on December 28, 2023 by xi'an
Another X validated question of some interest: how to infer about the parameters of a model when only given a fraction 1-α of the order statistics. For instance, the (1-α)n largest observations. On a primary level, the answer is somewhat obvious since the joint density of these observations is available in closed form. At another level, it brings out the fact that the distribution of the unobserved part of the sample given the observed one only depends on the smallest observed order statistic ς (which is thus sufficient in that sense) and ends up being the original distribution truncated at ς, which allows for a closed form EM implementation. Which is also interesting given that the moments of a Normal order statistic are not available in closed form. This reminded me of the insufficient Gibbs paper we wrote with Antoine and Robin a few months ago, except for the available likelihood. And provided fodder for the final exam of my introductory mathematical statistics course at Paris Dauphine.
simulating the maximum of Rayleigh variates
Posted in Books, Statistics, University life with tags beta distribution, chi distribution, John Strutt, Lord Raleigh, Nobel Prize, order statistics, random simulation, Rayleigh distribution on December 26, 2023 by xi'an
An X validated question on an efficient way to simulate the largest order statistics of a Rayleigh (large) sample. Named after the 1904 Nobel recipient, John Strutt. This is not a commonly used distribution in statistics, since it coincides with the χ2 distribution. Anyway, thanks to its compact, closed form cdf, the largest order statistics can be directly simulated, at a constant cost in the sample size, as
or equivalently as
since the smallest order statistic from a Uniform sample, U(1), is distributed from a Be(1,N) distribution.
simulated annealing and logistic regression to the max
Posted in Kids, R, Statistics with tags guessing game, logistic regression, mathematical puzzle, order statistics, R, simulated annealing, The Riddler on April 26, 2023 by xi'anA Riddler puzzle on the three binary and sequential questions one should ask three players hiding their respective U(0,1) realisation, U, V, and W, to best guess which player holds the largest number, max{U,V,W}. Assuming questions of the type Is U<b¹, &tc., the challenge boils down to selecting seven bounds (one for U, two for V, and four for W) in order to optimise the probability of picking the right player. Which means for a given collection of such bounds to learn this probability from the three binary answers. These can be turned into eight (2³) binary variables and I used them as entries in a logistic regression to predict that W was larger than max(U,V), itself predicted by the first two answers. The optimisation of the bounds can then be achieved by simulated annealing (or otherwise) and the approach returns (random) outputs like the following bounds (one on U, two on V, and four on W)
0.616 0.434 0.830 0.350 0.736 0.913 0.796 0.827
for an estimated probability of 0.827. This is a somewhat coherent sequence of bounds when considering the simpler case of two players. Indeed, with three bounds, the probability of winning can be readily derived as
logically optimised by (b¹,b²,b³)=(1/2,1/4,3/4) for a success probability of 0.875. And it coïncides with the solution posted by The Riddler, although there is no intuition behind the figures, contrary to the two player situation. In fact, I am surprised that the bound on W does not equate the expectation of max{U,V} under the current conditions:
> x=runif(1e6,0,.616);y=runif(1e6,0,.434) > mean(y+(x-y>0)*(x-y)) [1] 0.3591648
fast track & slow lane
Posted in Books, Kids, R, Statistics with tags grandes écoles, oral exam, order statistics, riddle, The Riddler on September 3, 2022 by xi'an
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)}
