Независимые множества в случайных графах пересечений: различия между версиями

Независимые множества в случайных графах пересечений (посмотреть исходный код)

170 байт добавлено , 26 февраля 2020

4817

правок

@@ Строка 28: / Строка 28: @@
 '''Теорема 2. Обозначим за <math>X^{(k)}</math> число независимых множеств размера k в случайном графе пересечений <math>G(n, m,\overrightarrow{p})</math>, где <math>\overrightarrow{p} = [p_1, p_2, ..., p_m]</math>. Тогда'''
-<math>Var \big( X^{(k)} \big) = \sum_{s=1}^k \binom{n}{2k - s} \binom{2k - s}{s} \Big( \gamma(k, s) \frac{E[x^{(k)}]}{\binom{n}{k}} - \frac{E^2 [X^{(k)}]}{\binom{n}{k}^2} \Big)</math>, где E [X^] – среднее число независимых множеств размера k, а m Y(k, s)= }~
+<math>Var \big( X^{(k)} \big) = \sum_{s=1}^k \binom{n}{2k - s} \binom{2k - s}{s} \Big( \gamma(k, s) \frac{E[x^{(k)}]}{\binom{n}{k}} - \frac{E^2 [X^{(k)}]}{\binom{n}{k}^2} \Big)</math>,
+'''где <math>E[X^{(k)}]</math> – среднее число независимых множеств размера k,'''
+'''а <math>\gamma(k, s) = \prod_{i=1}^m \Big( (1 - p_i)^{k - s} + (k - s)p_i (1 - p_i)^{k - s - 1} \Big) \Big( 1 - \frac{sp_i}{1 + (k - 1) p_i} \Big).</math>'''