Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I pick $k$ integers without replacement from $\{1, \ldots, n\}$. Let $I$ be the value of the highest integer. A calculation with binomials reveals $$E[I] = \frac{k}{k+1}(n+1)$$ This is a very simple formula - does it have a simple calculation-free proof?

share|improve this question
    
Do you know some instance of calculation-free proof for the expected value of some non-constant random variable? I would like to see it. –  Matemáticos Chibchas Feb 7 '13 at 8:22
    
In many cases, you can use symmetry or some clever conditioning to avoid heavy calculations. –  pierre Feb 7 '13 at 8:33
    
You just said it: "heavy" calculations. This is OK, but no calculations at all? Besides, I agree that conditioning is clever, but it is based on the nontrivial subject of conditional expectation. –  Matemáticos Chibchas Feb 7 '13 at 9:04
    
@MatemáticosChibchas - the answer by Henry below is what I would call calculation-free. –  pierre Feb 8 '13 at 23:42
add comment

1 Answer

up vote 4 down vote accepted

Picking $k$ integers without replacement from $\{1, \ldots ,n\}$ involves breaking the interval $[0,n+1]$ into $k+1$ pieces where the length of each piece has the same distribution.

So the expected length of each piece (including the piece from the highest sampled integer to $n+1$) is $\dfrac{n+1}{k+1}$ and so the expected value of the highest sampled integer is $n+1 - \dfrac{n+1}{k+1}$.

Simple calculation will give your result.

So in general, the expected value of the $j$th sampled integer (counting from the bottom) is $j \dfrac{n+1}{k+1} $.

share|improve this answer
    
Sorry by my ignorance, but I don't get it: what is the "same distribution" of each piece? (I don't understand the expected length stuff either, but hopefully this will be cleared when I get illuminated about the "same distribution" issue) Thanks. –  Matemáticos Chibchas Feb 7 '13 at 20:08
    
Very nice! But how do you show that are no "edge effects," i.e., that the length of the first piece has the same as the length of the second? –  pierre Feb 7 '13 at 22:04
    
@Matemáticos Chibchas: Each length is a random variable with a distribution. Each of these distributions is the same and has the same mean. –  Henry Feb 8 '13 at 7:35
    
@pierre: Imagine seating $k+1$ people round a table with $n+1$ seats: there are no edge effects in the gaps between people. Then cut the table where the first person sits and straighten it into a bench of length $n+1$. –  Henry Feb 8 '13 at 7:39
    
Lovely. Thank you for this fantastic answer. –  pierre Feb 8 '13 at 23:41
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.