Take the 2-minute tour ×

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


