Как вычислить значение ожидания

Question

Я застрял в задаче математического ожидания.

Мне присвоен неориентированный граф с различными компонентами связи. 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. 

Что такое ожидаемое значение количества вариантов, которые мы должны сделать до тех пор, пока не будет отмечен нужный узел.

Я могу вычислить значение ожидания грубой силой, но есть ли другой эффективный метод его вычисления?

Answer 1

Пусть U_i является случайной величиной, равной 1, если i-я компонента выбрана перед целевым компонентом (и равна нулю в противном случае).

Поэтому количество вариантов задается 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 в зависимости от определения проблемы)