Вибірка за значимістю

Розглянемо оцінку ймовірності шляхом моделювання ${\displaystyle p_{t}\,}$ події ${\displaystyle X\geq t}$, де ${\displaystyle X}$ є випадковою величиною з розподілом ${\displaystyle F}$ і функцією густини ймовірності ${\displaystyle f(x)=F'(x)\,}$. Незалежна однаково розподілена (i.i.d) послідовність ${\displaystyle X_{i}\,}$ довжини ${\displaystyle K}$ генерується з розподілу ${\displaystyle F}$, та підраховується число ${\displaystyle k_{t}}$ випадкових величин, які лежать вище порога ${\displaystyle t}$. Випадкова величина ${\displaystyle k_{t}}$ характеризується біноміальним розподілом

${\displaystyle P(k_{t}=k)={K \choose k}p_{t}^{k}(1-p_{t})^{K-k},\,\quad \quad k=0,1,\dots ,K.}$

Це демонструє, що ${\displaystyle \operatorname {E} [k_{t}/K]=p_{t}}$ і ${\displaystyle \operatorname {var} [k_{t}/K]=p_{t}(1-p_{t})/K}$, тож у межі ${\displaystyle K\to \infty }$ ми можемо отримати ${\displaystyle p_{t}}$. Зауважимо, що дисперсія є малою, якщо ${\displaystyle p_{t}\approx 1}$. Вибірка за значимістю пов'язана з визначенням і використанням альтернативної функції щільності ${\displaystyle f_{*}\,}$ (для ${\displaystyle X}$), що зазвичай називають густиною зміщення для імітаційного експерименту. Ця щільність дозволяє події ${\displaystyle {X\geq t\ }}$ зустрічатися частіше, тому довжина послідовності ${\displaystyle K}$ зменшується для даної дисперсії оцінки. Як варіант, для даного ${\displaystyle K\,}$використання густини зміщення призводить до меншої дисперсії в порівнянні зі звичайною оцінкою Монте-Карло. Використовуючи визначення ${\displaystyle p_{t}}$, ми можемо представити ${\displaystyle f_{*}}$ наступним чином:

${\displaystyle {\begin{aligned}p_{t}&={E}[1(X\geq t)]\\[6pt]&=\int 1(x\geq t){\frac {f(x)}{f_{*}(x)}}f_{*}(x)\,dx\\[6pt]&=E_{*}[1(X\geq t)W(X)]\end{aligned}}}$

де

${\displaystyle W(\cdot )\equiv {\frac {f(\cdot )}{f_{*}(\cdot )}}}$

є коефіцієнтом правдоподібності і називається ваговою функцією. Остання рівність у наведеному вище рівнянні мотивує оцінювача

${\displaystyle {\hat {p}}_{t}={\frac {1}{K}}\,\sum _{i=1}^{K}1(X_{i}\geq t)W(X_{i}),\,\quad \quad X_{i}\sim f_{*}}$

Це рівняння є незміщеною оцінкою вибірки за значимістю ${\displaystyle p_{t}\,}$. Тобто процедура оцінки полягає у створенні i.i.d вибірок з ${\displaystyle f_{*}\,}$ і для кожної вибірки, що перевищує ${\displaystyle t\,}$, оцінка збільшується на вагу ${\displaystyle W\,}$, оцінену за значенням вибірки. Результати усереднюються за ${\displaystyle K\,}$ випробуваннями. Легко показати, що дисперсія оцінки вибірки за значимістю є

${\displaystyle {\begin{aligned}\operatorname {var} _{*}{\widehat {p}}_{t}&={\frac {1}{K}}\operatorname {var} _{*}[1(X\geq t)W(X)]\\[5pt]&={\frac {1}{K}}\left\{{E_{*}}[1(X\geq t)^{2}W^{2}(X)]-p_{t}^{2}\right\}\\[5pt]&={\frac {1}{K}}\left\{{E}[1(X\geq t)W(X)]-p_{t}^{2}\right\}\end{aligned}}}$

Тепер проблема застосування вибірки за значимістю зосереджується на пошуку густини зміщення ${\displaystyle f_{*}\,}$ таким чином, щоб дисперсія оцінки вибірки за значимістю була меншою за дисперсію загальної оцінки Монте-Карло. Деяка функція густини зміщення, що мінімізує дисперсію, а за певних умов зводить її до нуля, називаюється оптимальною функцією густини зміщення.

Хоча існує багато видів методів зміщення, наступні два методи є найбільш широко використовуваними при застосуванні вибірки за значимістю.

Перенесення маси ймовірності в область події ${\displaystyle {X\geq t\ }}$ шляхом додатнього масштабування випадкової величини ${\displaystyle X\,}$ з числом, більшим за одиницю, призводить до збільшення дисперсії (також середнього) функції густини. Як наслідок, збільшується хвіст щільності, результатом чого є збільшення ймовірності події. Масштабування, ймовірно, є одним з найперших відомих методів зміщення, який широко використовується на практиці. Він простий у реалізації і зазвичай забезпечує консервативні переваги моделювання порівняно з іншими методами.

У вибірці за значимістю шляхом масштабування щільність моделювання вибирається як функція густини масштабованої випадкової величини ${\displaystyle aX\,}$, де зазвичай ${\displaystyle a>1}$ для оцінки ймовірності хвоста шляхом перетворення,

${\displaystyle f_{*}(x)={\frac {1}{a}}f{\bigg (}{\frac {x}{a}}{\bigg )}\,}$

і вагова функція є

${\displaystyle W(x)=a{\frac {f(x)}{f(x/a)}}\,}$

У той час як масштабування зміщує масу ймовірності в бажану область події, воно також штовхає масу в комплементарну область ${\displaystyle X<t\,}$ , що є небажаним. Якщо ${\displaystyle X\,}$ є сумою ${\displaystyle n\,}$ випадкові величини, розповсюдження маси відбувається в ${\displaystyle n\,}$ розмірний простір. Наслідком цього є зменшення значення приросту вибірки для збільшення ${\displaystyle n\,}$, і називається ефектом розмірності. Сучасною версією вибірки за значимістю шляхом масштабування є, наприклад, так звана сигма-масштабована вибірка (SSS), яка виконує множинний аналіз Монте-Карло (MC) з різними коефіцієнтами масштабування. На відміну від багатьох інших методів оцінки високої продуктивності (наприклад, відстаней у гіршому випадку (WCD)), SSS не сильно страждає від проблеми розмірності. Крім того, звернення до кількох виходів MC не призводить до зниження ефективності. З іншого боку, як WCD, SSS призначений лише для гаусових статистичних змінних, і на відміну від WCD, метод SSS не призначений для надання точних статистичних кутів. Іншим недоліком SSS є те, що робота MC з великомасштабними факторами може стати складною, наприклад, через проблеми зближення моделі та симулятора. Крім того, у SSS ми стикаємося з сильним компромісом зміщення та дисперсії: використовуючи великі масштабні коефіцієнти, ми отримуємо досить стабільні вихідні результати, але чим більш масштабні коефіцієнти, тим більша похибка зміщення. Якщо переваги SSS не мають великого значення, то інші методи є більш ефективними.

Інший простий і ефективний метод зміщення використовує трансляцію функції густини (і, отже, випадкової величини), щоб помістити більшу частину її ймовірної маси в область рідкісних подій. Трансляція не страждає від ефекту розмірності і успішно використовується в кількох програмах, пов'язаних із моделюванням цифрових комунікаційних систем. Вона часто забезпечує кращий приріст симуляції, ніж масштабування. При зміщенні за допомогою трансляції густина моделювання визначається як

${\displaystyle f_{*}(x)=f(x-c),\quad c>0\,}$

де ${\displaystyle c\,}$ є величиною зсуву і має бути обрана для мінімізації дисперсії оцінки вибірки за значимістю.

Фундаментальна проблема застосування вибірки за значимістю полягає в тому, що розробка хороших зміщених розподілів стає складнішою зі збільшенням складності системи. Складні системи — це системи з довгою пам'яттю, оскільки комплексна обробка кількох входів проводиться набагато легше. Ця розмірність або пам'ять може викликати проблеми трьох видів:

• довга пам'ять (сильні міжсимвольні інтерференції (ISI))
• невідома пам'ять (декодери Вітербі)
• можливо нескінченна пам'ять (адаптивні еквалайзери)

В принципі, ідеї вибірки за значимістю залишається незмінною в цих ситуаціях, але дизайн стає набагато складнішим. Успішний підхід до боротьби з цією проблемою, по суті, полягає в розбитті моделювання на кілька менших, більш чітко визначених підпроблем. Потім стратегії вибірки за значимістю використовуються для націлювання на кожну з простіших підпроблем. Прикладами методів розбиття моделювання є моделювання кондиціонування та помилки-події (EES) та регенеративного моделювання.

Щоб визначити успішні методи вибірки за значимістю, корисно мати можливість кількісно оцінити економію під час виконання за рахунок використання цього підходу. Зазвичай використовується показник продуктивності ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$, і це можна інтерпретувати як коефіцієнт прискорення, за допомогою якого оцінка вибірки за значимістю досягає такої ж точності, що й оцінка MC. Це має бути обчислено емпіричним шляхом, оскільки дисперсія оцінки навряд чи буде аналітично можлива, коли їх середнє значення нерозбірне. Іншими корисними поняттями для кількісної оцінки вибірки за значимістю є межі дисперсії та поняття асимптотичної ефективності. Одним із відповідних показників є так званий ефективний розмір вибірки (ESS).[3]

Дисперсія не є єдиною можливою функцією втрат для моделювання, а інші функції втрат, такі як середнє абсолютне відхилення, використовуються в різних статистичних програмах. Тим не менш, дисперсія є основною функцією втрат, яка розглядається в літературі, ймовірно, через використання дисперсії в довірчих інтервалах і в показнику ефективності ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$.

Супутнім питанням є той факт, що співвідношення ${\displaystyle \sigma _{MC}^{2}/\sigma _{IS}^{2}\,}$ переоцінює економію часу виконання через вибірку за значимістю, оскільки не включає додатковий обчислювальний час, необхідний для підрахування вагової функції. Отже, деякі люди оцінюють чисте покращення часу виконання різними способами. Можливо, більш серйозними витратами на вибірку за значимістю є час, необхідний для розробки та програмування техніки та аналітичного виведення бажаної вагової функції.

Коли різні допоміжні розподіли, ${\displaystyle g_{n}(x)}$, ${\displaystyle n=1,\ldots ,N,}$ спільно використовуються для опису вибірок ${\displaystyle x_{1},\ldots ,x_{N},}$ можна використовувати різні відповідні вагові функції (наприклад, див.[4][5][6][7]). В адаптивному налаштуванні допоміжні розподіли, ${\displaystyle g_{n,t}(x)}$, ${\displaystyle n=1,\ldots ,N,}$ та ${\displaystyle t=1,\ldots ,T,}$ оновлюються на кожній ітерації ${\displaystyle t}$ адаптивного алгоритму вибірки за значимістю. Отже, оскільки використовується сукупність щільностей пропозицій, можна використовувати декілька відповідних комбінацій схем вибірки та зважування.[8][9][10][11][12][13][14]