Distribuciones en subconjuntos de $\{1, 2, ..., J\}$ ?

Question

Me pregunto si hay algún tipo de distribución estándar en subconjuntos de enteros $\{1, 2, ..., J\}$ . De forma equivalente, podríamos expresarlo como una distribución en un $J$ vector de longitud de resultados binarios, por ejemplo, si $J = 5$ entonces $\{1, 3, 5\}$ corresponde al vector $(1, 0, 1, 0, 1)$ .

Idealmente lo que estoy buscando es alguna distribución $\nu_\theta (\cdot)$ que proviene de una familia indexada por un parámetro de dimensión finita $\theta$ que distribuiría su masa de tal manera que dos vectores binarios $r_1$ y $r_2$ tendrán una probabilidad similar si están "cerca", es decir $r_1 = (0, 0, 1, 0, 1)$ y $r_2 = (0, 0, 1, 1, 1)$ tienen probabilidades similares. En realidad, lo que pretendo hacer, con suerte, es poner una prioridad en $\theta$ tal que si sé $\nu_\theta (r_1)$ es bastante grande, entonces $\nu_\theta (r_2)$ es probablemente grande en relación con los vectores alejados de $r_1$ .

Una estrategia que se me ocurre sería poner una métrica o alguna otra medida de dispersión en $d_\theta$ en $\{0, 1\}^J$ y luego tomar $\nu_\theta (r) \propto \exp (-d_\theta (r, \mu))$ o algo similar. Un ejemplo explícito sería $\exp\left\{-\|r - \mu\|^2 / (2 \sigma^2)\right\}$ por analogía con la distribución normal. Eso está bien, pero espero que haya algo estándar y susceptible de análisis bayesiano; con esto no puedo escribir la constante normalizadora.

Answer 1

Podrías favorecer a las familias de localización basadas en la distancia de Hamming debido a su riqueza, flexibilidad y facilidad de cálculo.

---

Notación y definiciones

Recordemos que en un módulo libre de dimensión finita $V$ con base $\left(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_J\right)$ El Distancia Hamming $\delta_H$ entre dos vectores $\mathbf{v}=v_1 \mathbf{e}_1 + \cdots + v_J\mathbf{e}_J$ y $\mathbf{w}=w_1 \mathbf{e}_1 + \cdots + w_J\mathbf{e}_J$ es el número de plazas $i$ donde $v_i \ne w_i$ .

Dado cualquier origen $\mathbf{v}_0\in V$ , las particiones de la distancia Hamming $V$ en esferas $S_i(\mathbf{v}_0)$ , $i=0, 1, \ldots, J$ , donde $S_i(\mathbf{v}_0) = \{\mathbf{w}\in V\ |\ \delta_H(\mathbf{w}, \mathbf{v}_0) = i\}$ . Cuando el anillo de tierra tiene $n$ elementos, $V$ tiene $n^J$ elementos y $S_i(\mathbf{v})$ tiene $\binom{J}{i}\left(n-1\right)^i$ elementos. (Esto se deduce inmediatamente de la observación de que los elementos de $S_i(\mathbf{v})$ difieren de $\mathbf{v}$ exactamente $i$ lugares, de los cuales hay $\binom{J}{i}$ posibilidades y que hay, independientemente, $n-1$ de valores para cada lugar).

Traducción afín en $V$ actúa de forma natural sobre sus distribuciones para dar familias de localización. En concreto, cuando $f$ es cualquier distribución en $V$ (que significa poco más que $f:V\to [0,1]$ , $f(\mathbf{v})\ge 0$ para todos $\mathbf{v} \in V$ y $\sum_{\mathbf{v}\in V}f(\mathbf{v})=1$ ) y $\mathbf{w}$ es cualquier elemento de $V$ entonces $f^{(\mathbf{w})}$ es también una distribución en la que

$$f^{(\mathbf{w})}(\mathbf{v}) = f(\mathbf{v}-\mathbf{w})$$

para todos $\mathbf{v}\in V$ . A ubicación familia $\Omega$ de las distribuciones es invariante bajo esta acción: $f\in \Omega$ implica $f^{(\mathbf{v})}\in \Omega$ para todos $\mathbf{v}\in V$ .

Construcción

Esto nos permite definir familias de distribuciones potencialmente interesantes y útiles especificando sus formas en un vector fijo $\mathbf{v}$ que por conveniencia tomaré como $\mathbf{0} = (0,0,\ldots,0)$ y traduciendo estas "distribuciones generadoras" bajo la acción de $V$ para obtener la familia completa $\Omega$ . Para conseguir la propiedad deseada que $f$ debe tener valores comparables en puntos cercanos, simplemente se requiere esa propiedad de todas las distribuciones generadoras.

Para ver cómo funciona esto, construyamos la familia de localización de todas las distribuciones que disminuyen con el aumento de la distancia. Dado que sólo $J+1$ Las distancias de Hamming son posibles, considere cualquier secuencia decreciente de números reales no negativos $\mathbf{a}$ = $0 \ne a_0 \ge a_1 \ge \cdots \ge a_J \ge 0$ . Establecer

$$A = \sum_{i=0}^J (n-1)^i\binom{J}{i} a_i$$

y definir la función $f_\mathbf{a}:V\to [0,1]$ por

$$f_\mathbf{a}(\mathbf{v}) = \frac{a_{\delta_H(\mathbf{0},\mathbf{v})}}{A}.$$

Entonces, como es sencillo de comprobar, $f_\mathbf{a}$ es una distribución en $V$ . Además, $f_\mathbf{a} = f_{\mathbf{a}'}$ si y sólo si $\mathbf{a}'$ es un múltiplo positivo de $\mathbf{a}$ (como vectores en $\mathbb{R}^{J+1}$ ). Así, si queremos, podemos normalizar $\mathbf{a}$ a $a_0=1$ .

En consecuencia, esta construcción da una parametrización explícita de todas las distribuciones invariantes de localización que son decrecientes con la distancia de Hamming: cualquier distribución de este tipo tiene la forma $f_\mathbf{a}^{(\mathbf{v})}$ para alguna secuencia $\mathbf{a} = 1 \ge a_1 \ge a_2 \ge \cdots \ge a_J \ge 0$ y algún vector $\mathbf{v}\in V$ .

Esta parametrización puede permitir una especificación conveniente de las prioridades: factorizarlas en una prioridad sobre la ubicación $\mathbf{v}$ y una prioridad en la forma $\mathbf{a}$ . (Por supuesto, se podría considerar un conjunto más amplio de priores en el que la ubicación y la forma no fueran independientes, pero esto sería una empresa más complicada).

Generación de valores aleatorios

Una forma de tomar muestras de $f_\mathbf{a}^{(\mathbf{v})}$ es por etapas mediante la factorización en una distribución sobre el radio esférico y otra distribución condicionada a cada esfera:

1. Dibujar un índice $i$ de la distribución discreta en $\{0,1,\ldots,J\}$ dada por las probabilidades $\binom{J}{i}(n-1)^i a_i / A$ , donde $A$ se define como antes.

2. El índice $i$ corresponde al conjunto de vectores que difieren de $\mathbf{v}$ exactamente $i$ lugares. Por lo tanto, seleccione aquellos $i$ lugares fuera de la $\binom{J}{i}$ posibles subconjuntos, dando a cada uno la misma probabilidad. (Esto es sólo una muestra de $i$ subíndices de $J$ sin sustitución). Dejemos que este subconjunto de $i$ lugares se escriba $I$ .

3. Dibujar un elemento $\mathbf{w}$ seleccionando independientemente un valor $w_j$ uniformemente del conjunto de escalares no iguales a $v_j$ para todos $j\in I$ y, en caso contrario, establecer $w_j=v_j$ . De manera equivalente, cree un vector $\mathbf{u}$ seleccionando $u_j$ uniformemente al azar de la no cero escalares cuando $j\in I$ y en caso contrario establecer $u_j=0$ . Establecer $\mathbf{w} = \mathbf{v} + \mathbf{u}$ .

El paso 3 es innecesario en el caso binario.

---

Ejemplo

Aquí hay un R implementación para ilustrar.

rHamming <- function(N=1, a=c(1,1,1), n=2, origin) {
  # Draw N random values from the distribution f_a^v where the ground ring
  # is {0,1,...,n-1} mod n and the vector space has dimension j = length(a)-1.
  j <- length(a) - 1
  if(missing(origin)) origin <- rep(0, j)

  # Draw radii `i` from the marginal distribution of the spherical radii.
  f <- sapply(0:j, function(i) (n-1)^i * choose(j,i) * a[i+1])
  i <- sample(0:j, N, replace=TRUE, prob=f)

  # Helper function: select nonzero elements of 1:(n-1) in exactly i places.
  h <- function(i) {
    x <- c(sample(1:(n-1), i, replace=TRUE), rep(0, j-i))
    sample(x, j, replace=FALSE)
  }

  # Draw elements from the conditional distribution over the spheres
  # and translate them by the origin.
  (sapply(i, h) + origin) %% n
}

Como ejemplo de su uso:

test <- rHamming(10^4, 2^(11:1), origin=rep(1,10))
hist(apply(test, 2, function(x) sum(x != 0)))

Esto tomó $0.2$ segundos para dibujar $10^4$ elementos iid de la distribución $f_{\mathbf{a}}^{(\mathbf{v})}$ donde $J=10$ , $n=2$ (el caso binario), $\mathbf{v}=(1,1,\ldots,1)$ y $\mathbf{a}=(2^{11},2^{10},\ldots,2^1)$ es exponencialmente decreciente.

(Este algoritmo no requiere que $\mathbf{a}$ sea decreciente; por lo tanto, generará variantes aleatorias de cualquier familia de ubicaciones, no sólo las unimodales).

Answer 2

Una muestra de un proceso puntual k-determinante modela una distribución sobre subconjuntos que fomenta la diversidad, de manera que es menos probable que los elementos similares aparezcan juntos en la muestra. Consulte K-determinantal point process sampling de Alex Kulesza, Ben Taskar.