436
правок
Изменения
м
small changes
Далее:
<tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} > t_0) \thickapprox P_{n, p}(BinomBinomial(n, 1 - (1 - p)^{t_0}) > t_0) \thickapprox</tex><br>
(с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>
<tex>\thickapprox P_{n, p}(BinomBinomial(n, pt_0) > t_0) \thickapprox</tex><br>
(с учетом центральной предельной теоремы) <br>
<tex> \thickapprox \int\limits_{\frac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx</tex>.
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
Применим центральную предельную теорему к
<tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(BinomBinomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
Интегрирование пойдет '''переформулируй''' от минус бесконечности до
<tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
=== Неоткрытые вершины ===
Будем считать шагом алгоритма поиска открытие новой вершины. После первых <tex>i</tex> шагов алгоритма, любая из вершин, кроме стартовой, может быть неоткрытой с вероятностью <tex>p = (1 - \frac{d}{n})^i</tex>. Пусть <tex>z_i</tex> {{---}} число вершин, открытых за первые <tex>i</tex> шагов алгоритма поиска. <tex>z_i</tex> распределены как <tex>Binomial(n − 1,1 − (1 - \frac{d}{n})^i)</tex>.<br> '''Унифицируй и пиши везде либо Binom, либо Binomial'''
== Ветвящийся процесс =='''
