数学期望学习笔记

数学期望和组合计数有许多共通之处,可以看作是带系数的计数。

Part 1 记号和定义

在本文中:

  • 仅讨论在值域中均匀随机的随机变量;

  • xx 为某随机变量,即取值在值域中随机的变量,则 Px(i)P_x(i)xx 取到 ii 的概率;

  • xx 为某随机变量,则 E(x)\mathbb E(x) 表示 xx 的期望值,即 iiPx(i)\sum\limits_{i} i\cdot P_x(i)iPx(i)di\int i\cdot P_x(i)\,di

Part 2 性质和技巧

把期望看作带系数计数 与 考虑组合意义 都是常用的推导方法。

2.0 约定

  • 证明中只用到了 \sum 且没有特殊说明:这里只证明值域离散(随机变量只能取整数)的情况下的性质,值域连续(随机变量可以取实数)的情况下也有这些性质,将这些证明中的 i\sum\limits_{i} 换成 di\int\,di 即可证明;
  • 证明中用到了 \int 且没有特殊说明:这些性质只有在值域连续的情况下才能存在;

2.1 基础性质

xxyy 为某两随机变量(不一定无关,即它们可能会互相影响)。

  • 可加性

    E(x+y)=E(x)+E(y)\mathbb E(x+y)=\mathbb E(x)+\mathbb E(y)

    证明

    E(x+y)=iijPx(j)Py(ij)=jPx(j)kPy(k)(j+k)=jjPx(j)+kkPy(k)\begin{aligned} \mathbb E(x+y)&=\sum\limits_{i} i\cdot \sum \limits_{j}P_x(j)P_y(i-j)\\ &=\sum\limits_{j}P_x(j)\sum\limits_{k}P_y(k)\cdot(j+k)\\ &=\sum\limits_{j}j\cdot P_x(j)+\sum\limits_{k}k\cdot P_y(k) \end{aligned}

    Q.E.D.

  • 线性性

    对于某常数 α\alpha,有:

    E(αx)=αE(x)\mathbb E(\alpha x)=\alpha \mathbb E(x)

    证明

    E(αx)=iαPx(i)=αiiPx(i)=αE(x)\mathbb E(\alpha x)=\sum\limits_{i}\alpha \cdot P_x(i)=\alpha\sum\limits_{i}i\cdot P_x(i)=\alpha\mathbb E(x)

    Q.E.D.

  • 无关可乘性

    xxyy 无关,即一个的取值不会影响到另一个,则有:

    E(xy)=E(x)E(y)\mathbb E(xy)=\mathbb E(x)\cdot\mathbb E(y)

    证明

    E(xy)=ijijPx(i)Py(j)=E(x)E(y)\mathbb E(xy)=\sum\limits_{i}\sum\limits_{j}ij\cdot P_x(i)P_y(j)=\mathbb E(x)\cdot \mathbb E(y)

    Q.E.D.

2.2 常用技巧

若无特殊说明,公式中出现的变量均为随机变量。

  • 发生事件期望所需次数

    若某事件每次发生的概率为 aa,其中 aa 是一个确定的实数,则发生该事件所需的期望次数为 1a\frac{1}{a}

    证明

    E=a+(1a)(E+1)E=a+E+1aEaaE=1E=1a\mathbb E=a+(1-a)(\mathbb E+1)\\ \mathbb E=a+\mathbb E+1-a\mathbb E-a\\ a\mathbb E=1\\ \mathbb E=\frac{1}{a}

    Q.E.D.

  • 分配

    E((a+b)(c+d))=E(ac)+E(ad)+E(bc)+E(bd)\mathbb E((a+b)(c+d))=\mathbb E(ac)+\mathbb E(ad)+\mathbb E(bc)+\mathbb E(bd)

    E(i=1nj=1mxi,j)=E(x1,1×x2,1××xn,1)+E(x1,2×x2,1××xn,1)++E(x1,m×x2,m××xn,m)\mathbb E\left(\prod\limits_{i=1}^n\sum\limits_{j=1}^m x_{i,j}\right)=\\ \mathbb E(x_{1,1}\times x_{2,1}\times \dots \times x_{n,1})+E(x_{1,2}\times x_{2,1}\times \dots \times x_{n,1})+\dots+E(x_{1,m}\times x_{2,m}\times \dots \times x_{n,m})

    即每一个 E()\mathbb E() 中一共有 nn 项相乘,第 ii 项可以是 xi,[1,m]x_{i,[1,m]} 中的任意一个。

    拆括号后运用期望的可加性即可证明,第二条是第一条的拓展。

  • nn 个值域相同的随机变量的第 kk 小值的期望

    nn 个在 [0,1][0,1] 间的连续随机变量 x1nx_{1\sim n},则 E(kth-mink{xi})=kn+1\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{k}{n+1}

    nn 个在 [1,m][1,m] 间的离散随机变量 x1nx_{1\sim n},则 E(kth-mink{xi})=kmn+1\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{km}{n+1}

    证明

    先证明第一条。

    引入另一个 [0,1][0,1] 间的连续随机变量 yy,设 P(i)P(i)ikth-mink{xi}i\le\text{kth-min}_k\{x_i\} 的概率,那么 E(kth-mink{xi})=01P(i)di1=P(y)\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{\int_0^1 P(i)\,di}{1}=P(y)

    考虑给所有随机变量升序排序,相同则按原来的位置排,那么一共有 (n+1)!(n+1)! 种顺序,其中 yy 排在前 kk 位的一共有 kn!kn! 种顺序,具体的考虑插入即可。

    那么 P(y)=kn!(n+1)!=kn+1=E(kth-mink{xi})P(y)=\frac{kn!}{(n+1)!}=\frac{k}{n+1}=\mathbb E\left(\text{kth-min}_k\{x_i\}\right)

    第二条相当于第一条把 xix_i 乘上 mm 然后取整转化为离散情况。

    Q.E.D.

Part 3 例题

3.1 期望参与答案计算

  • CF1523E Crypto Lights | 题解

  • CF1278F Cards

    查看题解

    考虑设第 ii 次洗牌后第一张牌的情况为 xix_i(是王牌则 xi=1x_i=1,否则 xi=0x_i=0),那么显然 E(xi)=1m\mathbb E(x_i)=\frac{1}{m}

    发现答案等价于 E((i=1nxi)k)\mathbb E\left(\left(\sum\limits_{i=1}^n x_i\right)^k\right),根据 2.2 中的分配技巧,这个东西相当于:

    E(x1k)+E(x1k1x2)++E(xnk)\mathbb E(x_1^k)+\mathbb E(x_1^{k-1}x_2)+\dots+\mathbb E(x_n^k)

    即每一个 E()\mathbb E() 中一共有 kk 项相乘,第 ii 项可以是 x[1,n]x_{[1,n]} 中的任意一个。

    考虑一项一项填入 E()\mathbb E() 中,由于不同的 xpx_p 互相独立且本质相同,则 p1=p2,E(xp1xp2)=E(xp1)E(xp2)=1m2\forall p_1\not=p_2,\mathbb E(x_{p_1}x_{p_2})=\mathbb E(x_{p_1})\mathbb E(x_{p_2})=\frac{1}{m^2}。而相同的 xpx_p 取值肯定一样,那么我们只需要关心有多少个不同的 xpx_p

    fi,jf_{i,j} 表示确定了前 ii 项,其中一共有 jj 个不同的 xpx_p。显然 f0,0=1f_{0,0}=1,转移考虑下一位填入的 xpx_p 是否出现过:

    fi,j=fi1,j×j+fi1,j1×(nj+1)×1mf_{i,j}=f_{i-1,j}\times j+f_{i-1,j-1}\times (n-j+1)\times \frac{1}{m}

    最后答案即为 i=0kfk,i\sum\limits_{i=0}^k f_{k,i}

    时间复杂度 O(k2)O(k^2)

  • CF1842G Tenzing and Random Operations

3.2 期望参与时间复杂度计算