浏览顺序相同的简历数期望

yinda_peng

大概两三天之后会发布答案，如果有鱼油在此之前写出来了，将提前发布答案
写对的鱼油给予评分奖励（非会员优先评鱼币，会员优先评荣誉），不仅写对还给出清晰解答的鱼油将额外给予贡献评分奖励
希望大家尽量自己思考，一道题目，你看答案写和没看答案写是完全不同的感受

  某公司录用员工时，采用这样一种方式：公司会统一组织进行一场考核，并根据考核表现打分（百分制），体现在简历上，成绩越高，越有可能通过面试。得到考核分数后，甲、乙两人负责审核面试者，他们均有所有面试者的简历，并且将各自根据面试者能力值从大到小的顺序浏览。由于简历事先被打乱过，所以能力值相同的简历的出现顺序是从它们的全排列中等可能地取一个。现已知部分考核成绩为(共15个)：[77,89,72,84,72,88,80,77,84,89,90,72,75,80,82]。设A为甲乙两人的浏览顺序中出现在同一位置的简历数，试求A的期望E(A)。

yinda_peng

我们假设不同元素个数为 k 个，分别为 x1, x2, ..., xk 。我们知道数组是排好序的，所以相同的元素一定连续出现。

我们可以将数组分成 {x1x1...x1, x2x2...x2, ..., xkxk...xk} 这样 k个小区间。

设 X 表示出现在同一位置简历的总数， Xi 表示 第i个区间中 在同一位置元素的个数。

同一位置简历总数 X 等于每个小区间中同一位置简历数之和，即 X = X1 + X2 + ... + Xk

所以由期望公式可得到 E(X) = E(X1 + X2 + ... + Xk) = E(X1) + E(X2) + ... + E(Xk)。下面求 E(X1), E(X2), ..., E(Xk)。

不失一般性，我们考虑第 i 个区间 xixi...xi 的期望 E(Xi)，设区间长度为 L。为了符号简单，我们记这 L个 xi 组成的序列为 y1, y2, ..., yL 。并且设 Yi 是第 i 个元素是否相同的 0-1 变量，如果第 i 个元素相同， Yi=1，否则 Yi=0。

由期望公式可知，E(Xi) = E(Y1 + Y2 + ... + YL) = E(Y1) + E(Y2) + ... + E(YL) = 1/L + 1/L + ... + 1/L = 1/L * L = 1。（这里如果概率论学的不好可能会看不懂，三言两语也解释不清，其实是0-1变量的典型用法。）

于是， E(X) = E(X1 + X2 + ... + Xk) = E(X1) + E(X2) + ... + E(Xk) = 1 + 1 + ... + 1 = k。我们只需要知道不同元素的个数。