I have an intuitive notion of 'local randomness' that I am trying to make precise and understandable, and I am running into a bunch of problems. A quick web search failed to find anything relevant in the discrete domain. I was able to find some information on 'mixing length' in convection, but that's in a continuous domain. Almost everything in the discrete world is concerned with producing globally truly random permutations, but I want to generate permutations as if the original were 'stirred' locally. Here is what I mean:

Consider a finite sequence of some objects of length $n$, for instance, the integers $(65, 66, ..., 74)$ in a sequence of length $10$. Say that I 'stir' the elements of this sequence in groups of length $3$, starting from the left and going to the right. I replace the first three elements, namely $(65,66,67)$, with a randomly chosen permutation, say $(66,67,65)$. I then step one to the right and replace the next three elements, now $(67,65,68)$ after the prior stirring to the left, with a random permutation of those three, say $(67,68,65)$. I then repeat this procedure, stepping once to the right each time, until I stir the final batch of three at the end. I might end up with a permutation like $(66,67,68,70,65,69,73,71,72,74)$. I intuit this as 'locally random' because the low numbers have a tendency to stay to the left and the high numbers tend to stay to the right. Notice that $65$, the original smallest number, has migrated halfway across the sequence, but the tendency is still there.

My biggest problem with this is that the procedure is biased: the low numbers can migrate far to the right, but the high numbers have no chance to get far to the left. That's similar to convection, in which the 'hot' layers bubble up to the 'cool' layers. But, in convection, the cool material can sink all the way to the bottom due to negative buoyancy. I thought about running the procedure twice, once forward, once backward, but then I lost my ability to understand it.

Under what name has this sort of thing been studied and are there references to some material I could study? Are there better procedures for locally stirring my sequences so that they're not directionally biased?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.