Изменения

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

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

1 байт убрано, 21:12, 2 декабря 2019
м
Теоремы о связи вероятности и матожидания
{{Теорема
|id=th1
|statement= Пусть <tex>Z_nN_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_nN_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n N_z \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно.
|proof=
Воспользуемся [[Неравенство Маркова | неравенством Маркова]]:
<tex>P(Z_n N_z > 0) = P(Z_n N_z \geqslant 1) \leqslant EZ \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
|id=th2
|statement= Пусть <tex>Z_nN_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_nN_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n EN_z \rightarrow \infty</tex>, при <tex>n \rightarrow \infty</tex>, и <tex>EZ^2 = (EZ)^2(1 + o(1))</tex> то <tex>A</tex> а.п.н истинно.
|proof=
Воспользуемся [[Неравенство Маркова#thCheb | неравенством Чебышева]]:
<tex>P(Z_n N_z = 0) = P(Z_n N_z \leqslant 0) = P(EZ_n EN_z - Z_n N_z \geqslant EZ_nEN_z) \leqslant P(|EZ_n EN_z - Z_nN_z| \geqslant EZ_nEN_z) \leqslant \dfrac{DZ_nDN_z}{(EZ_nEN_z)^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
31
правка

Навигация