I would like to put prior probabilities over permutation matrices $\mathbf{P}$

$$\vec A = \mathbf{P} \vec B$$

where $\vec A$ and $\vec B$ are the same random vectors up to a permutation (hence the equality above).

The motivation for the problem is to learn from data the distribution of ways that data gets reordered by a process.

I have another soft constraint. I don't want the priors to be really strong. I don't mind if some permutation matrices a slightly more likely than others, but I don't want the model to strongly prefer specific permutation matrices in the priors. Sorry that is vague, but I couldn't quite define exactly how weak is weak enough.


Bernoulli Entries

My first naive attempt is to assign that $p_{ij} \sim \text{Binomial}\left(1, \frac{1}{2} \right)$, but this ignores the constraint every row and column has only one non-zero value.

Correlated Entries

A next step could be to model that deeper dependence using a multivariate normal and a sigmoid (or similar) to predict the probability parameters for the binomial. But this still only probabilistically would give me permutation matrices. A quickly-contrived first approximation of this approach might look like this:

$$p_{ij} \sim \text{Binomial}\left(1, \theta_{i,j} \right)$$

$$\theta_{i,j} := \text{sigmoid}(\tau_{ij})$$

($\tau_{ij}$ is an element of a random matrix $\mathbf{T}_{n \times n}$)

$$\mathbf{T}_{n \times n} \sim \text{MvNormal}(\mathbf{M}_{n \times n}, \mathbf{\Sigma}_{n^2 \times n^2})$$

Ordinal Regression

It occurred to me that I could do an ordered regression where I ordered logit transform both the predictor and predicted variables, but I am unsure how that gets me the permutation matrices I want at the end.


How can I put priors on the permutation matrices so that the row/column constraint is necessarily satisfied?

  • 1
    $\begingroup$ If you want a low-information prior (depending on what you're doing with the prior/how the prior is entering into your calculations), you could put a uniform prior on them, since it would then just be $\frac{1}{m}$ (where $m$ counts the number of possible $P$'s) - which is just a scaling constant. If you explain where that causes you a difficulty, that might clarify what the issue really is. The problem I expect would tend to be more with "how do I label my permutations" to keep track of the posterior probabilities which isn't really a problem with the prior ... ctd $\endgroup$
    – Glen_b
    Aug 8, 2023 at 22:47
  • 1
    $\begingroup$ ctd ... though if you want a non-uniform prior, you run into the labelling issue at the "specify the prior" stage. $\endgroup$
    – Glen_b
    Aug 8, 2023 at 22:48
  • 1
    $\begingroup$ It is efficient for keeping track of all the permutations that have been generated. $\endgroup$
    – whuber
    Aug 9, 2023 at 15:07
  • 1
    $\begingroup$ @whuber Ah, I see. So if I take 2000 samples from the posterior I need only store no more than 2000 distinct integers. That is feasible. I'll have to think more on how to change my PyMC code, but that isn't a stats question. $\endgroup$
    – Galen
    Aug 9, 2023 at 15:17
  • 2
    $\begingroup$ Note that if you're considering sample sizes on the order of 2000 and $n$ greater than $10$ or so, you don't have to worry about detecting collisions: they will be inconsequentially rare. The only data structure you will need then is an array (of fixed, predictable size). Other data structures might be more useful and efficient depending on how you plan to analyze the posterior distribution, but might not be worth the time to implement unless this will be extensively-used production code. $\endgroup$
    – whuber
    Aug 9, 2023 at 15:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.