Mean of a Set of Numbers by SubsetsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/