2
$\begingroup$

Let's say I have a set of $N$ random $k$-permutations $P_1,\ldots,P_N$ selected according to some probability distribution. I consider the probability distribution of the frequencies of contiguous pairs in a permuted sequence. I'm not sure how to express this properly so I'll give an example: with $k=4$ and the permutation $P_i=(24)$ we would reorder the sequence $[1,2,3,4]$ to $[1,4,3,2]$; what I call "contiguous pairs" for $P_i$ would be $(1, 4)$, $(4, 3)$, $(3, 2)$ and $(2, 1)$. So I can count the frequencies of the $k(k - 1)$ possible pairs for my $N$ permutations.

Now, my intuition is that, if my permutations are sampled according to a uniform distribution, then each of these frequencies should be about the same as $N \rightarrow \infty$, and they would follow a binomial distribution with $N$ trials and probability $1 / (k - 1)$, because for each permutation any element $a$ may be followed by any of the other $k - 1$ elements with equal probability. I'm not completely sure this is really correct, though, because there are relationships between the frequency values (i.e. $\sum_{i \in \{1,\ldots,k\}\setminus{\{a\}}}\text{frequency}((a, i)) = N\, \forall\, a \in \{1,\ldots,k\}$).

My question is, assuming the previous is actually correct, or otherwise that we know that uniformly sampled permutations have a probability distribution of frequencies of contiguous pairs $D$, can we invert the implication? That is, would observing $D$ in another set of random permutations mean they follow a uniform probability distribution?

EDIT:

I noticed that the above condition is definitely not enough for a uniform permutation distribution. You could imagine a random permutation such that the first element is always the same but the remaining ones are uniformly shuffled, then it would fulfill the condition but it wouldn't be what I am looking for. So I guess the conditions that I'd need to check are, following a uniform distribution of contiguous pairs and uniform probability of each element falling into each position.


Background:

I answered this question in Stack Overflow: How to verify that a shuffling algorithm is uniform? (I invite anyone willing to it to comment on my answer or post their own if they think it's wrong). I am a software engineer, so my background in statistics is not the strongest, but (after a misguided attempt) I proposed a small code snippet to measure the frequency with which each possible permutation was generated.

While this is (I think) a correct approach, in the sense that it is measuring "the right thing", it takes a large number of trials to have significant results, so I was wondering if it may be possible to analyse a smaller statistic, such as the distribution of frequencies of contiguous pairs.

$\endgroup$
1
$\begingroup$

No, this is is still not enough. For $n\ge4$, a uniform distribution over the permutations with even parity also fulfils your criteria, for instance for $n=4$: $1234$, $1342$, $1423$, $2143$, $2431$, $2314$, $3241$, $3412$, $3124$, $4213$, $4132$, $4321$.

More generally speaking, it would be surprising if you could fully determine a distribution with $n!$ free parameters and one linear constraint (the normalization) by specifying $n^2$ linear constraints.

$\endgroup$
  • $\begingroup$ I see, thanks for the clear example. Can you please briefly explain why the distribution has n! parameters? I thought a uniform distribution over the whole set of permutations would have a single parameter p = 1 / n! $\endgroup$ – jdehesa Jun 1 '18 at 10:47
  • 1
    $\begingroup$ @jdehesa: Yes, the uniform distribution is fully determined (it doesn't have any free parameters, since $p=\frac1{n!}$ is determined by normalization). I mean that a general distribution over permutations has $n!$ free parameters minus one normalization constraint, so in order to make sure that a given distribution actually is the uniform distribution, you'd usually have to introduce $n!-1$ constraints, whereas you only introduced $n^2$ constraints and were hoping that this would uniquely identify the uniform distribution. $\endgroup$ – joriki Jun 1 '18 at 11:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.