Return to Revisions

This isn't a problem I've looked at before, but I've been thinking about it since reading your post, and there does seem to be an interesting limit. The following looks like it should all work out, but I haven't gone through all the details yet.

Embed the set $\{1,...,n\}$ into the unit interval $I=[0,1]$ by $\theta(i)=\frac in$. Then look at $\theta(A)$ for the fixed points $A\subset \{1,..,n\}$ of a random permutation. Increasing n to infinity, the distribution of $\theta(A)$ should converge weakly to the Poisson point process on I with intensity being the standard Lebesgue measure.

That is only the fixed points though. You can look at the limiting distribution of the set of all points contained in orbits of bounded size (≤ m, say), and at the action of the random permutation on this set. This should have a well defined limit, and you can then take the limit m → ∞ to to give a random countable subset of I and a random permutation on this, such that all orbits are finite.

Let I_n={1/n,2/n,...,n/n} ⊂ I, and consider a random permutation π of this. The probability that any point P ∈ I_n is an element of an orbit of size r is (1-1/n)(1-2/n)...(1-(r-1)/n)(1/n). The expected number of points lying in such orbits is (1-1/n)...(1-(r-1)/n) and the expected number of orbits of size r is (1-1/n)...(1-(r-1)/n)/r, which tends to 1/r as n → ∞.

Now represent orbits of size r of the permutation π by sequences of distinct elements of the interval I, (x₁,...,x_r), where π(x_i) = x_i+1 and π(x_r) = x₁. We'll identify cyclic permutations of such sequences, as they represent the same orbit and the same action of π on the orbit. So (x₁,...,x_r) = (x_r,x₁,...,x_r-1). Let I^(r) be the space of such sequences up to identification of cyclic permutations.

Then, every permutation π of I_n gives a set of fixed points A₁ ⊂ I⁽¹⁾=I, orbits of size 2, A₂ ⊂ I⁽²⁾, orbits of size 3, A₃ ⊂ I⁽³⁾, etc. Then, I propose that A₁, A₂, A₃,... will jointly converge to the following limit; (α₁,α₂,α₃,...) are independent Poisson random measures on I⁽¹⁾,I⁽²⁾,I⁽³⁾,... respectively such that the intensity measure of α_r is uniform on I^(r) with total weight 1/r. Taking the union of all these orbits gives a random countable subset of I and a random permutation of this.

I used the unit interval as the space in which to embed the finite sets {1,...,n} but, really, any finite measure space (E,ℰ,μ) with no atoms will do. Just embed the finite subsets uniformly over the space (i.e., at random).