如何计算期望值
How to calculate expectation value
我卡在期望值的问题上了
我得到了一个具有不同连通分量的无向图。第 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 个选择，则可能 + 1）。
所以这个随机变量的期望值由sum E(U_i)由期望的线性给出。
现在，E(U_i) = 0 * P(U_i == 0) + 1 * P(U_i==1) = P(U_i==1)所以我们要做的就是计算在目标之前选择第 i 个组件的概率。
第 i 个组件有 x[i] 个成员，而目标有 x[t] 个成员。
重要的是这些 x[i]+x[t] 个节点中的哪个是第一个被随机选择的，所以第一个被选中的概率是 x[i]/(x[i]+x[t]) 在组件中i.
所以我们得出结论：
P(U_i==1) = x[i]/(x[i]+x[t])
E(number of choices) = sum_(i != t) x[i]/(x[i]+x[t])
（根据问题定义可能+1）
我卡在期望值的问题上了
我得到了一个具有不同连通分量的无向图。第 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 个选择，则可能 + 1）。
所以这个随机变量的期望值由sum E(U_i)由期望的线性给出。
现在，E(U_i) = 0 * P(U_i == 0) + 1 * P(U_i==1) = P(U_i==1)所以我们要做的就是计算在目标之前选择第 i 个组件的概率。
第 i 个组件有 x[i] 个成员，而目标有 x[t] 个成员。
重要的是这些 x[i]+x[t] 个节点中的哪个是第一个被随机选择的，所以第一个被选中的概率是 x[i]/(x[i]+x[t]) 在组件中i.
所以我们得出结论：
P(U_i==1) = x[i]/(x[i]+x[t])
E(number of choices) = sum_(i != t) x[i]/(x[i]+x[t])
（根据问题定义可能+1）