Симулация на процеса на Поасон

Един от най-важните процеси, наблюдавани в природата, е процесът на Поасон. Ето защо е важно да се разбере как могат да се моделират такива процеси. Методите за моделиране се различават в зависимост от вида на точковия процес на Поасон, т.е. пространството, в което протича процесът, и хомогенността или хетерогенността на процеса. Няма да се интересуваме от развитието на потока на Поасон или важните му приложения в различни области. За да запази този материал интересен, на читателя силно се препоръчва да прочете съответните раздели във Feller (1965) и Sinlar (1975) за основна теория и някои раздели в Trivedi (1982) за ИТ приложения.

На първата стъпка дефинираме процес на Поасон върху [0;+∞). Процесът е напълно определен от група случайни събития, които се случват в определени произволни времена 0 0. Вижте, например, Feller (1965). По този начин разпределението на Поасон възниква съвсем естествено.

Предишната концепция може да се обобщи до R d . Нека A е някакво подмножество на R d и N е случайна променлива, която приема само цели числа. Нека X1. XN е набор от произволни вектори, които приемат стойност в A. Тогава казваме, че Xi дефинира равномерен или хомогенен процес на Поасон върху A, ако

За всяко крайно множество от по двойки несвързани подмножества на множеството A Аi с краен размер, събитието N(A1). N(Ak са независими
За всяко Борелово подмножество B на множество A, разпределението N(B) зависи само от размера на множество B

Бележка на преводача: Би било по-добре да се използва думата „мярка“, но за тези, които не обичат математиката, тогава ще трябва да обясняват дузина страници или дори повече.

Отново тези предположения предполагат,че всички N(B) са разпределени според закона P(λVol(B)) за някакво неотрицателно λ, което ще наречем интензитет или параметър на интензитета на равномерен процес на Поасон върху A. Примери за такива процеси във високомерно евклидово пространство включват бактерии върху петриево блюдо и сцени на убийство в Хюстън.

Симулация на хомогенни поасонови процеси

Ако трябва да симулираме равномерен процес на Поасон върху набор A, принадлежащ на Rd, тогава трябва да генерираме някакъв брой произволни вектори Xi от A. По теорема 1.1 това може да стане по следния начин:

Генериране на Поасонова случайна променлива N с параметър λVol(A) Генериране на независими случайни вектори X1. XN равномерно разпределен върху A RETURN X1. XN

За генериране на стойността N е безполезно да използваме алгоритъм със средна сложност O(1), защото в края на алгоритъма ще прекараме поне Ω(n) операции. Следователно, ако се използва този алгоритъм, е силно препоръчително да се генерира Поасонова случайна променлива с много прост алгоритъм (с нарастване на средното време като O(λ)). За някои набори A могат да се използват други методи, които не изискват изрично генериране на случайна променлива на Поасон. Има три случая, които използваме, за да илюстрираме това.

За да направим това, имаме нужда от интересна връзка между процеса на Поасон и експоненциалното разпределение.

Теорема 1.2 предлага следния метод за моделиране на равномерен процес на Поасон върху A=[0;+∞)

T = 0 (спомагателна променлива за актуализиране на "време") k = 0 (инициализиране на брояча на събития) ПОВТОРЕНИЕ Генериране на експоненциална произволна стойност E k = k + 1 T = T + E/λ T[k] = T ДО НЕвярно (това е безкраен цикъл; по желание можете да добавите критерий за спиране)

Този алгоритъм е лесен за изпълнение, тъй като не е необходимо да се генерират Поасонови случайни променливи. За други прости множества A има тривиални обобщения на теорема 1.2. Например, когато A=[0,t]x[0,1], където t може да бъде безкрайност, 0 T = 0 (допълнителна променлива) k = 0 (брояч) ПОВТОРЕНИЕ Генериране на експоненциална случайна променлива E k = k+1 T = T + InvΛ(E+Λ(T)), (InvΛ е обратното на Λ) T[ k] = T ДО Невярно

Пример 1.2. Хомогенен процес на Поасон

За специалния случай λ(t)=λ, Λ(t)=λt е лесно да се види, че InvΛ(E+Λ(T))=T+E/λ, което води отново до експоненциалния метод.

За да симулираме сутрешния поток от автомобили преди час пик, понякога можем да вземем λ(t)=t, след това Λ(t)=t^2/2 и да получим стъпката

Ако функцията на интензитета може да бъде представена като сума от функциите на интензитета, т.е.

0 Генериране на T[1,1]. T[n,1] за n процеси на Поасон и съхранете тези стойности заедно с индексите на съответните процеси в таблица T = 0 (текущо време) k = 0 ПОВТОРЕНИЕ Намерете минималния елемент T[i,j] в таблицата и го изтрийте k = k + 1 T[k] = T[i,j] Генерирайте T[i,j+1] и вмъкнете в таблицата ДО НЕвярно

Третият общ принцип е принципът на изтъняване (Lewis and Schaedler, 1979). Подобно на това, което се случва при метода на отклонението, ние приемаме, че има функция на интензитета на доминиращата светлина λ(t) T = 0 k = 0 REPEAT Генериране на Z, първото събитие в нееднороден процес на Поасон с функция на интензитет μ, което се случва след време T. Присвояване на T = Z Генериране на равномерно разпределенвърху [0;1] случайна променлива U АКО U ТОГАВА k = k + 1, X[k] = T ДОКАТО Невярно

Твърди се, че така генерираната последователност Xk образува нехомогенен процес на Поасон с функция на интензитета λ. Обърнете внимание, че сме взели нехомогенен процес 0 T = 0 k = 0 ПОВТОРЕНИЕ Генериране на експоненциална случайна променлива E с параметър 1 T = T + E/(2λ) Генериране на случайна променлива равномерна на [0;1] U АКО U ТОГАВА k = k + 1, X[k] = T ДО НЕвярно

Излишно е да казвам, че тук може да се използва теоремата за двама полицаи, за да се избегне изчисляването на косинуса в повечето случаи.

Последна дума за ефективността на алгоритъма, когато нехомогенен процес на Поасон е моделиран върху множеството [0,t]. Средният брой събития, които са необходими от доминиращия процес, е равен, докато средният брой върнати случайни променливи е Съотношението на средните може да се разглежда като обективна мярка за ефективност, сравнима в духа на константата на отклонение в метода на стандартното отклонение. Имайте предвид, че не можем да използваме средната стойност на съотношението, тъй като по принцип то би било равно на безкрайност поради положителната вероятност нито една от стойностите да не се върне.

Hardcore conf в C++. Каним само професионалисти.