 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Expected Smaller (Posted on 2014-05-12) 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.

 No Solution Yet Submitted by Jer No Rating Comments: ( Back to comment list | You must be logged in to post comments.) Solution | Comment 1 of 2

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_(n-1) + 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 2014-05-12 14:44:12 Please log in:

 Search: Search body:
Forums (5)