Symmetric groups and Poisson processes

Question

Consider the number of fixed points in a permutation chosen uniformly at random from the symmetric group on $n$ elements - this gives a probability distribution. For $k < n$, the $k$-th moments of this distribution are the same as the Poisson distribution with $\lambda = 1$.

Since you can't pick uniformly randomly from an infinite set, it doesn't make sense to ask if you get exactly the Poisson distribution in the limit of the symmetric group on a countably infinite set. But can you get there in another way? Is there a known way to take limits in some category of distributions and groups that leads to the Poisson distribution for the fixed points of some countably infinite group of permutations? Alternately, is there a known structure that can be put on $|S_\omega|$ that gives rise to a Poisson process that is analogous to the finite case?

Also, are there other infinite families of finite permutation groups that give rise to a similarly elegant characterization of the distribution of fixed points? Say by taking one of the families of finite simple groups and applying the same finite extension to each of them?

(Please excuse me if I accidentally posted this twice - I didn't see the first attempt go through.)

Answer 1

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).

Answer 2

"On Fixed Points of Permutations" by Diaconis, Fulman and Guralnick is a good place to start reading, though this problem has been treated many different times in the literature.

To briefly summarize, though, most papers that I have read have just noted that under reasonable topologies of the 'space of all measures on the non-negative integers', the number of fixed points of $S_{n}$ really does converge to Poisson with mean 1 (in particular, I think it does for total variation, prokhorov, weak, etc).

For a comment completely unrelated-to-the-literature comment, I think you're going to find it much more difficult to deal with measures on the permutation group on the positive integers (i.e. the 'countably infinite' permutation group) than just taking the limits of the finite ones, as there aren't any nicely uniform measures. Of course, there is nothing wrong with embedding the finite ones in the infinite one.