¿Distribuciones en subconjuntos de ?

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

Idealmente, lo que estoy buscando es alguna distribución , que provenga de una familia indexada por un parámetro dimensional finito , que distribuya su masa de tal manera que dos vectores binarios y tengan un valor similar probabilidad si están "juntos" juntos, es decir, y tienen probabilidades similares. Realmente, lo que espero hacer es poner un prior en modo que si sé que es bastante grande, entonces probablemente sea grande en relación con los vectores muy alejados de .$\nu_\theta (\cdot)$$\theta$$r_1$$r_2$$r_1 = (0, 0, 1, 0, 1)$$r_2 = (0, 0, 1, 1, 1)$$\theta$$\nu_\theta (r_1)$$\nu_\theta (r_2)$$r_1$

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

Puede favorecer a las familias de ubicación en función de la distancia de Hamming , debido a su riqueza, flexibilidad y capacidad de cálculo.

Notación y definiciones

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

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

La traducción afina en actúa naturalmente en sus distribuciones para dar familias de ubicaciones. Específicamente, cuando es cualquier distribución en (lo que significa poco más que , para todos y ) y es cualquier elemento de , entonces también es una distribución dónde$V$$f$$V$$f:V\to [0,1]$$f(\mathbf{v})\ge 0$$\mathbf{v} \in V$$\sum_{\mathbf{v}\in V}f(\mathbf{v})=1$$\mathbf{w}$$V$$f^{(\mathbf{w})}$

para todos . Un familias de de la distribución es invariante bajo esta acción: implica para todos .$\mathbf{v}\in V$ $\Omega$$f\in \Omega$$f^{(\mathbf{v})}\in \Omega$$\mathbf{v}\in V$

Construcción

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

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

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

Entonces, como es fácil de comprobar, es una distribución en . Además, si y solo si es un múltiplo positivo de (como vectores en ). Por lo tanto, si lo deseamos, podemos estandarizar a .$f_\mathbf{a}$$V$$f_\mathbf{a} = f_{\mathbf{a}'}$$\mathbf{a}'$$\mathbf{a}$$\mathbb{R}^{J+1}$$\mathbf{a}$$a_0=1$

Por consiguiente, esta construcción proporciona una parametrización explícita de todas esas distribuciones invariantes de ubicación que disminuyen con la distancia de Hamming: cualquier distribución de este tipo tiene la forma para alguna secuencia y algunos vector .$f_\mathbf{a}^{(\mathbf{v})}$$\mathbf{a} = 1 \ge a_1 \ge a_2 \ge \cdots \ge a_J \ge 0$$\mathbf{v}\in V$

Esta parametrización puede permitir una conveniente especificación de los anteriores: factorizarlos en un prior en la ubicación y un prior en la forma . (Por supuesto, uno podría considerar un conjunto mayor de antecedentes donde la ubicación y la forma no son independientes, pero esta sería una tarea más complicada).$\mathbf{v}$$\mathbf{a}$

Generando valores aleatorios

Una forma de muestras de es por etapas factorizándolas en una distribución sobre el radiofrecuencia esférica y otra distribución condicional en cada esfera:$f_\mathbf{a}^{(\mathbf{v})}$

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

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

3. Dibuje un elemento seleccionando independientemente un valor uniformemente del conjunto de escalares que no sea igual a para todos y establezca . De manera equivalente, cree un vector seleccionando uniformemente al azar de los escalares distintos de cero cuando y estableciendo . Establezca .$\mathbf{w}$$w_j$$v_j$$j\in I$$w_j=v_j$$\mathbf{u}$$u_j$$j\in I$$u_j=0$$\mathbf{w} = \mathbf{v} + \mathbf{u}$

El paso 3 es innecesario en el caso binario.

Ejemplo

Aquí hay una Rimplementació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ó segundos para dibujar elementos iid de la distribución donde , (el caso binario), y está disminuyendo exponencialmente.$0.2$$10^4$$f_{\mathbf{a}}^{(\mathbf{v})}$$J=10$$n=2$$\mathbf{v}=(1,1,\ldots,1)$$\mathbf{a}=(2^{11},2^{10},\ldots,2^1)$

(Este algoritmo no requiere que esté disminuyendo; por lo tanto, generará variaciones aleatorias de cualquier familia de ubicaciones, no solo las unimodales).$\mathbf{a}$

Una muestra de un proceso de punto k-determinante modela una distribución sobre subconjuntos que fomenta la diversidad, de modo que es menos probable que elementos similares ocurran juntos en la muestra. Consulte el muestreo del proceso del punto K-determinante por Alex Kulesza, Ben Taskar.