Modeling a list with a tunable degree of disorder/shuffling

Question

Imagine we have a list of ordered numbers $L = (1, 2,\dots, N)$.

I want to add an arbitrary amount of "disorder" to that list. For instance:

• Adding a little bit of disorder would permute a few neighboring numbers

• Adding more disorder would permute several numbers, many of them not neighbors

• Adding maximal disorder would permute all the numbers

Ideally I would like to use an algorithm that has a sound statistical/information theoretic foundation.

I am not sure about how to search for this. I have tried Googling things like:

• Tunable degree of shuffling
• Generating random lists of numbers with a given entropy / Kullback-Leibler distance
• Generating a list with a given level of presortedness

Note that the solution is not just shuffling a given percentage of the numbers. When disorder is small, the shuffling should occur among numbers that are close.

The process I am trying to model is akin to "shaking." Imagine I have a number of casino tokens ordered one after the other on top of a one dimensional table. Then I shake the table along its dimension and see in what order the tokens landed. The tunable degree of disorder I want to model corresponds to how much I shake the table.

Any ideas? Many thanks!

Answer 1

Let $O = \{ (0, 1, 2, ..., N) \}$, i.e. the set containing the single correctly ordered $N$-tuple. Let ${\sim}O$ be the set of all orderings that does not contain the correct ordered $N$-tuple.

Now given a particular shuffling algorithm $A$, that has the constraint that it is defined in terms of randomly selecting a subset of elements, then randomly permuting those elements, we can define $KL(A)$ to be the Kullback-Leiber Divergence (or cross entropy) between the two probabilities $P(O)$ and $P({\sim}O)$ after applying that algorithm twice. This then formally defines a measure in terms of information theory for how 'random' or 'shuffly' a particular algorithm is.

E.g. For the identity shuffle, $Id$, we have $KL(Id) = 0$.

E.g. Let $A_M$ be the algorithm that randomly picks $M$ elements to be shuffled, then it's easy to check that for $X < Y$, $KL(A_X) < KL(A_Y)$.

You can then inverse $KL(A_M)$ as a function on $M$ to generate an algorithm $A_M$ given a particular $KL$ (this won't be well defined for all $KL$, and so $M$ could be chosen such that $KL(A_M)$ is closest).

Note that we defined a 'space' of algorithms, we could consider extending this space to be the composition of arbitrary $A_M$ algorithms. Then the inverse of $KL$ may not be unique - i.e. define a set of algorithms.

Finally, I would like to add that your question is actually an interesting open question in Information Theory as there is no such definition that let's the space of algorithms be arbitrary. The closest definition is Kolmogorov Complexity, which essentially considers the length of the smallest program that implements the algorithm, the problem with this is the choice of programming language is arbitrary. Furthermore even if we choose a programming language, computing Kolmogorov Complexity is undecidable (no program exists that can determine the minimum length of an implementation).

Answer 2

Here is an algorithm which seems to work quite well, but does not have a sound information-theoetric foundation: let $X_i$, $1 \le i \le n$ be independent draws from a normal distribution with mean $0$ and variance $\sigma^2$. Let $Y_i = i + X_i$. Then re-sort your list according to the sizes of the $Y_i$. If $\sigma$ is small, then it is very likely that you will have $Y_1 < Y_2 < \cdots < Y_n$, so your list will not be permuted at all. But as $\sigma \rightarrow \infty$, the $Y_i$ are essentially just a bunch of random numbers, and you are equally likely to get them sorted in any order. (To be precise, $P($ order of $i$ and $j$ gets swapped $) = P(Y_j < Y_i) \rightarrow 1/2$ as $\sigma \rightarrow \infty$.)

Here is code to do it in the R language with $n=10$:

L <- 1:10
X <- rnorm(10, 0, 1)
L[order(1:10 + X)]
# [1]  1  2  4  3  5  6  7  8  9 10
X <- rnorm(10, 0, 10)
L[order(1:10 + X)]
# [1]  1  3  7  4  2  9  8  6 10  5
X <- rnorm(10, 0, 100)
L[order(1:10 + X)]
# [1]  4 10  3  7  1  8  5  6  2  9