0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the quick answer. I get the idea, but I'm not sure if I can use it. I'm not certain about this, but I think the problem is meant as: [...] To show that each randomly generated permutation of A ("that can be generated by the algorithm") occurs with the same probability [..] Considering only cyclic permutations of $(1,...,n)$, it seems apparent that all other permutations have Zero probability. More interesting for me are permutations that can indeedly be generated and satisfy the $\tfrac{1}{n}$ probability property, but are less (more) likely than others. Do they exist? $\endgroup$ – Octavius Nov 2 '19 at 21:17
  • $\begingroup$ @Oct You're making life difficult for yourself if you consider this example to be "cheating." Sure, you could make all of the probabilities nonzero, but why when it's not specified and simply easier to do this? $\endgroup$ – Matt Samuel Nov 2 '19 at 22:02
  • $\begingroup$ Hm, I think I was being unclear here. The thing is that this problem is part of a lecture on algorithms (current topic: randomisation). So when the task says "each randomly generated permutation", I think it means, that only those are allowed to be considered, that are possible OUTPUTS A' of an algorithm (whatever algorithm this may be) that gives me a random permutation of some INPUT array A. But maybe I am just interpreting the task wrongly. :( $\endgroup$ – Octavius Nov 2 '19 at 22:30
  • $\begingroup$ E.G.: An algorithm randomly gives cyclic permutations of A as an OUTPUT, but only cyclic permutations. I now have to show, that each cyclic permutation is equally probable amongst all other cyclic permutations. $\endgroup$ – Octavius Nov 2 '19 at 22:42
  • $\begingroup$ @Octavius I have added a second example which I thing deals with your point, if I understand it correctly $\endgroup$ – Henry Nov 2 '19 at 23:37

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.