6
$\begingroup$

A toy example:

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

dist = UniformDistribution[Thread[{0, mxs}]];
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])]] &;
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this attempt. +1 $\endgroup$ – ciao Sep 27 at 7:13
2
$\begingroup$

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):

enter image description here

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.