# Ideas to speed up an order statistic calculation?

A toy example:

{n, top} = {25, 100};
mxs = RandomReal[{0, top}, n];

result = Mean[OrderDistribution[dist, n]]


With these parameters this takes many minutes. My actual application will have $$n$$ in the hundreds and $$top$$ in the thousands (though the latter should not have much if any affect).

Ideas to speed this up?

Edit: This seems to do the trick snappily, I'll self-answer with this if no one can beat it.

fn = With[{m = Sort@#, r = Range@Length@#},
Tr[m^Reverse@r/((Last@r - r + 1) (Last@r - r + 2) Append[
Reverse[FoldList[Times, Reverse[Rest@m]]], 1])]] &;


I'm not sure exactly what you're looking for. Anyway, here's an approximation to the mean of the order statistic that takes a second or two to compute on my laptop:

Sort[#][[n]] & /@ RandomVariate[dist, 10^6] // Mean


Of course you could take fewer or more draws depending on the accuracy you want.

• Thanks for this attempt. +1 – ciao Sep 27 at 7:13

The OP edit answer does what I need pretty snappily.

For reference, the function and its usage is

fn = With[{m = Sort@#, r = Range@Length@#},
Tr[m^Reverse@r/((Last@r - r + 1) (Last@r - r + 2) Append[
Reverse[FoldList[Times, Reverse[Rest@m]]], 1])]] &;

fn@maxlist


where $$maxlist$$ is a list of the endpoints (maximums) of your uniform distributions.

For larger $$n$$ cases, the same but in log space can be nearly an order of magnitude faster:

fn2 = With[{m = Log[Sort@#], r = Range@Length@#},
Tr[Exp[m*
Reverse@r - (Log@(Last@r - r + 1) + Log@(Last@r - r + 2) +
Append[Reverse@Accumulate@Reverse@Rest@m, 0])]]] &;


E.G., calculating the millionth order statistic of a million uniform reals with endpoints between 0 and 1000 {n,top}={1*^6,1000} takes a couple of seconds on my laptop, with ~linear time vs $$n$$, compared to the much worse time vs $$n$$ growth of the intrinsic method (reaching a comparable time at $$n$$=16).

Performance comparison ($$Mathematica$$ intrinsic up to $$n$$=25 only): 