Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
What about 1 2 2 and permutations? –  Aryabhata Apr 2 '12 at 20:12
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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