我陷入了一个期望值的问题。
我得到了一个具有不同连通分量的无向图。第i个组件中有x[i]个元素给出了连接元件的个数和集合x选择节点后，连接到该节点的所有节点都将被标记。
So overall we have to do something like this:
1. Pick any node which is not marked.
2. Mark all the nodes of the connected component, which contains node chosen in step 1.
repeat process 1, 2 until you mark a specific code.
在标记所需节点之前，我们必须做出的选择的数量的期望值是多少。
我可以用蛮力来计算期望值，但是有没有其他有效的方法来计算它呢？
最佳答案
如果在目标组件之前选择了第i个组件，则设U_i为等于1的随机变量（否则为零）。
因此，选择的数量由sum U_i给出（如果第一次找到它算是一个选择，则可能是+1）。
因此，这个随机变量的期望值是由期望的线性来给出的。
现在，sum E(U_i)我们要做的就是计算第i个分量在目标之前被选择的概率。
第i个组件有x[i]个成员，而目标有x[t]个成员。
所有重要的是，这些x[i]+x[t]节点中的哪一个是第一个随机选择的，所以第一个选择的节点在组件i中的概率是E(U_i) = 0 * P(U_i == 0) + 1 * P(U_i==1) = P(U_i==1)。
所以我们得出结论：
P(U_i==1) = x[i]/(x[i]+x[t])
E(number of choices) = sum_(i != t) x[i]/(x[i]+x[t])
（根据问题定义，可能为+1）
关于algorithm - 如何计算期望值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32495461/