20190822 关于某个结论的证明
qwaszx
·
·
个人记录
随便康了点东西
有n个在[0,1]之间均匀分布的连续型随机变量，求它们的第k小的期望.
先做一个简单的问题，n=k，这时就是\max，我们求出概率分布函数P(x)=x^k，即\max\{S\}\leq x的概率，然后求导一下就可以得到概率密度函数p(x)=kx^{k-1}，我们把它乘上x再积分就得到
E(\max\{S\})=\int_{0}^1p(x)xdx=\int_0^1kx^kdx=\frac{k}{k+1}
现在考虑k\neq n的情况.这时无法直接使用刚才的做法，我们来考虑\min-\max容斥，即
kth\min \{S\}=\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\max\{T\}
关于这个式子的证明，我们直接构造一波
设kth\min\{S\}=\sum\limits_{T\subseteq S}f(|T|)\max\{T\}
考虑S中第x+1小的元素，它对答案的贡献是\sum\limits_{i=0}^x\binom{x}{i}f(i+1)
这个式子的意思就是当第x+1小的元素作为\max时，集合里的数只能是前x个数选出若干个.它应该等于1当且仅当x=k-1，换句话说有
\sum\limits_{i=0}^x\binom{x}{i}f(i+1)=[x=k-1]
二项式反演一波得到
f(x+1)=\sum\limits_{i=0}^x\binom{x}{i}(-1)^{x-i}[i=k-1]=\binom{x}{k-1}(-1)^{x-k+1}
即
f(x)=\binom{x-1}{k-1}(-1)^{x-k}
于是我们得到
kth\min \{S\}=\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\max\{T\}
如果在两边套上一个期望就有
E(kth\min \{S\})=E\left(\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\max\{T\}\right)
由于期望是线性函数，所以有
E(kth\min \{S\})=\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}E(\max\{T\})
套到最开始的式子上就有
\begin{aligned}E(kth\min \{S\})&=\sum_{T\subseteq S}\binom{|T|-1}{k-1}(-1)^{|T|-k}\frac{|T|}{|T|+1}\\&=\sum_{i\geq 0}\binom{i-1}{k-1}\binom{n}{i}\frac{i}{i+1}(-1)^{i-k}\\&=\frac{k}{n+1}\sum_{i\geq 0}\binom{i}{k}\binom{n+1}{i+1}(-1)^{i-k}\end{aligned}
关于后面这个式子，去具体数学找一波答案发现有
\sum_k\binom{l}{m+k}\binom{s+k}{n}(-1)^k=(-1)^{l-m}\binom{s-m}{n-l}
关于这个式子的证明，具体数学上说可以"细心地从范德蒙德卷积得到"，但是我没有得到，所以这里使用由CTime_Pup_314神仙给出的生成函数证明.
设
\begin{aligned}F(x)&=\sum_nx^n\sum_k\binom{l}{m+k}\binom{s+k}{n}(-1)^k\\&=\sum_k\binom{l}{m+k}(-1)^k\sum_n\binom{s+k}{n}x^n\\&=\sum_k\binom{l}{m+k}(-1)^k(1+x)^{s+k}\\&=(-1)^{l-m}(1+x)^{s-m}\sum_k\binom{l}{k}(-1)^{l-k}(1+x)^k\\&=(-1)^{l-m}(1+x)^{s-m}x^l\end{aligned}
于是
[x^n](-1)^{l-m}(1+x)^{s-m}x^l=(-1)^{l-m}\binom{s-m}{n-l}
重新考虑之前的式子，它和标准形式还不太一样，缺少i=-1这一项，于是我们用标准形式减去i=-1的项，即
\frac{k}{n+1}\left((-1)^{n+k}\binom{-1}{k-n-1}-\binom{-1}{k}(-1)^{k-1}\right)=\frac{k}{n+1}
前面那一项因为k\leq n所以是0，\binom{-1}{k}=(-1)^k
于是我们得到结论E(kth\min(X))=\dfrac{k}{n+1}