求两个随机变量的差的绝对值的期望

问题1：给定离散随机变量 x 均匀分布在区间 [a, b] 的整点上，y 均匀分布在区间 [c, d] 的整点上，求期望 E(|x-y|)。

问题很简单，显然最直接的办法就是枚举 x 和 y 然后进行统计即可。如果再稍稍思考一下，那么可以发现其实只用枚举其中一个变量就行了，因为若固定 x = i，那么求 E(|i-y|) 只需要对 i <=y 和 i > y 两种情况分别进行讨论即可。上面两个方法的运行时间都是与区间的大小相关的，对于这样简单的一个问题，有理由相信一定有 O(1) 的方法存在，事实上也的确如此，推导如下。

首先可以交换 x , y 的顺序以保证 a <= c，那么 a, b, c, d 之间的顺序可以分成 3 种情况：

a <= b <= c <= d
a <= c < b <= d
a <= c <= d < b

对于第 1 种情况，因为 y 始终大于等于 x，因此 E(|x-y|) = E(y) – E(x);

对于第 2 种情况，除了 cb 段以外 y 始终大于 x, 因此 E(|x-y|) = E(y) – E(x) + p_cb_cb * e_cb_cb，这里的p_cb_cb 表示 x 和 y 都分布在 cb 段的概率，e_cb_cb 表示当 x 和 y 都分布在 cb 段时，|x-y|的期望。

对于第 3 种情况，可以将第 ab 拆成 ad 和 d’b 两段，这里 d’ = d + 1。于是 E(|x-y|) = p_ad_cd * e_ad_cd + p_d’b_cd * e_d’b_cd，而 e_ad_cd 可以按第 2 种情况来求， e_d’b_cd 可以按第 1 种情况来求，问题解决。

现在唯一剩下的问题就是如果求 e_cb_cb，显然若 b – c + 1 = n，那么 e_cb_cb = e_[1, n]_[1, n]. 于是问题可以转换为：

问题2：给定离散随机变量 x 和 y 均匀分布在区间 [1, n] 的整点上，求期望 E(|x-y|)。

问题 2 简单地做一个求和就可以得到一个 closed form：

$\begin{align*} E_{n} &= \frac{1}{n^2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{|i-j|}} =\frac{2}{n^2}\sum_{i=1}^{n}{\sum_{j=1}^{i}{(i-j)}} =\frac{2}{n^2}\sum_{i=1}^{n}{\sum_{k=1}^{i-1}{k}} \\ &= \frac{1}{n^2}\sum_{i=1}^{n}{(i^2-i)} =\frac{n^2-1}{3n} \end{align*}$

利用上式可以得到解决问题 1 的代码如下：

double eabs(int a, int b, int c, int d)
{
    if (a > c) {swap(a, c); swap(b, d);}
    if (b > d)
    {
        double e_ad_cd = eabs(a, d, c, d);
        double p_ad_cd = (double)(d - a + 1) / (b - a + 1);
        double e_db_cd = (b - c + 1) / 2.0;
        double p_db_cd = (double)(b - d) / (b - a + 1);
        return e_ad_cd * p_ad_cd + e_db_cd * p_db_cd;
    }
    int n = max(b - c + 1, 1);
    double e_ab_cd = (c + d - a - b) / 2.0;
    double e_cb_cb = (n - 1.0 / n) / 3.0;
    double p_cb_cb = (double)n / (b - a + 1) * (double)n / (d - c + 1);
    return e_ab_cd + e_cb_cb * p_cb_cb;
}

再来看如果随机变量是连续分布的那情况又如何：

问题3：给定连续随机变量 x 均匀分布在区间 [a, b) 上，y 均匀分布在区间 [c, d) 上，求期望 E(|x-y|)。

问题 3 同样可以根据 a, b, c, d 的顺序分成 3 种情况进行讨论，而在情况 2 中仍然还要碰到求 e_cb_cb 的问题。若 n = b - c，对于连续随机变量显然有 e_cb_cb = n * e_[0,1)_[0,1)，于是问题就转化成了：

问题4：给定连续随机变量 x 和 y 均匀分布在区间 [0, 1) 上，求期望 E(|x-y|)。

对于问题 4，可以直接求一个积分(实际上如果画出函数图像的话就是两个三棱锥)，也可以直接求极限：

$E_{[0,1)}=\lim_{n\rightarrow \infty}{\frac{E_n}{n}}=\lim_{n\rightarrow \infty}{\frac{n^2-1}{3n^2}}=\frac{1}{3}$

由上式可以得到解决问题 3 的代码如下：

double eabs(double a, double b, double c, double d)
{
    if (a > c) {swap(a, c); swap(b, d);}
    if (b > d)
    {
        double e_ad_cd = eabs(a, d, c, d);
        double p_ad_cd = (d - a) / (b - a);
        double e_db_cd = (b - c) / 2.0;
        double p_db_cd = (b - d) / (b - a);
        return e_ad_cd * p_ad_cd + e_db_cd * p_db_cd;
    }
    double n = max(b - c, 0.0);
    double e_ab_cd = (c + d - a - b) / 2.0;
    double e_cb_cb = n / 3.0;
    double p_cb_cb = n / (b - a) * n / (d - c);
    return e_ab_cd + e_cb_cb * p_cb_cb;
}

最后祝大家兔年快乐!