1
$\begingroup$

Let $L=\{a_1,a_2,\ldots,a_k\}$ be a random (uniformly chosen) subset of length $k$ of the numbers $\{1,2,\ldots,n\}$. I want to find $E(X)$ where $X$ is the random variable that sums all numbers. We might want that $k < n$ too.

My main problem is that I cannot get the function $q(a,k,n)$ that gives me the number of ways to write the number $a$ as the sum of exactly $k$ distinct addends less or equal $n$. This seems related but it doesn't limit the size of the numbers.

$\endgroup$

2 Answers 2

5
$\begingroup$

The expectation of each of the terms in the sum is $(n+1)/2$ so the expectation is $k(n+1)/2$.

If you want to calculate the function $q(a,k,n)$ then you can use my Java applet here, by choosing "Partitions with distinct terms of:" $a$, "Exact number of terms:"$k$, "Each term no more than:" $n$, and then click on the "Calculate" button. If instead you start with "Compositions with distinct terms of:", then you will get a figure $k!$ times as big.

$\endgroup$
1
  • $\begingroup$ Thanks, I accepted this one because I think your great applet can be useful for me on later tasks too :) $\endgroup$
    – Listing
    Commented May 7, 2011 at 13:49
2
$\begingroup$

Hint: (1) Compute $E(a_1)$. (2) Show that $E(a_k)=E(a_1)$ for every $k$. (3) Deduce $E(X)$.

This is a good example where computing the distribution is messy but computing the expectation is easy.

$\endgroup$
1
  • $\begingroup$ Thank you! Too bad I cannot accept two answers as both answers together answer my questions completely :) $\endgroup$
    – Listing
    Commented May 7, 2011 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .