z****n
发帖数: 17 | 1 There is a bag with N balls numbered 1,...,N.
You pick out k balls, X_1, ..., X_k without replacement. What is the expected value of the
maximum, E[max X_i, 1<=i<=k] ? | p*****k
发帖数: 318 | | z****n
发帖数: 17 | 3 I approached this question in a brute force way... compute the probability
of max(x1--xk) =m.. then compute the expectation.. it turns out that it's
too hard to compute the expectation..
Can you give us some hints.. ? | c******r
发帖数: 300 | 4 For r.v. taking non-negative integer values
EX = P(X>0) + P(X>1) + ...
Note
P(max X_i > m) = 1 - P(max X_i <= m) = 1 - C_m^k / C_N^k (for m>=k) and 1
for m < k, we have
E(max X_i) = N + 1 - (C_k^k + C_{k+1}^k + ... + C_N^k) / C_N^k
= N + 1 - C_{N+1}^{k+1} / C_N^k
=N + 1 - (N+1)/(k+1) = k*(N+1) / (k+1)
expected value of the
【在 z****n 的大作中提到】
: There is a bag with N balls numbered 1,...,N.
: You pick out k balls, X_1, ..., X_k without replacement. What is the expected value of the
: maximum, E[max X_i, 1<=i<=k] ?
| c******r
发帖数: 300 | 5 or use induction on N
for N = k, the result is clearly N
otherwise, you have the recursion
f(N) = (k/N) * N + (1 - k/N) * f(N-1)
by conditioning on whether the largest ball is N or not.
Solving the recursion gives you
k(N+1)/(k+1) again.
expected value of the
【在 z****n 的大作中提到】
: There is a bag with N balls numbered 1,...,N.
: You pick out k balls, X_1, ..., X_k without replacement. What is the expected value of the
: maximum, E[max X_i, 1<=i<=k] ?
| z****n
发帖数: 17 | 6 给解释一下.. 谢谢
C_k^k + C_{k+1}^k + ... + C_N^k) == C_{N+1}^{k+1} | z****n
发帖数: 17 | |
|
