Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  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. Standard member PBE6
    Bananarama
    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:18 / 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.
  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..