[组合] 一道有关数学期望题目

本帖最后由 dahool 于 2020-4-28 09:58 编辑

有$2019$个人，每个人从集合$\{1,2,\cdots,2019\}$中等概率的挑选一个数，这些数为$a_1,a_2,\cdots,a_{2019}$，令$A$为这些数构成的集合，例如：$a_1=a_2=\cdots=a_{2018}=1,a_{2019}=2$，则$A=\{1,2\}$，求集合$A$的元素个数的数学期望.

分享到: QQ空间 腾讯微博 腾讯朋友

战巡

2^#

发表于 2020-4-28 12:54 | 只看该作者

本帖最后由战巡于 2020-4-28 17:50 编辑

回复 1# dahool

如果令$N$为集合总数（这里$N=2019$，但我们可以探寻更一般的情况），然后令$m_n$为第$n$个人挑选完后构成的集合元素个数

显然有$m_1=1$, $P(m_2=1)=\frac{1}{N}, P(m_2=2)=\frac{N-1}{N}$，然后当给定了$m_n$以后，会有
\[P(m_{n+1}=m_n|m_n)=\frac{m_n}{N}\]
\[P(m_{n+1}=m_n+1|m_n)=\frac{N-m_n}{N}\]
而后
\[E[m_{n+1}|m_n]=P(m_{n+1}=m_n|m_n)m_n+P(m_{n+1}=m_n+1|m_n)(m_n+1)\]
\[=\frac{m_n^2}{N}+\frac{N-m_n}{N}(m_n+1)=1+m_n(1-\frac{1}{N})\]
也就是
\[E[m_{n+1}]=E[E[m_{n+1}|m_n]]=E[1+m_n(1-\frac{1}{n})]=1+(1-\frac{1}{N})E[m_{n}]\]
然后就有
\[E[m_n]=N-N\left(\frac{N-1}{N}\right)^n\]
当$n=N=2019$
\[E[m_{2019}]=2019-2019\left(\frac{2018}{2019}\right)^{2019}\]

TOP

dahool