返回题库

抽样的不同数个数

Distinct Number Draws

专题
Probability / 概率
难度
L6

题目详情

从集合 {1,2,…,n}\{1,2,\dots,n\} 中进行有放回抽样，独立均匀地抽取 nn 次。

问：抽到的不同数值的期望个数是多少？

提示：指示变量 + 期望线性性。

Given the set of numbers from 1 to n: { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?

Hint

Linearity of expectation

解析

令 SiS_i 指示数 ii 是否至少出现一次，则

E[Si]=1−P(i 从未被抽到)=1−(1−1n)n.E[S_i]=1-P(i\text{ 从未被抽到})=1-\left(1-\frac1n\right)^n.

不同值总数 S=∑i=1nSiS=\sum_{i=1}^n S_i，因此

E[S]=n(1−(1−1n)n).E[S]=n\left(1-\left(1-\frac1n\right)^n\right).

Original Explanation

E(n) = n[1-(1-1/n)^n]

Solution

Notice that number of distinct points in the produced set is same as number of distinct points selected from the given set {1..n} . For that we denote indicator function Si, that is, Si = 1 if the interger i is taken into produced set.

Let S denote the number of distinct points selected, S = S1+..+Sn E(S) = E(S1) +...+ E(Sn) and E(Si) = 1 * P(Si) = 1 - (Probability that 'i' is not chosen in any draw)

= 1 - ( Prob that is i is not chosen in one 1st draw)^n = 1 - ( 1 - 1/n )^n

Thus E(S) = n * ( 1 - ( (n-1) / n)^n )