|
|
一开始我一直顺着原文的叙述试图理解概率为何为1/(k+1), 很困惑。谢谢数值分析坛友的提醒,终于想明白了。下面试着用同一思路但不同的语言叙述一下,作为总结。. u1 q3 I, w7 s6 M9 J! S4 `
- w, G, m" d2 t5 G
Let S be the set of the n elements in which there are k and only k elements that have value x. For each element w, let I be the indicator if w is examined or not, that is, I(w) = 1 if w is examined and 0 if w is not examined. X, the number of elements being examined, will be the sum of I(w) for all w in S. Accordingly, E[X] will be the sum of E[I(w)]=P{I(w)=1}.
- T8 ^! N D: f9 j$ R' Y% @) F: [" C* L8 y, `5 a" _1 y7 l1 e8 W7 O
For w that has a value x, the chance of w being examined is the chance that w is at the first position of a permutation of k x-valued elements. Therefore it's 1/k.% \; U- e8 h! q. V
% M: H' ^' g. ]1 k3 O0 x
For w that has a value not being x, the chance of x being examined is the chance that w is at the first position of a permutation of all k x-valued elements plus w. Therefore it's 1/(k+1).
7 B8 f+ T$ S! R6 ~0 A+ \& C
' W% A) h* x, e- H) W0 h k4 ~! qThere are k elements that have value x and n-k elements that are not equal to x, so the sum of all these probabilities will be k*(1/k) + (n-k)*(1/(k+1)) = (n+1)/(k+1)./ n9 P q/ i, U9 [9 c1 d5 {+ ^. s* Z* L
9 O _! {2 h7 o: `- |, Q* |
理解上述解法的一个关键点是对于所有不等于x的element,它能不能有机会被查验取决于而且只取决于它与k个值为x的elements的相对位置。 |
评分
-
查看全部评分
|