 Interesting combinatorics/probability problem David113 Posers and Puzzles 12 Sep '08 15:54
1. 12 Sep '08 15:54
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).
2. 12 Sep '08 18:43
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. 😳
3. 13 Sep '08 15:181 edit
Assuming you pick R numbers out of the first N ordinals, you can find the number of combinations where X is the smallest chosen via calculated combinatorics.

If X is the smallest, it was chosen, and so you are then deciding on R-1 numbers out of the N-X remaining (all larger), which you arrive at this formula for total number of ways..

(N-X)! / [(R-1)! * (N-X-R+1)!]

In order to obtain the arithmetic mean of the lowest term for all the combinations, You would, for each valid X, sum up the formula multipled by X and divide by the total number of combinations.

This is as far as I have gotten thus far.
4. 14 Sep '08 13:51
Well, tried out a few cases in Excel, and thus far the formula holds.

The tricky thing will be either to simplify the sums of combinations or else bypass them entirely..