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?

  • 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