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).

- Joined
- 25 Aug '06
- Moves
- 0

- Joined
- 14 Feb '04
- Moves
- 28719

False berry12 Sep '08 18:43

Just taking an initial stab at this:*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).**

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. ðŸ˜³- Joined
- 15 Feb '07
- Moves
- 667

13 Sep '08 15:181 editAssuming 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.- Joined
- 15 Feb '07
- Moves
- 667