Вспомните один известный замечательный предел
где е – основание натурального логарифма. Интуитивно результат следует из похожего предельного перехода:
Давайте посмотрим, о чем нам говорит эта формула.
Если c < 1, то в среднем число вершин, у которых нет ни одного ребра, стремится к бесконечности. В этом случае таких вершин будет очень много, связность сети с большой вероятностью будет потеряна.
Если c > 1, то в среднем число вершин, у которых нет ни одного ребра, стремится к нулю. Значит, с большой вероятностью таких вершин не будет и связность сети сохранится.
Таким образом, мы видим, откуда появляется фазовый переход!
Наконец, если c = 1, то в среднем число вершин, у которых нет ни одного ребра, равно единице. Заметим, что единица – это среднее значение, а в реальности таких вершин может быть 0, 1, 2… Можно доказать, что соответствующее распределение вероятности близко к закону Пуассона с параметром 1:
Соответственно, вероятность того, что таких вершин не будет, то есть связность сети сохранится, равна е–1.
Добавим, что это еще не строгое доказательство, потому что мы проанализировали только среднее количество вершин, у которых нет ни одного ребра. Для завершения доказательства нужно еще показать, что в случае c < 1 и c > 1 число вершин без ребер относительно мало отклоняется от среднего значения. Для этого разработаны стандартные методы, в частности, основанные на неравенствах Маркова и Чебышева. Эти неравенства названы в честь замечательных русских математиков, стоявших у истоков теории вероятностей.
Назад к Главе 4
Приложение к главе 5
Анализ метода выбора из двух
Допустим, у нас n серверов. Заявки (или задания) поступают с интенсивностью λn в единицу времени, и каждый сервер в среднем обрабатывает одно задание в единицу времени, то есть загрузка системы равна λ < 1 (если λ ≥1, то система перегружена, очередь будет расти до бесконечности). Рассмотрим случай, когда n очень велико и стремится к бесконечности.
Обозначим через fk долю серверов, у которых ровно k заявок (заявка, которая находится на обслуживании в данный момент, тоже учитывается). Обозначим через uk долю серверов, у которых заявок k или больше. Значения uk можно легко получить через fk и наоборот:
Понятно, что u0 = 1.
Представим, что система находится в равновесии. Тогда у нас в среднем
серверов, на которых ровно k заданий. Все эти серверы обрабатывают задания со скоростью одно задание в единицу времени. Другими словами, количество серверов с k заявками или больше уменьшается на n(uk − uk+1) в единицу времени.
Теперь давайте посмотрим, на сколько количество серверов с k заявками или больше увеличивается в единицу времени. Чтобы увеличить число таких серверов, заявки должны поступать на серверы, у которых в данный момент k − 1 заявка. При методе выбора из двух вероятность того, что новое задание попадет на сервер с k или больше заявками, равна
потому что в этом случае оба случайно и независимо выбранных сервера должны иметь k или больше заявок, и для каждого из двух серверов эта вероятность иk
[26]
. Значит, вероятность того, что новая заявка поступит на сервер, у которого ровно k − 1 заявка, равна
Поскольку заявок в единицу времени поступает λп, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на
Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:
Результат, приведенный в работе
{34}
, говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:
