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 Answer 1

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$
2
  • $\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$
    – javidcf
    Jun 1, 2018 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, 2018 at 11:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .