Let's say you have a set of order statistics $ X_{(1)}, \dots, X_{(N)} $ drawn from a discrete uniform distribution $ \text{unif}(1,S) $. If you choose $ X_{(n_1)}, \dots, X_{(n_k)} $ from this set, how would you find the distribution $ Y = \sum_{j=1}^k X_{(n_k)} $?

As an example to make it clearer, I've been trying to develop a tabletop RPG system and I'm thinking that the player could level up their stats in a few different ways. One way I'm imagining is that players can roll--for example--4 d6's and then must start off with $ X_{(1)} + X_{(2)} $, then being able to upgrade to something like $ X_{(2)} + X_{(3)} $. I'd like to work this out in general to see if it's balanced, but given that $ X_{(1)}, \dots, X_{(k)} $ are not i.i.d., this has been difficult.


I have still been considering this question, and I've been able to make some slight progress by considering a transformation of the sample space. In particular, let

$$ S = \{ X \in \textbf{N}^K : 1 \leq X_1 \leq \dots \leq X_K \leq T \} $$

If $ m_Y(r) $ counts the multiplicity of $ r $ in the vector $ Y $ (e.g., $ m_{(1,3,3)}(3) = 2 $), the p.m.f. of this distribution is,

$$ f(Y) = \frac{1}{T^K} \binom{K}{m_Y(1), \dots, m_Y(T)} $$

Questions about order statistics from the original distribution then become questions about the marginal probabilities of a given index. E.g., something like $ \Pr(X^{(1)} = 2) $ becomes $ \Pr(Y_2 = 2) $. Then the marginal distribution of $ Y_i $ is

$$ f_{Y_i}(z) = \sum_{\substack{y \in S\\ y_i = z}} f(y) $$

This helps a bit, and it's more of an answer I had initially, but if there's a way of simplifying this sum I have been unable to find it.

  • 1
    $\begingroup$ What information would you need to decide if it's "balanced"? Or is that more a general impression from looking at the distributions? $\endgroup$ – Glen_b -Reinstate Monica Oct 17 '15 at 22:53
  • $\begingroup$ It'll probably be about 50/50 between calculations and what feels right as I move on. I know I could just write a program to bruteforce the results, but a formula (even if not closed form) would be nice, and I'm now curious about the solution. $\endgroup$ – Tim Reilly Oct 17 '15 at 23:12

Can you get what you want from the expectations? From "Tables of Moments of Sample Extremes of Order Statistics from Discrete Uniform Distribution," by Turan, Calik, and Gurcan (available at https://openaccess.firat.edu.tr/xmlui/bitstream/handle/11508/8469/ATuran.pdf?sequence=1) I found for a sample of size $n=4$ that $$E[X_{(1)}]={ { \left( 6S^4+15S^3+10S^2-1 \right)} \over {30S^3}}$$ and $$E[X_{(4)}]={ { \left( 24S^4+15S^3-10S^2+1 \right) } \over {30S^3}}$$ I couldn't find any published formulas for the intermediate order statistics, but the 4 six-sided dice example is small enough to do by enumeration. This confirms the 4 expectations are $$E[X_{(1)}]={{2275} \over {1296}}=1.7554$$ $$E[X_{(2)}]={{3759} \over {1296}}=2.9005$$ $$E[X_{(3)}]={{5313} \over {1296}}=4.0995$$ $$E[X_{(4)}]={{6797} \over {1296}}=5.2446$$

  • $\begingroup$ This is certainly a step towards something. I'll mark it as the accepted answer unless someone finds something more explicit. $\endgroup$ – Tim Reilly Oct 26 '15 at 21:18

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.