Randomly generated permutations

combinatoricspermutationsprobability

I have been thinking about this problem the whole day, but I really don't get any useful ideas on how to solve it.

The problem is:

Let $A[1,…,n]$ be an array that contains elements of some set M (doesn't matter what kind of set, for simplicity let us say $M = \{1, …, n\}$ ).

To show that each randomly generated permutation of A occurs with the same probability, it is NOT sufficient to show that for each $i \in M $ the probability for $A[i]$ to be on position $j$ is equal to $\tfrac{1}{n}$. Find an example where the latter property is satisfied but the first one isn't.

—Problem End—

$ $

I was working on an algorithm like this one (pseudo-code):

for $\quad i = 1:n \quad$ do

$\quad k = random(1,n)$

$\quad$ change $A[i]$ with $A[k]$

end for

So, I am generating a random number $k$ between $1$ and $n$ and change the position of $A[i]$ with that of the random number. I think this does not necessarily generate random permutations, because in the case of for example $n=3$, I have $n^n = 27$ possible arrangements, where certainly some are the same, but I have only $n! = 6$ permutations, which means, some permutations are more likely. Calculating the possibility for $A[i]$ to be on some position $j$ is quite difficult though, because there are many ways to get there.

If someone could give me some advice or a hint, I would appreciate it.

Thank you,

Ocatvius

Best Answer

A simple example is to consider arrays of the form $(m+1, m+2, \ldots n, 1, 2,\ldots, m)$. There are $n$ such arrays with $0 \le m \lt n$, and if they are equally likely then $A[i]=j$ when $m \equiv i-j \bmod n$ which happens with probability $\frac1n$

But there are $n!$ possible randomly generated permutations of $A$ and so in this example they are not equally likely: $n!-n$ of them have probability $0$ in this example while $n$ have positive probability

Added as your comment suggests you think the $n$ cyclic permutations have the same probabilities as each other

An alternative algorithm:

  • Generate a random number $m$ uniformly from $\{0,1,\ldots m-1\}$ and another $k$ from $\{0,1,2\}$
  • If $k=0$ or $k=2$ then choose the permutation $(m+1, m+2, \ldots n, 1, 2,\ldots, m)$
  • If $k=1$ then choose the reverse of that, i.e. permutation $(m,m-1,\ldots, 1, n, n-1, \ldots m+1)$

So there are now $2n$ possible permutations, $n$ having probability $\frac2{3n}$ of appearing and the other $n$ having probability $\frac1{3n}$ of appearing. For given $i$ and $j$ you still have the required $\mathbb P(A[i]=j)=\frac1n$.

Incidentally, in both this and the previous counterexample, and indeed any counterexample, you need $n \gt 2$

Related Question