1
$\begingroup$

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?

  • 1
    What about 1 2 2 and permutations?2012-04-02
  • 1
    but not `1 3 3` and permutations2012-04-02
  • 0
    @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.2012-04-03
  • 0
    @MarcinZalewski: Yeah, was just looking to clarify what you exactly wanted...2012-04-03
  • 0
    @ 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.2012-04-04

2 Answers 2

1

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.

0

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
  • 0
    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](https://oeis.org/A000670) for any sequences that are reasonably long.2012-04-03