Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been trying to figure out how to determine the probability distribution function for the sum of $N$ values taken from a set of $K$ consecutive values (valued $1$ to $K$).

For example, if I choose at random 5 values from a set of 50 for a trial and sum the results, I get a value I'll call $S$. If I do that for a million trials and look at the distribution of $S$, it will be a bell-curved distribution, but I don't know how to calculate the mean, median, standard deviation, etc.

I also understand that:

  • There are $\frac{50!}{(50-5)!} = 254,251,200$ permutations.
  • The smallest sum is $1+2+3+4+5=15$ and the largest sum is $46+47+48+49+50=240$.

I just can't figure out how to derive a formula to determine how many permutations (or maybe combinations if order doesn't matter?) sum up to a given value $S$ between $15$ and $240$.

share|improve this question
    
    
When you "choose at random 5 values from a set of 50", are you choosing distinct values or allowing for duplicates? I.e., are you sampling with or without replacement? –  awkward Jul 7 '13 at 0:55
    
The values are distinct...like choosing 5 of 50 lottery balls or something, numbered 1 to 50. Forgive me, I think that is called "without replacement". I'm a bit of a novice at statistics. –  mitselplik Jul 7 '13 at 17:08

2 Answers 2

Since the sum of Gaussian variables is Gaussian, you only need to find two parameters: the mean and the standard deviation. The mean is easy, due to linearity of expectation. Let's call it $\mu$.

The standard deviation is trickier. If $\frac{k}{n}$ is large, you can get an easy approximation by ignoring the fact that the values have to be distinct. In this case, just use the fact that the standard deviation scales like $\sqrt{n}$.

If you need an exact formula, you will have to compute the variance: $$-\mu^2+\sum_{|S|=N}\left(\sum_{x\in S}x\right)^2$$over all sets $S$ containing your elements.

share|improve this answer

So it turns out that the solution to this problem is non-trivial. After further analysis, I've determined that the "distribution" scales to a bell curve that can be obtained by simply counting the sums of all possible permutations of N values from the set of integers from 1 to K.

Facts/Discoveries:

  • There are $N(K - N) + 1$ sums.
  • The smallest sum $S$min = $\frac N 2$×$($N $+$ 1$)$.
  • The largest sum $S$max = $\frac N 2$×$($2K - N + 1$)$.
  • Given $S$ ∈ {$S$min, ... , $S$max}, then $count(S) = N!×p(S)$, where $p(S)$ is a strict partitioning function of $S$ such that all summands are unique and ≥ 1.
  • Further Research:
    Thus far, I have yet to find a straight-forward formula for $p(S)$ (or perhaps $p(S, K, N)$ since the function domain changes with different values of $K$ and $N$).

    The question is essentially equivalent to asking "How many ways can a flight of $K$ stairs be climbed, taking at least 1 stair at a time, never repeating the number of stairs previously taken, and moving exactly $N$ times?"

    Once I (or perhaps smarter minds than I) have figured out a way to calculate $p(S, K, N)$, then I will need to determine how to scale the "distribution" based on the number of trials. I am not sure that it would be linear.

    Assuming anyone else is interested in this problem, I generated the set of counts for $K = 10, N = 5$ below:
    {120,120,240,360,600,840,1080,1320,1680,1920,2160,2280,2400,2400,2280,2160,1920,1680,1320, 1080,840,600,360,240,120,120}

    Factoring out $5!$ yields:
    {1,1,2,3,5,7,9,11,14,16,18,19,20,20,19,18,16,14,11,9,7,5,3,2,1,1}

    share|improve this answer

    Your Answer

     
    discard

    By posting your answer, you agree to the privacy policy and terms of service.

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