Shuffling an ordered list with a given degree of randomness

Question

I feel like the following problem should have a well-known answer, but unfortunately I don't know the keywords to look up.

I would like a procedure that takes as an input an ordered list of items, and outputs a shuffled version of that list. The procedure should have a tunable 'knob' that determines the degree of randomness (defined in some appropriate sense) in the output list. In particular:

• If the knob is set to 0, the output should be identical to the input

• If the knob is set to 1, the I output should be a complete shuffle, such that none of the input order is preserved (in expectation)

• A small value of the knob should make items likely to move around by a few places up or down the list, but big jumps should be rare

Is there a way to make these ideas precise, and is there a known procedure for this problem?

Any leads would be appreciated.

Answer 1

There is a quantity called Kendall's tau, which would be close to what you want. It is defined more generally but specifically, for two permutations, the Kendall tau distance between them is the number of pairs that are in different order in the two permutations.

For example, the Kendall tau distance between $\pi=(0 3 1 6 2 5 4)$ and $\sigma=(1 0 3 6 4 2 5)$ is four because the pairs $0-1, 3-1, 2-4, 5-4$ are in different order in the two rankings, but all other pairs are in the same order.

One way of defining the distance is to write $$ K(\pi,\sigma)=\sum_{\{i,j\}\in P} \mathbf{1}\left\{i ~and~ j~are~in~opposite~order~in~\pi~and~\sigma\right\}, $$ where the sum is over $P,$ the unordered pairs of distinct elements.

This distance is $0$ if the two permutations are the same and $n(n-1)/2$ if they are opposite ordered.

Given a permutation $\pi$, and a value $r\geq 0$ for the Kendall tau, one can generate a permutation $\sigma$ such that $K(\pi,\sigma)=r:$

Let $\sigma=\pi,$ and if $r=0,$ stop output $\sigma.$

Otherwise choose uniformly at random $r$ positions $I_r$ such that $$I_r=\{i_1,\ldots,i_r\} \subset \{0,\ldots,n-1\},$$ and uniformly at random $r$ positions $J_r$ from the remaining positions such that $$J_r=\{j_1,\ldots,j_r\} \subset \{0,\ldots,n-1\} \setminus I_r.$$

For $k=1,\ldots,r,$ let $TEMP:=\sigma(i_r),$ $\sigma(i_r)=\pi(j_r),$ and $\pi(j_r)=TEMP.$

Answer 2

One approach could be to give each element a random value which is close to its original position when the knob is close to $0$ and which is almost uniformly distributed when the knob is close to $1$, and then order the output by these random values

For example this is an R function

shuffle <- function(x, knob=1){
  if(knob <= 0) {return(x)}
  if(knob >= 1) {knob <- 1}
  n <- length(x)
  a <- 1 + ((1:n)-1)/(n-1) * (1/knob-1)
  b <- 1 + (n-(1:n))/(n-1) * (1/knob-1)
  x[order(rbeta(n,a,b))]
  }

which applied to the first half of the alphabet with the knob set to $1,0.2,0.02$ might give

> set.seed(2018)
> shuffle(LETTERS[1:13], knob=1)
 [1] "G" "E" "H" "M" "J" "D" "C" "F" "A" "I" "K" "L" "B"
> shuffle(LETTERS[1:13], knob=0.2)
 [1] "C" "B" "E" "A" "J" "D" "F" "H" "I" "M" "G" "L" "K"
> shuffle(LETTERS[1:13], knob=0.02)
 [1] "A" "B" "D" "C" "F" "E" "H" "G" "J" "I" "K" "L" "M"