All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Expected Smaller (Posted on 2014-05-12) Difficulty: 3 of 5
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 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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information