2
$\begingroup$

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.
    • A partial answer to this is that if you have a partition $\{1,2,\cdots,N\} = A \sqcup B$, then conditional on knowing that $\sigma(A) = A', \sigma(B) = B'$, you have that $\{\sigma(x)\}_{x \in A}$ and $\{\sigma(x)\}_{x \in B}$ are independent. So there's a sort of partition/refinement-based conditional independence structure, I suppose?

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.