Всего с помощью двух слов можно охарактеризовать такие вещи, как
- поток вызовов на телефонной станции
- поток автомобилей на магистрали
- поток абонентов, звонящих в техподдержку
и многое другое. Всё это называется «простейший поток».
Очевидно, что количество вызовов на станции, автомобилей на магистралиявляются случайными в каждый момент времени. Учитывая то, что все три вещи из списка являются довольно важными для всего общества и для его оптимального существования, необходимо научиться моделировать этот поток.
Особенно актуальным является последний пункт приведённого списка, поскольку юзеры, не знающие простых основ компьютера, успевают их нереально задолбать, а зная параметры потока, можно спрогнозировать их количество.
Математическая модель простейшего потока требует от него нескольких свойств.
- Стационарность. Это означает, что вероятность попадания того или иного числа событий на некоторый отрезок времени зависит только от длины участка и не зависит от того, где расположен этот участок.
- Отсутствие последействия. Это означает следующее: если два промежутка времени не пересекаются, то количество событий, попавших на один из них, не зависит от количества событий, попавших на другой участок.
- Ординарность.Поток является ординарным, если вероятность попадания на один достаточно малый отрезок времени двух и более событий пренебрежимо меньше его длины.
Заметим, что в зависимости от того, как происходит разбиение реальных событий на временные интервалы, может зависеть, является ли данный поток простейшим или нет.
Например, поток автомобилей на магистрали в сутки не является простейшим, т. к. он не является стационарным: днём автомобилей меньше, чем утром и вечером, в то время как тот же поток в час пик уже можно считать простейшим.
Главным здесь является то, что интересующее нас количество подчиняется дискретному Пуассоновскому распределению.
Алгоритм
Пусть нам задано значение параметра a — среднее количество звонков в техподдержку, к примеру, и нам необходимо сгенерировать случайную величину X, подчиняющуюся закону распределения Po(a)
В классе Random языка C#, который я выбрал в качестве примера, есть метод Sample(), который генерирует случайное число от 0 до 1, равномерно на этом отрезке распределённое.
Так каким же образом из вещественного числа нам получить целое число? С помощью математических выкладок, очень простых с точки зрения специалистов по теории вероятности, можно доказать следующее утверждение.
Пусть у нас имеется некоторое количество независимых случайных чисел, равномерно распределённых на отрезке [0;1]. Тогда наименьшее число X, такое, что произведение X наших случайных чисел строго меньше, чем exp(-a), подчиняется Пуассоновскому распределению с параметром a
В результате мы получаем следующий алгоритм:
class Poisson: Random {
public static uint Generate(double a){
uint X = 0;
double Prod = 1;
double U = base.Sample();
Prod *= U;
while (Prod >= Math.exp(-a)) {
X++;
U = base.Next();
Prod *= u;
}
return X;
}
}
}
Вычислительная сложность этого алгоритма составляет O(a), однако здесь нам приходится многократно генерировать случайную величину, когда, на самом деле, можно обойтись всего лишь одной:
public static uint Generate(double a){
uint X = 0;
double Prod = Math.Exp(-a);
double Sum = Prod;
double U = base.Sample();
while (U > Sum) {
X++;
Prod *= a/Convert.ToDouble(X);
Sum += Prod;
}
return X;
}
Сложность этого алгоритма также составляет O(a).
Автор: ProPupil
