Изменения

Перейти к: навигация, поиск

Случайные графы

243 байта убрано, 16:09, 4 декабря 2019
м
Существование треугольников в случайном графе
Воспользуемся [[Неравенство Маркова| неравенством Маркова]]:
<tex>P(T > 0) = P(T \geqslant 1) \leqslant E[T] = \sum\limits_{i, j, k}T_{i, j, k}p^3 = C^3_np^3 \sim \dfrac{n^3p^3}{6}p^3 \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
 
'''''Добавил скобки вокруг E[T], оформи так же, а то слабо читается. С дисперсией тоже лучше добавить. Деление на 6 должно появиться под суммой сразу'''''
{{Теорема
Воспользуемся [[Неравенство Маркова#thCheb| неравенством Чебышева]]:
<tex>P(T = 0) = P(T \leqslant 0) = P(ET E[T] - T \geqslant ETE[T]) \leqslant P(|ET E[T] - T| \geqslant ETE[T]) \leqslant \dfrac{DTD[T]}{(ETE[T])^2}</tex>.
Найдем <tex>ETE[T^2]</tex>:
<tex>ETE[T^2 ] = E[(\sum\limits_{i, j, k}T_{i, j, k})^2]= E([\sum\limits_{i, j, k}(T_{i, j, k})^2) ] + E([\sum\limits_{i, j, k, a, b, c}T_{i, j, k}T_{a, b, c}) ] =</tex>
<tex>= ET E[T] + (C^3_nC^3_{n - 3} + C^3_nC^2_{n - 3})p^6 + 3C^3_n(n - 3)p^5 \sim \dfrac{n^3p^3}{6} + (\dfrac{n^6}{36} + \dfrac{n^5}{4})p^6 + \dfrac{n^4}{2}p^5 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} + \dfrac{n^4p^5}{2} \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36}</tex>
<tex>DT D[T] = ETE[T^2 ] - (ETE[T])^2 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} - \dfrac{n^6p^6}{36} = \dfrac{n^3p^3}{6}</tex>
<tex>P(T = 0) \leqslant \dfrac{\dfrac{n^3p^3}{6}}{\dfrac{n^6p^6}{36}} = \dfrac{6}{p^3n^3} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>
31
правка

Навигация