Моделирование простейшего потока

Всего с помощью двух слов можно охарактеризовать такие вещи, как

• поток вызовов на телефонной станции
• поток автомобилей на магистрали
• поток абонентов, звонящих в техподдержку

и многое другое. Всё это называется «простейший поток».

Очевидно, что количество вызовов на станции, автомобилей на магистралиявляются случайными в каждый момент времени. Учитывая то, что все три вещи из списка являются довольно важными для всего общества и для его оптимального существования, необходимо научиться моделировать этот поток.

Особенно актуальным является последний пункт приведённого списка, поскольку юзеры, не знающие простых основ компьютера, успевают их нереально задолбать, а зная параметры потока, можно спрогнозировать их количество.

Математическая модель простейшего потока требует от него нескольких свойств.

1. Стационарность. Это означает, что вероятность попадания того или иного числа событий на некоторый отрезок времени зависит только от длины участка и не зависит от того, где расположен этот участок.
2. Отсутствие последействия. Это означает следующее: если два промежутка времени не пересекаются, то количество событий, попавших на один из них, не зависит от количества событий, попавших на другой участок.
3. Ординарность.Поток является ординарным, если вероятность попадания на один достаточно малый отрезок времени двух и более событий пренебрежимо меньше его длины.

Заметим, что в зависимости от того, как происходит разбиение реальных событий на временные интервалы, может зависеть, является ли данный поток простейшим или нет.

Например, поток автомобилей на магистрали в сутки не является простейшим, т. к. он не является стационарным: днём автомобилей меньше, чем утром и вечером, в то время как тот же поток в час пик уже можно считать простейшим.

Главным здесь является то, что интересующее нас количество подчиняется дискретному Пуассоновскому распределению.

Алгоритм

Пусть нам задано значение параметра 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

Источник ^[1]