I am currently studying the concept of convergence in distribution in probability theory.
We have the permutation $\tau : \{1,\dots,n\} \to \{1,\dots,n\}$. Let $\tau_n$ be a random permutation chosen uniformly random from all $n!$ possible permutations.
We let $X_n$ be the number of fixed points of $\tau_n$.
I want to show that $\lim_{n\to\infty} F_{X_n} = F_X$ where $X$ ~ $\text{Poi}(1)$.
I am given a hint that I can explain that it is enough to show that $P(X_n = j) \to \frac{1}{ej!}$ for any fixed $j$. After that I can use the fact that $P(X_n = 0) \to 1/e$ as $n \to \infty$ (I have already proven this stament) to estimate the number of permutations with exactly j fixed points.
The thing I cannot get my head around is the part where I need to explain that it is enough to show that $P(X_n = j) \to \frac{1}{ej!}$ for any fixed $j$. Can someone clarify this a little for me?
I started with writing out that
$F_{X_n} = P(X_n \leq j) = P(X_n = 0) + P(X_n = 1) + \dots + P(X_n = j)$
But everything I tried after that didn't really make things clearer for me..
Any ideas?
Thanks in advance!
If you want to calculate $P\left(X_n=j\right)$, you need to calculate the amount of permutations $\tau_n:\{1,...,n\}\longrightarrow \{1,...,n\}$ with j fixed points.
If we were to construct such a permutation we'd have $binomial(n,j)=\frac{n!}{\left(n-j\right)! j!}$ possibilities to choose j fixed points. Now we have n-j ponints left, to construct permutations without fixed points. Following the wikipedia aricle about derangement, there are \begin{align} \left(n-j\right)! \sum_{k=0}^{n-j} \frac{\left(-1\right)^k}{k!} \end{align} permutations $\tau_{n-j}:\{1,...,n-j\}\longrightarrow \{1,...,n-j\}$ without fixed points.
Thus there are $\frac{n!}{\left(n-j\right)! j!} \left(n-j\right)! \sum_{k=0}^{n-j} \frac{\left(-1\right)^k}{k!} $ permutations with exactly $j$ fixed points.
Overall there are $n!$ permutations, therefore \begin{align} P\left(X_n=j\right)&= \frac{\frac{n!}{\left(n-j\right)! j!} \left(n-j\right)! \sum_{k=0}^{n-j} \frac{\left(-1\right)^k}{k!} }{n!} \\ &= \frac{1}{j!} \sum_{k=0}^{n-j}\frac{\left(-1\right)^k}{k!} \\ &\underset{n\rightarrow \infty}{\longrightarrow} \frac{1}{j!} \frac{1}{e}. \end{align}
In conclusion we see, that \begin{align} P\left(X_n=j\right) \underset{n\rightarrow \infty}{\longrightarrow} \frac{1}{j! e} =\frac{1^j e^{-1}}{j!}, \end{align} which ist the probability density of the Poisson distribution with parameter $\lambda=1$. Then $\text{lim}_{n\rightarrow \infty }F_{X_n}= F_X$, wehere $X \sim \text{Poi}\left(1\right)$.