关于经典题：随机点之间的线段的期望长度
大眼仔Happy
·
·
个人记录
题目：
在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。——NOIP 2018
\begin{aligned}
A.\,\dfrac{1}{2}
\qquad\qquad
\color{green}
B.\,\dfrac{1}{3}\sqrt{}
\qquad\qquad
\color{black}
C.\,\dfrac{2}{3}
\qquad\qquad
D.\,\dfrac{3}{5}
\end{aligned}
Solution
一共有多种解法，其中有些是我想到的，另一些是百度找到的好方法。
Sol 1（自己想到的，但是不太会计算，然后百度见到的计算）:
事实上我应该也是会的，虽然不会二重定积分……但是一个那里会啊……
考虑直接暴力二重定积分（但是需要一点微积分基础）：
&\iint_{S=1}|x-y|\,dx\,dy\\
=&2(\int_{0}^{1}dx\int_{0}^{x}(x-y)\,dy)\\
=&2(\int_{0}^{1}\dfrac{1}{2}x^2\,dx)\\
=&\dfrac{1}{3}
\end{aligned}
Sol 2（自己想到的）:
更加暴力的极限做法（需要一点极限基础，也用了微分法的思想，所以其实和 Sol1 本质上一样）：
设平均分成了 n 个线段，每个线段的长度都是 \dfrac{1}{n}，然后有编号为 0,1,2,3,\cdots,n 的点。我们把问题变成只能选我们设的这些点。
期望就是每一个方案的价值在乘上概率即可，所以有
\begin{aligned}
Ans
=&\sum_{i=0}^{n}\sum_{j=0}^{n}|\dfrac{i}{n}-\dfrac{j}{n}|\times (\dfrac{1}{n+1})^2\\
=&\dfrac{\sum_{i=0}^{n}i^2-n\sum_{i=0}^{n}i}{n(n+1)^2}+\dfrac{1}{2}
\end{aligned}
所以
\lim_{n\to \infty}Ans=\dfrac{\frac{2}{6}-\frac{1}{2}}{1}+\dfrac{1}{2}=\dfrac{1}{3}
（这里有个技巧，如果最高项相同的话，对于每一个分数直接用最高项的系数做分母分子就可以了。）
Sol 3（自己想到的）:
是自认为自己能想到的最好的解法。
设 f(x) 表示原问题中线段长度为 x 的答案，显然要求的是 f(1)。考虑分治，将原线段平均分成一半。分成两种情况：
两点在同一半：
这种情况实际上就是 f(\dfrac{1}{2})，而且显然有 f(\dfrac{1}{2})=\dfrac{1}{2}f(1)。
两点不在同一半：
这种情况也不会太复杂，可以简单给一个例子证明。
下面随便一个方案(假设选择的是红色的）：
\color{black}\_\_\_\color{red}{\_\_\_}\color{blue}{|}\color{black}\color{red}\_\color{black}\_\_\_\_\_
那么就会有一个对应的方案：
\color{black}\color{red}\_\color{black}\_\_\_\_\_\color{blue}{|}\color{black}\_\_\_\color{red}{\_\_\_}
第二中方案就是将左边的部分移到了右边，然后选择黑色的部分，我们会发现两种方案加起来刚好是整条线段，所以这里的期望应该是线段的一半，即 \dfrac{1}{2}，虽然一共有无限种方案，但是每一对都是 \dfrac{1}{2}，所以总共也是 \dfrac{1}{2}。
两种情况的概率都是 \dfrac{1}{2}，所以有 f(1)=\dfrac{1}{2}f(\dfrac{1}{2})+\dfrac{}{}\dfrac{1}{2}\times \dfrac{1}{2}
最后就得到了 f(1)=\dfrac{1}{3}。
Sol 4（百度的）:
见过的最巧妙的做法。
首先将问题转化为随机一个点 z 在线段 [x,y] 的概率。
然后对于每一个三元组 (a,b,c)（这里约定 a<b<c），分别用 x,y,z 匹配 a,b,c。若 z 匹配到的是 b，则说明在线段内，合法。概率显然为 \dfrac{1}{3}。
相等的情况并没有计算进去，但是我们会发现他并没有对答案进行贡献。可以考虑一下，取端点的话，对（线段 [x,y]）/（总线段 [0,1]）的值其实影响可以是被认为没有的。
upd on 9.13:更新了一下，对约定调整了一下，避免了取等的逻辑错误，参考这个。