Randomly select two numbers (not necessarily distinct) from the set
{0, 1/n, 2/n, ..., 1}
What is the expected value, in terms of n, of the smaller of the numbers?
Find the limit of this as n increases without bound.
To keep things simpler, I solved for randomly selecting pairs of integers from the set {0, 1, 2, ..., n} and then I just divided by n at the end.
There are (n + 1)^2 possible permutations of two (not necessarily distinct) integers from this set.
Let k = (2n + 1). Of the possible permutations, note that k of them will have 0 as the smaller of the two values; k  2 of them will have 1 as the smaller of the two values; k  4 of them will have 2 as the smaller of the two values; ... 1 of them will have n as the smaller of the two values.
So we need the sum from i=0 to n of i(2n + 1  2i). I noticed that the first few values of this for n=1,2, 3, 4, ... are 1, 5, 14, 30, 55, 91... and recognized this as a sequence of cumulative sums of squares (5 = 1+4, 14 = 1+4+9, 30 = 1+4+9+16, etc.). So it's a recurrence with a_n = a_(n1) + n^2. I solved this in closed form as (2n^3 + 3n^2 + n)/6.
So that's the numerator of the expected value, and we divide this by (n + 1)^2. Finally we need to divide by n as I mentioned earlier. Simplfying everything, the final expected value is just (2n + 1) / (6n + 6).
The first few values are:
n num den E(X)
1 3 12 0.25
2 5 18 0.277777778
3 7 24 0.291666667
4 9 30 0.3
5 11 36 0.305555556
6 13 42 0.30952381
7 15 48 0.3125
The limit as n goes to infinity is 1/3.

Posted by tomarken
on 20140512 14:44:12 