Skip to main content
1 of 2
πr8
  • 801
  • 8
  • 30

Probability Distribution on permutations with factor structure

Say I define a probability measure over the symmetric group $S_n$ as follows:

  • I specify $n$ positive `potential' functions $G_i : \{1, 2, \cdots, N\} \to (0,\infty)$
  • I then set

$$\mathbb{P}(\sigma) = \frac{1}{Z} \prod_{i=1}^N G_i(\sigma (i))$$

for permutations $\sigma \in S_n$, where $Z$ is a normalisation constant.

Is there a name for measures of this form?

  • It's certainly not completely generic - there are only $\Theta(n^2)$ of these measures over $S_n$, so clearly not every distribution over permutations can be written in this form.
  • It seems like it should be able to express this condition in terms of some sort of conditional independence relations, but I haven't been able to work out how to do so.

If there isn't a specific name for this family of measures, but they do have some useful properties which would otherwise be useful, I'll also be happy to accept answers which indicate this.

πr8
  • 801
  • 8
  • 30