Interesting combinatorics/probability problem

Originally posted by David113
We choose r distinct numbers randomly from the set {1, 2, 3, ..., n}. Prove: the expected value of the smallest chosen number is (n+1)/(r+1).

Just taking an initial stab at this:

One way to find the expected value of the smallest chosen number is to:

1. Count the number of combinations possible given a possible smallest chosen number.

2. Redo the above calculation for every possible smallest chosen number.

3. Multiply each sub-sum by the value of the smallest chosen number.

4. Divide by the total number of choices possible.

For the sake of example, let's let r=3. We start the count by including 1 in our trio of numbers, and then finding out how many combinations include the number 1. This is simply COMBIN(n-1,2) because 2 other numbers must be chosen from the remaining n-1 numbers. We now multiply this value by 1, since that is the smallest chosen number for this sub-sum.

Moving on to letting 2 be the smallest, the number of combinations is now COMBIN(n-2,2) because there are only n-2 numbers left to chose our remaining 2 numbers from. We now multiply this value by 2. In general terms, the sub-sums take the form k*COMBIN(n-k,r-1). The total number of combinations possible is simply COMBIN(n,r), so our expression becomes:

E(n,r) = SUM[k|1...(n-r+1)] k*COMBIN(n-k,r-1) / COMBIN(n,r)

where E(n,r) is the expected value of the smallest chosen number as a function of n and r. I still have to expand this expression and simplify, but I think the answer should pop out after a bit of algebra. I'll tackle it when I have a bit more time.

Anyone see anything wrong with this analysis so far? I usually make at least one in the early stages. 😳