Mean of a Set of Numbers by Subsets

Date: 08/15/99 at 01:53:54
From: Dave Bartlett
Subject: Mean of a set of numbers

Dear Dr. Math,

Suppose that we have a finite set of numbers. Prove that the mean of 
this set is the mean of the means of all the non-empty subsets of the 
set.

I can see that this is true for some simple examples, e.g. {1, 2, 3}, 
and I can imagine that it is true in general, but I'm not sure how to 
prove it. Could you help?

Dave

Date: 08/17/99 at 11:31:09
From: Doctor Budrow
Subject: Re: Mean of a set of numbers

Hello Dave,

Thanks for writing to Dr. Math.

This is a good problem that illustrates several concepts in 
combinatorics. It is also a good exercise in complicated notation.

To prove your proposition you need to know that:

1) The number of non-empty subsets of a finite set with N elements 
   is 2^N-1.

2) C(N,0) + C(N,1) + ... + C(N,N) = 2^N, where C(N,n) = 
   N!/((N-n)!*n!). So C(N,1) + ... + C(N,N)=2^N-1.

3) (N/n)C(N-1,n-1) = C(N,n).

If you need some help on the above, please write back.


Using the above facts, let's see how to prove your problem. If S is a
set with N numbers, S = {x_1, x_2, ..., x_N}, then it has 2^N-1 
non-empty subsets, say S_1, S_2, ..., S_M, where M = 2^N-1. The mean 
of S is

     (1/N)*(x_1 + x_2 + ... + x_N)

Let mu_i be the mean of subset i so the mean of the subsets is

     (1/M)*(mu_1 + mu_2 + ... + mu_M)

The contribution of x_1 to the mean of S is x_1/N, but what is the 
contribution of x_1 to the mean of the non-empty subsets of S? To 
answer this question, we have to count how many subsets x_1 appears in 
and calculate x_1's contribution to the mean of means for these 
subsets. This is where the notation becomes a little confusing if you 
aren't careful, but let's start counting.

First, there is only one set of size 1 that has x_1 as a member and 
whose mean is just x_1. This means (no pun intended) that for this 
subset, x_1 contributes x_1/M to the mean of means.

Next, there are C(N-1,1) subsets of size 2 that have x_1 as a member, 
so for these subsets x_1 contributes

     C(N-1,1)*(x_1/(2*M))

to the mean of means. To see this, note that if we chose x_1 to be in 
a subset of size 2, there are N-1 elements to choose from for the 
other element. There are C(N-1,1) ways to pick them.

Similarly, there are C(N-1,2) subsets of size 3 that have x_1 as a 
member, so for these subsets x_1 contributes

     C(N-1,2)*(x_1/(3*M))

to the mean of means. To see this, note that if we chose x_1 to be in 
a subset of size 3, there are N-1 elements to choose from for the 
other 2 elements. There are C(N-1,2) ways to pick them.

In general there are C(N-1,n-1) subsets of length n that have x_1 as a 
member. The contribution of x_1 from these subsets to the mean of 
means is

     C(N-1,n-1)*(x_1/(n*M))

Finally, let's add all the contributions of x_1 to the mean of means. 
This sum will be

     (x_1/M)*(1 + C(N-1,1)/2 + C(N-1,2)/3 + ... + C(N-1,N-1)/N)

Let's write this sum as

     (x_1/M)*(C(N-1,0) + C(N-1,1)/2 + ... + C(N-1,N-1)/N)

This is where a trick is needed to put this a form that will almost 
show the result. Multiply this sum by N/N (which is just one) to get

(x_1/(N*M))*((N/1)*C(N-1,0) + (N/2)*C(N-1,1) + ... + (N/N)*C(N-1,N-1))

From (3), this sum becomes

     (x_1/(N*M))*(C(N,1) + C(N,2) + ... + C(N,N))

and from (2) the sum becomes

     (x_1/(N*M))*(2^N-1)=(x_1/(N*M))*M = x_1/N

In other words, the contribution of x_1 to mean of means is exactly 
the same as its contribution to the mean of S.

Since the same argument holds for each of the x_i's, the mean of the 
means is the same as the mean.

You should try this on your example of S = {1,2,3} just to make sure 
you understand the notation, which you see can get quite involved.

If you need more, please write back.

- Doctor Budrow, The Math Forum
  http://mathforum.org/dr.math/