Derrangements

Consider a permutation \sigma of [n], and let X^n_j be the random variable that takes the value 1 if this permutation fixes j, and takes the value zero elsewhen. Set X_n= \sum X_n^j.

  1. Express P(X_n=k) in terms of P(X_m=0) for a suitable m.
  2. Find P(X_n >0), and hence find P(X_n=0).
  3. Find P(X_n=0) as n\to\infty, and deduce that X_n converges in distribution to a Poission variable. Of what weight?
Advertisements
Derrangements

One thought on “Derrangements

  1. 1. Choose k fixed points in a set of n elements, then choose a derangement of the other n-k elements, we get n!P(X_n=k)=\binom {n}{k}(n-k)!P(X_{n-k}=0), so P(X_n=k)=\frac{1}{k!}P(X_{n-k}=0).
    2. Let A_k be the number of permutations that fix k \in [n], by the inclusion-exclusion principle
    n!P(X_n>0) = |\bigcup_{i=1}^n A_i| = \sum_{k_1}|A_{k_1}| - \sum_{k_1<k_2}|A_{k_1} \bigcap A_{k_2}| + \ldots + (-1)^{n-1}|A_1\bigcap \ldots \bigcap A_n| = \sum_{j=1}^n(-1)^{j-1}\binom{n}{j}(n-j)! = \sum_{j=1}^n\frac{(-1)^{j-1}n!}{j!}
    Then, P(X_n>0) = \sum_{j=1}^n\frac {(-1)^{j-1}}{j!}. Thus, P(X_n = 0 ) = \sum_{j=0}^n\frac {(-1)^{j}}{j!}.
    3. Clearly \lim_{n\to\infty}P(X_n = 0) = \sum_{j=0}^\infty\frac {(-1)^{j}}{j!} = e^{-1}. And, by 1., \lim_{n\to\infty}P(X_n = k) = \lim_{n\to\infty}\frac{1}{k!}P(X_{n-k}=0) = \frac{e^{-1}}{k!} = \frac{1^ke^{-1}}{k!}. Thus, X_n converges in distribution to a Poisson variable of rate parameter 1.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s