3
$\begingroup$

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = \sum_{j}p_{i,j} = 1$, $i,j = 1,2,...,n$).

Probability matrix elements $p_{i,j}$ define probability of $i = \pi(j)$ and $0 <= p_{ij} <= 1$.

The sampled permutations should correspond to the defined probability matrix $P$ and probability of each permutation should correspond to the following permutation probability

$$p(\pi)=\frac{\prod_{i} p_{i,\pi(i)}}{\sum_{all \pi}\prod_{j} p_{j,\pi(j)}}=\frac{\prod_{i} p_{i,\pi(i)}}{perm(P)}$$

Example: Probability distribution matrix

$$ P = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \\ 1/2 & 0 & 1/2 \end{array} \right) $$

produce only two permutations $\pi_1 = (2 1 3)$ and $\pi_2 =(2 3 1)$ with the same probability $p(\pi_1) = p(\pi_2) =1/2$

This question is a follow-up to Random permutations by probability matrix

I tried a few variations of node histogram based sampling algorithm (NHBSA) by Shigeyoshi Tsutsui. This method is used as a main tool on permutation optimization problems. But the results are not very promising. So, I ask this question here, to learn what is current state of art on this topic.

I tried to test a few algorithms, but all these methods produce permutations with more or less distorted probability matrix even for small n (3 <= n <= 10 ). This is the reason why I am asking for help.

Some comments here states that interpretation of matrix $P$ and permutations probability $p(\pi)$ are not clear enough to define unique permutations distribution.

So, is possible to use $\prod_{i} p_{i,\pi(i)}$ for ranking of permutation probabilities, where permutations $\pi$ are generated randomly only by (0,1) restriction matrix via Hungarian algorithm for bipartite graph matching?

Comment: I am convinced now, that only "simple" way how to solve my problem is to generate arbitrary (random) permutations $\pi$ which satisfy to (0,1) restrictions in probability matrix only (elements $p_{i,j}>0$ should be transformed to $p_{i,j}=1$) and then rank all these permutations by $\prod_{i} p_{i,\pi(i)}$ probability.

The problem how to effectively generate (0,1) restricted permutations (permutations with restricted positions) is different problem.

$\endgroup$
3
  • $\begingroup$ "and then rank all these permutations by $\prod_{i} p_{i,\pi(i)}$ probability", i dont think this will work, since different permutations may have exactly same probability, like your example with $\pi_1 = (2 1 3)$ and $\pi_2 = (2 3 1)$, have exactly same probability $1/2$. How are you going to unrank them? $\endgroup$ – Nikos M. Jun 9 '15 at 14:48
  • $\begingroup$ I'm also looking into how to do this. One way to directly sample (that is computationally very expensive) is to calculate the permanent of the doubly stochastic matrix and then use that as a normalizing factor for given permutations. You can also get the mode of the distribution by finding the maximal matching (i.e. Kuhn-Munkres algorithm). At least one paper has suggested sampling rows based on their remaining entropy and then choosing uniformly among the remaining columns. This clearly doesn't work either. $\endgroup$ – Ryan Marcus Nov 16 '16 at 20:00
  • $\begingroup$ Perhaps using the Gumbel-max trick as in arxiv.org/pdf/1802.08665.pdf? $\endgroup$ – Jeremy Salwen Dec 7 '20 at 6:28
0
$\begingroup$

The problem has recently been actively studied:

https://arxiv.org/abs/2007.15043

https://arxiv.org/abs/1904.03836

https://projecteuclid.org/euclid.ejs/1586419218

https://academic.oup.com/comnet/article-abstract/6/6/833/4772759

P.S. It is true, that problem is not fully or correctly defined, but Raphael's comments are at least a bit confusing.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.