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?
Asked
Active
Viewed 741 times
7
-
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 07 '13 at 08:22
-
In many cases, you can use symmetry or some clever conditioning to avoid heavy calculations. – Michael S. Feb 07 '13 at 08: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 07 '13 at 09:04
-
@MatemáticosChibchas - the answer by Henry below is what I would call calculation-free. – Michael S. Feb 08 '13 at 23:42
1 Answers
6
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} $.
Henry
- 157,058
-
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 07 '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? – Michael S. Feb 07 '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 08 '13 at 07: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 08 '13 at 07:39
-
-
@Henry Can you explain me please how one can conclude in an intuitive fashion that the distributions of the lengths are the same? If $X^{(1)}<X^{(2)}<\cdots<X^{(k)}$ are the elements of the $k$-sample, then your claim is that the random variables $X^{(i)}-X^{(i-1)}$, for $i=1,\dots,k$, are equally distributed (here $X^{(k+1)}=n+1$). Of course, this can be proved via calculations, but I would be glad to see an intuitive explanation. – Matemáticos Chibchas Feb 09 '13 at 10:06
-
@Matemáticos Chibchas: see my response to pierre. Initially the distributions are the same because of rotational symmetry. – Henry Feb 09 '13 at 21:02