Adding order statistics sampling

[severinson]

Hello,

I've implemented sampling from the order statistics of an arbitrary sampleable. Are you interested in merging this kind of functionality into Distributions.jl?

The k-th order statistic is the k-th smallest value out of n (n >= k) variables. I'm using order statistics to model latency in distributed computing (the overall latency is the n-th order statistic of the latency of the n workers). Finding the distribution of the order statistics is often non-trivial. An implementation like this is a useful fallback.

I'm attaching a prototype implementation.

struct OrderStatistic{S<:Union{Discrete,Continuous},Spl<:Sampleable{Univariate,S},T} <: Sampleable{Univariate,S}
    spl::Spl
    k::Int
    buffer::Vector{T}
end

Base.show(io::IO, s::OrderStatistic) = print(io, "OrderStatistic($(s.spl), k=$(s.k), n=$(length(s.buffer)))")

OrderStatistic(s::Sampleable, k::Integer, n::Integer) = OrderStatistic(s, k, Vector{eltype(s)}(undef, n))

function rand(rng::AbstractRNG, s::OrderStatistic)
    Distributions.rand!(rng, s.spl, s.buffer)
    partialsort!(s.buffer, s.k)
    s.buffer[s.k]
end

[oschulz]

CC @LolianSh , this may interest you.