# How to randomly generate weak orderings of a given length in a uniform fashion?

I recently found out how to calculate the number of all possible weak orderings of a given length. Now, however, I am looking for a way not to only count but to also randomly generate these orderings with a uniform distribution. For, example, for sequences of length 3, there are 13 possible orderings:

1 2 3
3 2 1
1 3 2
2 1 3
2 3 1
3 1 2
1 1 3
1 3 1
3 1 1
3 3 1
3 1 3
1 3 3
1 1 1


Is there a method to uniformly generate such orderings at random?

-
What about 1 2 2 and permutations? – Aryabhata Apr 2 '12 at 20:12
but not 1 3 3 and permutations – Henry Apr 2 '12 at 23:31
@Aryabhata From the point of view of ordering, 1 2 2 and 1 3 3 are the same. You have one value lesser than the other two that are equal. – Marcin Zalewski Apr 3 '12 at 19:49
@MarcinZalewski: Yeah, was just looking to clarify what you exactly wanted... – Aryabhata Apr 3 '12 at 19:57
@ Aryabhata: OK, yeah, I was looking for just weak order permutations. Turns out that my question is answered very well in a paper I found. – Marcin Zalewski Apr 4 '12 at 1:40

In the meantime, I found the answer to my question in a paper listed on the Encyclopedia of Integer Sequences. The paper:

"Generating random weak orders and the probability of a Condorcet winner" by Hans Maassen and Thom Bezembinder.

Basically, the procedure goes as follows (copied from the paper):

Let $A$ be a set of $m$ elements, $m \geq 1$. Let a stochastic weak order $R$ on $A$ be generated by the following algorithm:

1. Draw an integer-valued random variable $K$ according to the probability distribution $\pi_m$. (See the instruction below).
2. To each $a \in A$ assign a random score $X_a$ according to the uniform distribution on $\lbrace 1; \ldots ;K \rbrace$.
3. Put $aRb$ iff $X_a \leq X_b$.

To generate numbers according to distribution $\pi_m$, do the following:

1. *Choose a small number $\delta$ such that $1/\delta$ is of the order of the total number of weak orders to be generated ($W_m$, can be calculated using the formula in the paper), and find $N \in \mathbb{N}$ so large that* $$W_m - \sum_{k=1}^{N}\frac{k^m}{2^{k+1}}<\delta.$$
2. *Fill an array with the partial sums $S_0, S_1, S_2, \ldots, S_N$* given by: $$S_k := \sum_{j=0}^k\frac{j^m}{2^{j+1}}, k = 0, 1, \ldots, N-1;\quad S_N := W_m.$$
3. For each of the weak orders to be sampled:
1. Let $Y := W_m \cdot RND(1)$, where $RND(1)$ produces a random number uniformly over $[0, 1]$.
2. Let $K$ be the least integer for which $S_K \geq Y$.

The details of why this works are in the paper.

-

This is easy enough as a programming exercise, for example in R:

First generate the weak orders in ascending order

n <- 3
orderwo <- matrix(1)
for (i in 2:n){orderwo <- rbind(cbind(orderwo,orderwo[,i-1]),cbind(orderwo,i))}


which produces something like

> orderwo
i
[1,] 1 1 1
[2,] 1 2 2
[3,] 1 1 3
[4,] 1 2 3


then permute these but only keep unique patterns

p <- t(perms(n))
permwo <- unique(matrix(orderwo[1,p], ncol=n))
for (i in 2:2^(n-1)){permwo <- rbind(permwo, unique(matrix(orderwo[i,p], ncol=n)))}


which produces something like

> permwo
[,1] [,2] [,3]
[1,]    1    1    1
[2,]    1    2    2
[3,]    2    1    2
[4,]    2    2    1
[5,]    1    1    3
[6,]    1    3    1
[7,]    3    1    1
[8,]    1    2    3
[9,]    1    3    2
[10,]    2    1    3
[11,]    2    3    1
[12,]    3    1    2
[13,]    3    2    1


then sample uniformly from this list

permwo[sample(nrow(permwo), 4, replace = TRUE), ]


which produces something like

     [,1] [,2] [,3]
[1,]    2    2    1
[2,]    1    1    3
[3,]    1    2    3
[4,]    3    1    2

-
Henry, thanks. In the meantime, I found this paper: "Generating random weak orders and the probability of a Condorcet winner" by Hans Maassen and Thom Bezembinder. It pretty much answers my question. Your answer is something that one would consider, but unfortunately it could be infeasible for any sequences that are reasonably long. – Marcin Zalewski Apr 3 '12 at 19:44