Originally posted by David113Just taking an initial stab at this:
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. 😳
1 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.