Algorithm for Weighted Permutation

Question

Suppose we would like to permute a list of $n$ elements, such that for each element $a_i$, it has a $p_{ij}$ probability of being in the $j$th slot in the permutation, and we assume $\sum_{i=0}^np_{ij}=1$ and $\sum_{j=0}^np_{ij}=1$. Find an algorithm for creating such a permutation.

I'm not sure how to go about this, since none of the probabilities are independent. The only algorithm I figure out was manually weighting each possible permutation then randomly selecting one based on these weights, but sadly this is in factorial time; preferably I would like to see a clean solution in polynomial time.

Answer 1

This is exactly equivalent to the base theory of doubly stochastic matrices. This is shown in the sense that a doubly stochastic matrix is expressible as a convex sum of permutation matrices. One high-level way of proving this is

1. Decompose the Probability Matrix: So, to start off, one decomposes a doubly stochastic probability matrix into a convex combination of permutation matrices. A permutation matrix represents a permutation of the elements within, and the coefficient (or weight) in front of it points out how much it contributes towards your original probability matrix.

2. Sample a Random Permutation: Based on the weights supplied by the decomposition, sample uniformly at random from the set of permutation matrices. This is equivalent to sampling a permutation with the distribution prescribed by your original probability matrix.

This construction respects the given probabilities to the putting in place of each element of the random permutation and it is efficient. However, the practical challenge comes at the decomposition step, which is a nontrivial but solvable in polynomial time using algorithms specifically designed to find the Birkhoff–von Neumann decomposition. After the decomposition, a permutation according to the weights can easily be selected and in a highly efficient way.

The above procedure avoids the factorial complexity to enumerate and weigh all possible permutations, with the polynomial-time solution to generate a permutation under specified probability constraints.