Como provar uma distribuição multinomial truncada?

Eu preciso de um algoritmo para provar uma distribuição multinomial truncada. Isso é,

\vec{x} \sim \frac{1}{Z} \frac{p_{1}^{x_{1}} \dots p_{k}^{x_{k}}}{x_{1}! \dots x_{k}!}

$\vec x \sim \frac{1}{Z} \frac{p_1^{x_1} \dots p_k^{x_k}}{x_1!\dots x_k!}$

onde é uma constante de normalização, tem componentes positivos e . Considero apenas valores de no intervalo . $Z$ $\vec x$ $k$ $\sum x_i = n$ $\vec{x}$ $\vec a \le \vec x \le \vec b$

Como posso provar essa distribuição multinomial truncada?

Nota: Consulte a Wikipedia para obter um algoritmo para amostrar uma distribuição multinomial não truncada. Existe uma maneira de adaptar esse algoritmo a uma distribuição truncada?

Versão uniforme: uma versão mais simples do problema é obter todos os iguais, . Se você pode criar um algoritmo para amostrar a distribuição truncada nesse caso, pelo menos, publique-a. Embora não seja a resposta geral, isso me ajudaria a resolver outros problemas práticos no momento. $p_i$ $p_i = 1/k$

algorithms multinomial random-generation becko
fonte

Respostas:

Se eu entendi corretamente, você deseja provar valores da distribuição multinomial com probabilidades tal forma que , mas você deseja que a distribuição seja truncada para para todos . $x_1,\dots,x_k$ $p_1,\dots,p_k$ $\sum_i x_i = n$ $a_i \le x_i \le b_i$ $x_i$

Vejo três soluções (nem tão elegantes quanto no caso não truncado):

Aceitar rejeitar. Amostra de multinomial não truncado, aceite a amostra se ela se encaixar nos limites do truncamento; caso contrário, rejeite e repita o processo. É rápido, mas pode ser muito ineficiente.

rtrmnomReject <- function(R, n, p, a, b) {
  x <- t(rmultinom(R, n, p))
  x[apply(a <= x & x <= b, 1, all) & rowSums(x) == n, ]
}

Simulação direta. Amostra de maneira semelhante ao processo de geração de dados, ou seja, amostra de mármore único de uma urna aleatória e repita esse processo até que você tenha amostrado bolinhas no total, mas conforme você implanta o número total de bolinhas de urna determinada ( já é igual a ) pare de desenhar a partir dessa urna. Eu implementei isso em um script abaixo. $n$ $x_i$ $b_i$

# 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)
}

Algoritmo de metrópole. Finalmente, a terceira e mais eficiente abordagem seria usar o algoritmo Metropolis . O algoritmo é inicializado usando simulação direta (mas pode ser inicializada de maneira diferente) para desenhar a primeira amostra . Nas etapas a seguir iterativamente: o valor da proposta é aceito como com probabilidade , caso contrário, o valor é considerado é o lugar, onde. Como proposta, usei a função que pega o valor e alterna aleatoriamente de 0 para o número de casos e a move para outra categoria. $X_1$ $y = q(X_{i-1})$ $X_i$ $f(y)/f(X_{i-1})$ $X_{i-1}$ $f(x) \propto \prod_i p_i^{x_i}/x_i!$ $q$ $X_{i-1}$ step

# 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)
}

O algoritmo começa em e depois vagueia pelas diferentes regiões de distribuição. É obviamente mais rápido que os anteriores, mas você deve se lembrar que se você o usar para amostrar um pequeno número de casos, poderá acabar com desenhos próximos um do outro. Outro problema é que você precisa decidir sobre o tamanho, ou seja, quão grandes os saltos o algoritmo deve fazer - pequenos demais podem levar a movimentos lentos, grandes demais podem levar a muitas propostas inválidas e a rejeitá-las. Você pode ver exemplos de seu uso abaixo. Nas plotagens, é possível ver: densidades marginais na primeira linha, plotagens de traços na segunda linha e plotagens mostrando saltos subsequentes para pares de variáveis. $X_1$ step

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)

O problema com a amostragem dessa distribuição é que descreve uma estratégia de amostragem muito ineficiente em geral. Imagine que e , e estão próximos de '; nesse caso, você deseja provar amostras de categorias com probabilidades diferentes, mas espera resultados semelhantes. frequências no final. Em casos extremos, imagine a distribuição de duas categorias em que e , $p_1 \ne \dots \ne p_k$ $a_1 = \dots = a_k$ $b_1 = \dots b_k$ $a_i$ $b_i$ $p_1 \gg p_2$ $a_1 \ll a_2$ $b_1 \ll b_2$ , nesse caso, você espera que algo muito raro aconteça (exemplo da vida real dessa distribuição seria o pesquisador que repete a amostragem até encontrar a amostra que seja consistente com sua hipótese, por isso tem mais a ver com trapaça do que com amostra aleatória) .

A distribuição é muito menos problemática se você a definir como Rukhin (2007, 2008), onde você casos para cada categoria, ou seja, amostra proporcionalmente a 's. $np_i$ $p_i$

Rukhin, AL (2007). Estatísticas de ordem normal e somas de variáveis geométricas aleatórias em problemas de alocação de tratamento. Estatísticas e letras de probabilidade, 77 (12), 1312-1321.

Rukhin, AL (2008). Parando regras em problemas de alocação equilibrada: distribuições exatas e assintóticas. Análise Sequencial, 27 (3), 277-292.

Tim
fonte

Rejeitar amostras inválidas pode ser muito lento. Provavelmente é mais simples fazer uma tradução, , . Dessa forma, você só tem o limite superior, com se preocupar. Em seguida, você pode remover linha onde você rejeitar a amostra se o é violada (se pode conceber valores de onde esta rejeição seria muito ineficiente)

y_{i} = x_{i} - a_{i}

$y_i = x_i - a_i$

m = n - \sum_{i} a_{i}

$m = n - \sum_i a_i$

y_{i} \leq b_{i} - a_{i}

$y_i \le b_i - a_i$

x \geq a

$x \ge a$

a

$a$

Becko

@ Becko se você comparar essa abordagem com a descrita por mim, verá que eles oferecem soluções diferentes .

Tim

Eu não entendo como eles podem ser diferentes? Tudo o que fiz foi uma mudança de variáveis.

Becko

@ Becko, seu ponto de partida é tudo x[i] >= a. Imagine que você jogou uma moeda tendenciosa com probabilidade de cabeça = 0,9. Você joga a moeda até obter pelo menos 10 caras e 10 caudas. No ponto de parada, você terá, em média, muito mais caras do que caudas. Iniciar em x[1] = ... = x[k] = asignifica que você ignora o fato de que os pontos de partida de cada um x[i]são diferentes por causa dos diferentes p[i].

Tim

Eu entendo o seu ponto. A única coisa que não gosto na sua solução é que acho que pode ser muito ineficiente para escolhas específicas dos parâmetros.

Becko

Aqui está o meu esforço na tentativa de traduzir o código R de Tim para Python. Como passei algum tempo entendendo esse problema e codificando os algoritmos em Python, pensei em compartilhá-los aqui, caso as pessoas estejam interessadas.

Algoritmo Accept-Reject :

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

Simulação direta

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

Algoritmo de metrópole

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

Para uma implementação completa desse código, consulte meu repositório do Github em

https://github.com/mohsenkarimzadeh/sampling

Mohsen Kiskani
fonte