Книга Кому нужна математика? Понятная книга о том, как устроен цифровой мир, страница 36. Автор книги Нелли Литвак, Андрей Райгородский

Разделитель для чтения книг в онлайн библиотеке

Онлайн книга «Кому нужна математика? Понятная книга о том, как устроен цифровой мир»

Cтраница 36

Вспомните один известный замечательный предел


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

где е – основание натурального логарифма. Интуитивно результат следует из похожего предельного перехода:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Давайте посмотрим, о чем нам говорит эта формула.

Если 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(ukuk+1) в единицу времени.

Теперь давайте посмотрим, на сколько количество серверов с k заявками или больше увеличивается в единицу времени. Чтобы увеличить число таких серверов, заявки должны поступать на серверы, у которых в данный момент k − 1 заявка. При методе выбора из двух вероятность того, что новое задание попадет на сервер с k или больше заявками, равна


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

потому что в этом случае оба случайно и независимо выбранных сервера должны иметь k или больше заявок, и для каждого из двух серверов эта вероятность иk [26] . Значит, вероятность того, что новая заявка поступит на сервер, у которого ровно k − 1 заявка, равна


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Поскольку заявок в единицу времени поступает λп, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:


Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Результат, приведенный в работе {34} , говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:

Вход
Поиск по сайту
Ищем:
Календарь
Навигация