Как отобрать усеченное многочленное распределение?

9

Мне нужен алгоритм для выборки усеченного полиномиального распределения. Это,

Икс~1Zп1Икс1...пКИксКИкс1!...ИксК!

где - нормализационная константа, имеет положительных компонент и . Я рассматриваю только значения в диапазоне .ZИксКΣИксязнак равноNИксaИксб

Как я могу попробовать этот усеченный мультиномиальный дистрибутив?

Примечание: см. Википедию для алгоритма выборки неусеченного многочленного распределения. Есть ли способ адаптировать этот алгоритм к усеченному распределению?

Унифицированная версия: более простая версия проблемы - взять все равными, . Если вы можете разработать алгоритм для выборки усеченного распределения по крайней мере в этом случае, пожалуйста, опубликуйте его. Хотя это и не общий ответ, это помогло бы мне решить другие практические проблемы на данный момент.пяпязнак равно1/К

becko
источник

Ответы:

9

Если я вас правильно понимаю, вы хотите значения из полиномиального распределения с вероятностями такими, что , однако вы хотите, чтобы распределение было усечено, поэтому для всех .p 1 , , p k i x i = n a ix ib i x iИкс1,...,ИксКп1,...,пКΣяИксязнак равноNaяИксябяИкся

Я вижу три решения (не так элегантно, как в неусеченном случае):

  1. Accept-отвергаем. Образец из неусеченного многочлена, примите образец, если он соответствует границам усечения, в противном случае отклоните и повторите процесс. Это быстро, но может быть очень неэффективно.
rtrmnomReject <- function(R, n, p, a, b) {
  x <- t(rmultinom(R, n, p))
  x[apply(a <= x & x <= b, 1, all) & rowSums(x) == n, ]
}
  1. Прямое моделирование. Образец в моде, который напоминает процесс генерирования данных, то есть образец отдельного шарика из случайной урны и повторяйте этот процесс, пока вы не выберете в общей сложности шариков, но при развертывании общего количества шариков из данной урны ( уже равно ) затем прекратите рисовать из такой урны. Я реализовал это в сценарии ниже.х я б яNИксябя
# single draw from truncated multinomial with a,b truncation points
rtrmnomDirect <- function(n, p, a, b) {
  k <- length(p)

  repeat {
    pp <- p         # reset pp
    x <- numeric(k) # reset x
    repeat {
      if (sum(x<b) == 1) { # if only a single category is left
        x[x<b] <- x[x<b] + n-sum(x) # fill this category with reminder
        break
      }
      i <- sample.int(k, 1, prob = pp) # sample x[i]
      x[i] <- x[i] + 1  
      if (x[i] == b[i]) pp[i] <- 0 # if x[i] is filled do
      # not sample from it
      if (sum(x) == n) break    # if we picked n, stop
    }
    if (all(x >= a)) break # if all x>=a sample is valid
    # otherwise reject
  }

  return(x)
}
  1. Алгоритм Метрополис. Наконец, третий и наиболее эффективный подход заключается в использовании алгоритма Метрополиса . Алгоритм инициализируется с помощью прямого моделирования (но может быть инициализирован по-разному) для рисования первого образца . В следующих шагах итеративно: значение предложения y = q ( X i - 1 ) принимается как X i с вероятностью f ( y ) / f ( X i - 1 ) , в противном случае X i - 1Икс1Yзнак равноQ(Икся-1)Иксяе(Y)/е(Икся-1)Икся-1значение берется в этом месте, где , В качестве предложения я использовал функцию q, которая принимает значение X i - 1 и случайным образом переходит от 0 к числу случаев и перемещает его в другую категорию.е(Икс)αΠяпяИкся/Икся!QИкся-1step
# draw R values
# 'step' parameter defines magnitude of jumps
# for Meteropolis algorithm
# 'init' is a vector of values to start with
rtrmnomMetrop <- function(R, n, p, a, b,
                          step = 1,
                          init = rtrmnomDirect(n, p, a, b)) {

  k <- length(p)
  if (length(a)==1) a <- rep(a, k)
  if (length(b)==1) b <- rep(b, k)

  # approximate target log-density
  lp <- log(p)
  lf <- function(x) {
    if(any(x < a) || any(x > b) || sum(x) != n)
      return(-Inf)
    sum(lp*x - lfactorial(x))
  }

  step <- max(2, step+1)

  # proposal function
  q <- function(x) {
    idx <- sample.int(k, 2)
    u <- sample.int(step, 1)-1
    x[idx] <- x[idx] + c(-u, u)
    x
  }

  tmp <- init
  x <- matrix(nrow = R, ncol = k)
  ar <- 0

  for (i in 1:R) {
    proposal <- q(tmp)
    prob <- exp(lf(proposal) - lf(tmp))
    if (runif(1) < prob) {
      tmp <- proposal
      ar <- ar + 1
    }
    x[i,] <- tmp
  }

  structure(x, acceptance.rate = ar/R, step = step-1)
}

Икс1step

n <- 500
a <- 50
b <- 125
p <- c(1,5,2,4,3)/15
k <- length(p)
x <- rtrmnomMetrop(1e4, n, p, a, b, step = 15)

cmb <- combn(1:k, 2)

par.def <- par(mfrow=c(4,5), mar = c(2,2,2,2))
for (i in 1:k)
  hist(x[,i], main = paste0("X",i))
for (i in 1:k)
  plot(x[,i], main = paste0("X",i), type = "l", col = "lightblue")
for (i in 1:ncol(cmb))
  plot(jitter(x[,cmb[1,i]]), jitter(x[,cmb[2,i]]),
       type = "l", main = paste(paste0("X", cmb[,i]), collapse = ":"),
       col = "gray")
par(par.def)

введите описание изображения здесь

п1пКa1знак равнознак равноaКб1знак равно...бКaябяп1»п2a1«a2б1«б2

Nпяпя


Рухин А.Л. (2007). Статистика нормального порядка и суммы геометрических случайных величин в задачах распределения лечения. Статистика и вероятностные буквы, 77 (12), 1312-1321.

Рухин А.Л. (2008). Правила остановки в задачах сбалансированного распределения: точное и асимптотическое распределение. Последовательный анализ, 27 (3), 277-292.

Тим
источник
Yязнак равноИкся-aямзнак равноN-ΣяaяYябя-aяИксaa
@becko, если вы сравните такой подход с описанным мной, вы увидите, что они дают разные решения.
Тим
Я не понимаю, чем они могут отличаться? Все, что я сделал, это смена переменных.
Беко
@becko ваша отправная точка это все x[i] >= a. Представьте, что вы бросили смещенную монету с вероятностью головы = 0,9. Вы бросаете монету, пока не получите как минимум 10 голов и 10 хвостов. В точке остановки у вас будет в среднем намного больше голов, чем хвостов. Начиная с x[1] = ... = x[k] = aозначает, что вы игнорируете тот факт, что отправные точки каждого из x[i]них разные из-за разных p[i].
Тим
Я понимаю вашу точку зрения. Единственное, что мне не нравится в вашем решении, это то, что я думаю, что оно может быть очень неэффективным для конкретного выбора параметров.
Бекко
1

Вот мои усилия в попытке перевести код Тима R на Python. Так как я потратил некоторое время на понимание этой проблемы и написание алгоритмов на Python, я подумал поделиться ими здесь на случай, если люди заинтересуются.

  1. Принять-отклонить алгоритм :
def sample_truncated_multinomial_accept_reject(k, pVec, a, b):
    x = list(np.random.multinomial(k, pVec, size=1)[0])
    h = [x[i] >= a[i] and x[i] <= b[i] for i in range(len(x))]
    while sum(h) < len(h):
        x = list(np.random.multinomial(k, pVec, size=1)[0])
        h = [x[i] >= a[i] and x[i] <= b[i] for i in range(len(x))]
    return x
  1. Прямое моделирование
def truncated_multinomial_direct_sampling_from_urn(k, pVec, a, b):
    n = len(pVec)
    while True:
        pp = pVec 
        x = [0 for _ in range(n)] 
        while True:
            if sum([x[h] < b[h] for h in range(n)])==1:
                indx = [h for h in range(n) if x[h] < b[h]][0]
                x[indx] = k - sum(x)
                break
            i = np.random.choice(n, 1, p=pp)[0]
            x[i] += 1
            if x[i] == b[i]:
                pp = [pp[j]/(1-pp[i]) for j in range(n)]
                pp[i] = 0 
            if sum(x) == k:
                break  
        if sum([x[h] < a[h] for h in range(n)]) == 0:
            break 
    return x 
  1. Алгоритм Метрополис
def compute_log_function(x, pVec, a, b):
    x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
    x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    if x_less_a or x_more_a or sum(x) != k:
        return float("-inf")
    return np.sum(np.log(pVec)*x - np.array([math.lgamma(h+1) for h in x]))
def sampling_distribution(original, pVec, a, b, step):
    x = copy.deepcopy(original) 
    idx = np.random.choice(len(x), 2, replace=False)
    u = np.random.choice(step, 1)[0]
    x[idx[0]] -= u
    x[idx[1]] += u
    x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
    x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    while x_less_a or x_more_a or sum(x) != k:
        x = copy.deepcopy(original)  
        idx = np.random.choice(len(x), 2, replace=False)
        u = np.random.choice(step, 1)[0]
        x[idx[0]] -= u
        x[idx[1]] += u
        x_less_a = sum([x[i] < a[i] for i in range(len(pVec))])
        x_more_a = sum([x[i] > b[i] for i in range(len(pVec))])
    return x 
def sample_truncated_multinomial_metropolis_hasting(k, pVec, a, b, iters, step=1):
    tmp=sample_truncated_multinomial_accept_reject(k, pVec, a, b)[0]
    step = max(2, step)
    for i in range(iters):
        proposal = sampling_distribution(tmp, pVec, a, b, step)
        if compute_log_function(proposal, pVec, a, b) == float("-inf"):
            continue             
        prob = np.exp(np.array(compute_log_function(proposal, pVec, a, b)) -\
                      np.array(compute_log_function(tmp, pVec, a, b)))
        if np.random.uniform() < prob:
            tmp = proposal 
        step -= 1 
    return tmp

Для полной реализации этого кода, пожалуйста, смотрите мой репозиторий Github по адресу

https://github.com/mohsenkarimzadeh/sampling

Мохсен Кискани
источник