Изменения

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

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

1605 байт добавлено, 12:45, 30 ноября 2019
Нет описания правки
 
{{Определение
|neat = 1
}}
{{Определение
|definition= Свойство <tex>A</tex> '''ассимптотически почти наверное истинно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 1</tex>
}}
{{Определение
|definition= Свойство <tex>A</tex> '''ассимптотически почти наверное ложно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</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>
}}
 
== Теоремы о связи вероятности и матожидания ==
{{Теорема
|id=th1
|statement= Пусть <tex>Z_n</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_n(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно.
|proof=
Воспользуемся [[Неравенство Маркова | неравенством Маркова]]:
 
<tex>P(Z_n > 0) = P(Z_n \geqslant 1) \leqslant EZ \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
 
{{Теорема
|id=th2
|statement= Пусть <tex>Z_n</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | Z_n(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EZ_n \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 = 0) = P(Z_n \leqslant 0) = P(EZ_n - Z_n \geqslant EZ_n) \leqslant P(|EZ_n - Z_n| \geqslant EZ_n) \leqslant \dfrac{DZ_n}{(EZ_n)^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
 
== См. также ==
* [[Дискретная случайная величина]]
* [[Дисперсия случайной величины]]
* [[Математическое ожидание случайной величины]]
89
правок

Навигация