Дискретная таблица направляющих (DGT)#

  • Требуется: вектор вероятностей (PV) или PMF вместе с конечной областью определения

  • Скорость:

    • Настройка: медленная (линейная с длиной вектора)

    • Сэмплирование: очень быстрое

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

  1. Сгенерировать случайное число U ~ U(0,1).

  2. Найти наименьшее целое I такое, что F(I) = P(X<=I) >= U.

Шаг (2) является ключевым. Использование последовательного поиска требует O(E(X)) сравнений, где E(X) — математическое ожидание распределения. Однако индексированный поиск использует таблицу-указатель для перехода к некоторому I' <= I, близкому к I, чтобы найти X за постоянное время. Действительно, ожидаемое количество сравнений сокращается до 2, когда таблица-указатель имеет тот же размер, что и вектор вероятностей (это значение по умолчанию). Для больших таблиц-указателей это число становится меньше (но всегда больше 1), для меньших таблиц оно становится больше.

С другой стороны, время настройки таблицы-гида составляет O(N), где N обозначает длину вектора вероятностей (для размера 1 предварительная обработка не требуется). Более того, для очень больших таблиц-гидов эффекты памяти могут даже снизить скорость алгоритма. Поэтому мы не рекомендуем использовать таблицы-гиды, которые более чем в три раза превышают заданный вектор вероятностей. Если нужно сгенерировать только несколько случайных чисел, (гораздо) меньшие размеры таблиц лучше. Размер таблицы-гида относительно длины заданного вектора вероятностей может быть установлен с помощью guide_factor параметр:

>>> import numpy as np
>>> from scipy.stats.sampling import DiscreteGuideTable
>>>
>>> pv = [0.18, 0.02, 0.8]
>>> urng = np.random.default_rng()
>>> rng = DiscreteGuideTable(pv, random_state=urng)
>>> rng.rvs()
2    # may vary

По умолчанию вектор вероятностей индексируется, начиная с 0. Однако это можно изменить, передав domain параметр. Когда domain при использовании в комбинации с PV, это приводит к перемещению распределения из (0, len(pv)) to (domain[0], domain[0] + len(pv)). domain[1] игнорируется в этом случае.

>>> rng = DiscreteGuideTable(pv, random_state=urng, domain=(10, 13))
>>> rng.rvs()
10   # may vary

Метод также работает, когда вместо вектора вероятностей задана PMF. В этом случае ограниченная (конечная) область также должна быть задана либо путём передачи domain параметр явно или путем предоставления support метод в объекте распределения:

>>> class Distribution:
...     def __init__(self, c):
...             self.c = c
...     def pmf(self, x):
...             return x ** self.c
...     def support(self):
...             return 0, 10
...
>>> dist = Distribution(2)
>>> rng = DiscreteGuideTable(dist, random_state=urng)
>>> rng.rvs()
9     # may vary

Примечание

Поскольку DiscreteGuideTable ожидает PMF с сигнатурой def pmf(self, x: float) -> float, сначала векторизует PMF с помощью np.vectorize и затем вычисляет её во всех точках области определения. Но если PMF уже векторизован, гораздо быстрее просто вычислить её в каждой точке области определения и передать полученный PV вместе с областью. Например, pmf методы дискретных распределений SciPy векторизованы, и PV можно получить, выполнив:

>>> from scipy.stats import binom
>>> from scipy.stats.sampling import DiscreteGuideTable
>>> dist = binom(10, 0.2)  # distribution object
>>> domain = dist.support()  # the domain of your distribution
>>> x = np.arange(domain[0], domain[1] + 1)
>>> pv = dist.pmf(x)
>>> rng = DiscreteGuideTable(pv, domain=domain)

Здесь требуется домен для перемещения распределения

Размер таблицы направляющих относительно вектора вероятностей может быть установлен с помощью guide_factor параметр. Большие таблицы подсказок приводят к более быстрому времени генерации, но требуют более дорогой настройки.

>>> guide_factor = 2
>>> rng = DiscreteGuideTable(pv, random_state=urng, guide_factor=guide_factor)
>>> rng.rvs()
2     # may vary

К сожалению, PPF редко доступен в замкнутой форме или слишком медленный, когда доступен. Пользователю нужно только предоставить вектор вероятностей, и PPF (обратная CDF) может быть вычислен с использованием ppf метод. Этот метод вычисляет (точный) PPF заданного распределения.

Например, для расчета PPF биномиального распределения с \(n=4\) и \(p=0.1\): мы можем настроить таблицу направлений следующим образом:

>>> import scipy.stats as stats
>>> n, p = 4, 0.1
>>> dist = stats.binom(n, p)
>>> rng = DiscreteGuideTable(dist, random_state=42)
>>> rng.ppf(0.5)
0.0

Пожалуйста, смотрите [1] и [2] для получения дополнительных сведений об этом методе.

Ссылки#

На этой странице