# Distributions on subsets of $\{1, 2, …, J\}$?

I'm wondering if there are any sorts of standard distributions on subsets of integers $\{1, 2, ..., J\}$. Equivalently, we could express this as a distribution on a $J$ length vector of binary outcomes, e.g. if $J = 5$ then $\{1, 3, 5\}$ corresponds to the vector $(1, 0, 1, 0, 1)$.

Ideally what I'm looking for is some distribution $\nu_\theta (\cdot)$, coming from a family indexed by a finite dimensional parameter $\theta$, that would distribute its mass in such a way two binary vectors $r_1$ and $r_2$ will have similar probability if they are "close" together, i.e. $r_1 = (0, 0, 1, 0, 1)$ and $r_2 = (0, 0, 1, 1, 1)$ have similar probabilities. Really, what I aim to do hopefully, is put a prior on $\theta$ such that if I know $\nu_\theta (r_1)$ is fairly large then $\nu_\theta (r_2)$ is probably large relative to vectors far away from $r_1$.

One strategy that comes to mind would be to put a metric or some other measure of dispersion on $d_\theta$ on $\{0, 1\}^J$ and then take $\nu_\theta (r) \propto \exp (-d_\theta (r, \mu))$, or something similar. An explicit example would be $\exp\left\{-\|r - \mu\|^2 / (2 \sigma^2)\right\}$ in analogy with the normal distribution. That's fine, but I'm hoping there is something standard and amenable to Bayesian analysis; with this I can't write down the normalizing constant.

• Sampling a subset is a basic problem in survey methodology. – Stéphane Laurent Oct 12 '12 at 5:53
• @Stephane sure, but I think my problem differs in that I have some additional desired structure that I would like my distribution to reflect. Perhaps phrasing the question in terms of subsets was a bad idea since I have a vague notion of distance working for me. – guy Oct 12 '12 at 13:35
• Did you mean to write "...then $v_\theta(r_2)$ is probably small..."? As far as the normalizing constant goes, consider using the Hamming distance for metric: for location-scale families of distributions, you can compute that constant as the sum of just $J+1$ terms. Moreover, all such families that meet your criteria can be described by just $J$ discrete parameters (for the location) and $J$ continuous parameters. – whuber Oct 12 '12 at 14:51
• @whuber no, I meant large. I want $\nu_\theta (\cdot)$ to distribute its mass around points that are close together. It probably would have been more apropos to phrase the question as putting a distribution on the verticies of a hypercube. I had considered Hamming distance (which I guess is the same as $L_1$ in my case); I would probably want to tweak it as $\sum \left|\frac{r_i - \mu_i}{\sigma_i}\right|$, and I guess would probably have to do some MCMC to sample from such a distribution. – guy Oct 13 '12 at 1:13
• Oh, I see now. But that's not what you originally said. For instance, in your characterization, if $\nu(r_1)$ is large, and $R$ is the set of vectors "far away" from $r_1$, and $r_2$ is any vector not in $R$, then $\nu(r_2)$ must also "probably" be large. But "not far away" and "close" don't mean exactly the same things. It would be simpler--and more internally consistent--to rephrase the condition as you did in your comment. But no, you don't need MCMC to sample from location-scale distributions based on Hamming distances: there are much more efficient ways. – whuber Oct 13 '12 at 14:08

You might favor location families based on Hamming distance, due to their richness, flexibility, and computational tractability.

### Notation and definitions

Recall that in a free finite-dimensional module $V$ with basis $\left(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_J\right)$, the Hamming distance $\delta_H$ between two vectors $\mathbf{v}=v_1 \mathbf{e}_1 + \cdots + v_J\mathbf{e}_J$ and $\mathbf{w}=w_1 \mathbf{e}_1 + \cdots + w_J\mathbf{e}_J$ is the number of places $i$ where $v_i \ne w_i$.

Given any origin $\mathbf{v}_0\in V$, the Hamming distance partitions $V$ into spheres $S_i(\mathbf{v}_0)$, $i=0, 1, \ldots, J$, where $S_i(\mathbf{v}_0) = \{\mathbf{w}\in V\ |\ \delta_H(\mathbf{w}, \mathbf{v}_0) = i\}$. When the ground ring has $n$ elements, $V$ has $n^J$ elements and $S_i(\mathbf{v})$ has $\binom{J}{i}\left(n-1\right)^i$ elements. (This follows immediately from observing that elements of $S_i(\mathbf{v})$ differ from $\mathbf{v}$ in exactly $i$ places--of which there are $\binom{J}{i}$ possibilities--and that there are, independently, $n-1$ choices of values for each place.)

Affine translation in $V$ acts naturally on its distributions to give location families. Specifically, when $f$ is any distribution on $V$ (which means little more than $f:V\to [0,1]$, $f(\mathbf{v})\ge 0$ for all $\mathbf{v} \in V$, and $\sum_{\mathbf{v}\in V}f(\mathbf{v})=1$) and $\mathbf{w}$ is any element of $V$, then $f^{(\mathbf{w})}$ is also a distribution where

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

for all $\mathbf{v}\in V$. A location family $\Omega$ of distributions is invariant under this action: $f\in \Omega$ implies $f^{(\mathbf{v})}\in \Omega$ for all $\mathbf{v}\in V$.

### Construction

This enables us to define potentially interesting and useful families of distributions by specifying their shapes at one fixed vector $\mathbf{v}$, which for convenience I will take to be $\mathbf{0} = (0,0,\ldots,0)$, and translating these "generating distributions" under the action of $V$ to obtain the full family $\Omega$. To achieve the desired property that $f$ should have comparable values at nearby points, simply require that property of all generating distributions.

To see how this works, let's construct the location family of all distributions that decrease with increasing distance. Because only $J+1$ Hamming distances are possible, consider any decreasing sequence of non-negative real numbers $\mathbf{a}$ = $0 \ne a_0 \ge a_1 \ge \cdots \ge a_J \ge 0$. Set

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

and define the function $f_\mathbf{a}:V\to [0,1]$ by

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

Then, as is straightforward to check, $f_\mathbf{a}$ is a distribution on $V$. Furthermore, $f_\mathbf{a} = f_{\mathbf{a}'}$ if and only if $\mathbf{a}'$ is a positive multiple of $\mathbf{a}$ (as vectors in $\mathbb{R}^{J+1}$). Thus, if we like, we may standardize $\mathbf{a}$ to $a_0=1$.

Accordingly, this construction gives an explicit parameterization of all such location-invariant distributions that are decreasing with Hamming distance: any such distribution is in the form $f_\mathbf{a}^{(\mathbf{v})}$ for some sequence $\mathbf{a} = 1 \ge a_1 \ge a_2 \ge \cdots \ge a_J \ge 0$ and some vector $\mathbf{v}\in V$.

This parameterization may allow for convenient specification of priors: factor them into a prior on the location $\mathbf{v}$ and a prior on the shape $\mathbf{a}$. (Of course one could consider a larger set of priors where location and shape and not independent, but this would be a more complicated undertaking.)

### Generating random values

One way to sample from $f_\mathbf{a}^{(\mathbf{v})}$ is by stages by factoring it into a distribution over the spherical radi and another distribution conditional on each sphere:

1. Draw an index $i$ from the discrete distribution on $\{0,1,\ldots,J\}$ given by the probabilities $\binom{J}{i}(n-1)^i a_i / A$, where $A$ is defined as before.

2. The index $i$ corresponds to the set of vectors differing from $\mathbf{v}$ in exactly $i$ places. Therefore, select those $i$ places out of the $\binom{J}{i}$ possible subsets, giving each equal probability. (This is just a sample of $i$ subscripts out of $J$ without replacement.) Let this subset of $i$ places be written $I$.

3. Draw an element $\mathbf{w}$ by independently selecting a value $w_j$ uniformly from the set of scalars not equal to $v_j$ for all $j\in I$ and otherwise set $w_j=v_j$. Equivalently, create a vector $\mathbf{u}$ by selecting $u_j$ uniformly at random from the nonzero scalars when $j\in I$ and otherwise setting $u_j=0$. Set $\mathbf{w} = \mathbf{v} + \mathbf{u}$.

Step 3 is unnecessary in the binary case.

### Example

Here is an R implementation to illustrate.

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
}


As an example of its use:

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


This took $0.2$ seconds to draw $10^4$ iid elements from the distribution $f_{\mathbf{a}}^{(\mathbf{v})}$ where $J=10$, $n=2$ (the binary case), $\mathbf{v}=(1,1,\ldots,1)$, and $\mathbf{a}=(2^{11},2^{10},\ldots,2^1)$ is exponentially decreasing.

(This algorithm does not require that $\mathbf{a}$ be decreasing; thus, it will generate random variates from any location family, not just the unimodal ones.)

• Thanks for this! Hamming distance in this case is just $L_1$ in $\mathbb R^J$ restricted to the cube verticies; in that context, Hamming distance is acting isotropically. Getting away from that I guess complicates these things because I have more than $J$ different values for my distance measure? Any general comments on this? – guy Oct 13 '12 at 20:51
• Yes: a choice of distance functions will depend on what the values in $\{1,2,\ldots,n\}$ represent. Because the question has been formulated abstractly, we really have nothing to go on for forming opinions about what would be good choices. The Hamming distance would be appropriate for nominal values and perhaps in other cases, too, but other distances might work better when there is an inherent sense of distance for the set $\{1,2,\ldots,n\}$. In the binary case $n=2$, it's hard to generalize Hamming distances: they're pretty general already. – whuber Oct 13 '12 at 21:14

A sample from a k-determinantal point process models a distribution over subsets that encourages diversity, such that similar items are less likely to occur together in the sample. Refer to K-determinantal point process sampling by Alex Kulesza, Ben Taskar.