4. 概率方法
期望的线性性质
例一
随机以概率\(1/n!\)取一个置换, 求置换的不动点数目\(X=|\{i:1\leq i\leq n,\pi(i)=i\}\text{}|\)的期望
\[\textbf{Pr}(X=k)=\frac{\binom{n}{k}\cdot D(n-k)}{n!} \]其中\(D(.)\)是错排数, 可由容斥原理计算
例如, \(n=3,\textbf{E}[x]=\frac{1}{6}\cdot3+\frac{3}{6}\cdot1+\frac{2}{6}\cdot0=1.\)
例如, \(n=4,\textbf{E}[x]=\frac{1}{24}\cdot4+\frac{6}{24}\cdot2+\frac{8}{24}\cdot1+\frac{9}{24}\cdot0=1.\)
令\(X_i\)为事件\(\pi(i)=i\)的指示变量
\(X\) 是这 n 个指示变量的加和, 那么 \(X\) 的期望是这n个指示变量期望的加和
\[X=X_1+X_2+\cdots+X_n.\\ \textbf{E}[X]=\textbf{E}[X_1]+\cdots+\textbf{E}[X_n]=\frac{1}{n}\times n=1. \]例二
在一个盒子里有 n 个颜色不同的球. 随机取一个球, 记录它的颜色, 然后将其放回. 令\(X\)为 t 轮之后所记录的不同颜色的数目, 求 \(X\) 的期望
最自然的解法是计数, 但对于较大的参数 n, t, 计算会变得复杂。
通过期望的线性性质计算
令\(X_i\)为事件"第i种颜色被记录了"的指示变量
\(X=X_1+X_2+\cdots+X_n.\)
\(对任意i, \quad\textbf{E}[X_i]=1-(\frac{n-1}{n})^t.\quad\text{}\)
\(\textbf{E}[X]=\textbf{E}[X_1]+\textbf{E}[X_2]+\cdots+\textbf{E}[X_n]=n(1-(\frac{n-1}{n})^t).\)
例如, \(n=t=4\) 时,\(\textbf{E}[X]=4\times(1-\left(\frac{3}{4}\right)^4)=\frac{175}{64}.\)
例三
在坐标点A,每次以等可能概率向可以移动的方向移动一步, 求第一次走到坐标点E的时候的步数的期望值
A——B——C——D——E
令\(X_AB\)为从A出发, 第一次到B的步数, 类似地\(X_BC,X_CD,X_DE\)
\(\textbf{E}[X_{AB}]=1\)
\(\textbf{E}[X_{BC}]=\frac{1}{2}+\frac{1}{2}(1+\textbf{E}[X_{AB}]+\textbf{E}[X_{BC}])\Rightarrow\textbf{E}[X_{BC}]=3.\)
\(\textbf{E}[X_{CD}]=\frac{1}{2}+\frac{1}{2}(1+\textbf{E}[X_{BC}]+\textbf{E}[X_{CD}])\Rightarrow\textbf{E}[X_{CD}]=5.\)
\(\textbf{E}[X_{DE}]=\frac{1}{2}+\frac{1}{2}(1+\textbf{E}[X_{CD}]+\textbf{E}[X_{DE}])\Rightarrow\textbf{E}[X_{DE}]=7.\)
利用期望的线性性质, \(E[Y]=16\).
概率方法
证明带有某种性质P的特定组合结构存在
概率方法: 以概率工具给出一种存在性的证明
拉姆塞理论
定义\(R(s, t)\)为最小的正整数n，使得对\(K_n\)的边做任意的红蓝二着色时一定会存在红色的\(K_s\)或者蓝色的\(K_t\)
\(R(k,k)>\bigl(\frac{1}{e\sqrt{2}}+o(1)\bigr)k2^{k/2}.\)
作业
每次抽奖A B C各有1/3的概率被抽到, 求集齐全套抽奖次数X的期望.
\(X_{12}\)代表奖品种类数从1到2的抽奖次数
\(X=X_{01}+X_{12}+X_{23}\)
\(E[X_{01}]=1, E[X_{12}]=3/2, E[X_{23}]=3\)
\(E[X]=E[X_{01}]+E[X_{12}]+E[X_{23}]=5.5\)
概率方法2
取样与调整
- 在概率方法的应用中, 取样的概率需要灵活选择
- 很多时候, 随机取样的样本不能满足题意, 还需要在取样后再进行调整
例一 取样与调整: 独立集
设图G有n个顶点和\(nd/2\)条边, 则\(\alpha(G)\geq n/2d\text{.}\)
- 随机构造S，每个顶点独立地以概率p置于S.
- 随机选取的S并不保证是独立集!令Y为S所诱导的边数。
- 对于S诱导的每一条边，在S中删除此边的一个顶点，得到点集S'。S'为独立集，其大小的期望为E[S]=E[S] -E[]=np - nd p2.取p = 1/d.
Lovasz局部引理
