2
$\begingroup$

Given positive integers $a$ and $b$ ($b \leq a$), where $c$ is the set of all combinations of $a$ digit binary numbers, with $b$ 1's, and where $c_1$ is least significant bit, and $c_a$ is most significant bit,

What is the distribution of all sums, $1(c_1) + 2(c_2) + 3(c_3) + ... + a(c_a)$?

If near normal distribution, how would I calculate the mean and standard deviation from $a$ and $b$?

Example, $a$ = 5, $b$ = 3, then $c$ would be {00111, 01011. 01101, 01110, 10011, 10101, 10110, 11001, 11010, 11100}. For 00111, $c_1$ would be 1, $c_2=1$, and $c_a=c_5=0$. The range of the sums would be from 1(1) + 2(1) + 3(1) + 4(0) + 5(0) = 6 to 1(0) + 2(0) + 3(1) + 4(1) + 5(1) = 12

This is the math model I am using to correlate student score results on exams. I can find minimums and maximums, but am wondering if this is a normal distribution so that I can calculate the mean and standard deviation of this distribution. Another way I could do this is if I can make an algorithm to generate all the possible binary $c$ combinations.

A more accurate, but more complex question would be the distribution of the sums $d_1c_1 + d_2c_2 + ... + d_ac_a$, with $d_1$ to $d_a$ being fixed coefficients, which would be using weighted scores rather than ranks, but that can be another question later. Thanks.

$\endgroup$
9
  • 3
    $\begingroup$ In more conventional language, it appears you are asking for the distribution of the sample sum when taking a $b$-element sample without replacement from the set $\{1,2,\ldots, a\}$ or, generally, from the multiset $(d_1,d_2,\ldots,d_a)$. (Upon dividing by $b$ it would become a question about the sampling distribution of the mean.) This translation of your question makes the answers immediate, because you can apply standard results from sampling theory to draw conclusions about the distribution (it's not Normal, but when $b\ll a$ it will be close to Normal) and its moments. $\endgroup$ – whuber Dec 7 '14 at 2:32
  • $\begingroup$ Hax - what do you precisely mean by "correlate" there? @whuber thanks for the translation - I was having trouble figuring out what Hax was trying to achieve. $\endgroup$ – Glen_b Dec 7 '14 at 3:49
  • 1
    $\begingroup$ @whuber your concise description of my question is exactly what I am looking for, the distribution of the sample sums. If not normal, how can I get information about the distribution and moments, for a given a and b? Where can I find information about standard results from sampling theory to calculate this? My statistics level of knowledge is undergraduate statistic class. The values I am looking at are about 30 for b, and about 15-20 for a. This is small enough that I can generate the entire set, but I would need to write an algorithm to generate all possible samples. $\endgroup$ – Hax Dec 8 '14 at 21:17
  • $\begingroup$ Thank you for the clarification. You might start by looking at some of our threads referring to finite populations. They should contain formulas for estimating means and variances $\endgroup$ – whuber Dec 8 '14 at 21:23
  • $\begingroup$ @Glen_b I use the term "correlate" loosely here and would probably be better to use associate. I tried to narrow down my question to be more specific on what I am looking for, and whuber was very helpful in rephrasing it. Now I just need details on how to calculate this for each specific a and b for both a set of consecutive integers, and if possible, a multiset. $\endgroup$ – Hax Dec 8 '14 at 21:24
3
$\begingroup$

This distribution can be generated using an online calculator and Excel. As an example, suppose we have 19 balls labeled 1-19. Take all combinations of 10 balls and add the numbers on the 10 balls together for each combination. Find the distribution of these sums using the following procedure:

  1. Use the online combination and permutation calculator

entering 19 for n, 10 for r, no for order, no for repetition, numbers enter 1 through 19 in list, select cvs

exporting data to excel

There are 92378 combinations for C(19,10).

  1. In excel calculate the sums for each combination for the data. Use min and max function to determine range

    In this example, it ranges from 55 to 145.

  2. Generate the frequencies using the countif function to get the distribution.

Discrete distribution from Excel 2010

  1. To get the mean, use the average function.

  2. To get the standard deviation, use the stdevpa function.

  3. To get the probability mass function, calculate the probability by frequency/total combinations of each unique sum.

    In our example, probability of 100 is 2934/92378 = 0.031761 rounded.

  4. The mean can also be calculated using the formula

$\mu = \sum x p(x)$, and standard deviation using $\sigma = \sqrt {\sum (x - \mu)^2 p(x)}$

This example has a mean of 100, and standard deviation of 12.24745 rounded.

The distribution in this example is a symmetric unimodal discrete distribution. The referenced online calculator can generate only a maximum of 1,000,000 combinations.

To get formulas for mean and standard deviation in our problem in terms of a and b,

mean of population $ = \frac{\sum\limits_{i=1}^n a_i}{a}$

$$= \frac{a(a+1)}{2} * \frac{1}{a}$$

$$= \frac{(a+1)}{2}$$

mean of sample means $\bar x$ (mean of sampling distribution) is same as population mean so

$\frac{(a+1)}{2}$

mean of sampling distribution of sample sums

$\frac{b(a+1)}{2}$

for the standard deviation of the sampling distribution of sample sums, it is

sample size * standard error mean * finite population correction factor

$b * \frac{\sigma}{\sqrt b} * \frac{(a-b)}{(a-1)}$

in our example using the formulas, mean of the sample sum

$\frac{10(19+1)}{2} = 100$

standard deviation of sample sums =

$10 * \frac{5.47723}{\sqrt{10}} * \frac{19-10}{19-1}$

= 12.24745 rounded

which are the same values we got above with generating the distribution

The distribution is the probability mass function which has no single formula, but can be calculated for each discrete random variable by using variations of dice sum distributions (with replacement) b number of a-sided die, or subset sum (without replacement) specific sized subset calculations for the numerator, and ${{a}\choose{b}}$ for the denominator. The range of the random variables is the integer sequence from $\sum\limits_{i=1}^b x_i$ to $\sum\limits_{i=a-b}^a x_i$.

with replacement, multiple dice sum distributions

http://mathworld.wolfram.com/Dice.html

without replacement, special case of the subset-sum problem in which the number of items in the subset is b

https://mathoverflow.net/questions/101971/subset-sum-problem-when-the-number-of-integers-in-the-sum-is-known

https://math.stackexchange.com/questions/953908/probability-that-the-sum-of-three-integer-numbers-from-1-to-100-is-more-than-1/953950#953950

$\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.