Number of fixed points in permutations with Ewen distribution

Question

Let $S_n$ be the set of permutations of the first $n$ integers. Draw at random an element $\pi \in S_n$ with probability $$ P(\pi) = \frac{1}{Z_{N,n}}N^{\mathcal{L}(\pi)}, $$ where $\mathcal{L}(\pi)$ is the number of cycles of the permutation $\pi$ and $N >0$ is a parameter, $Z_{N,n}$ is a normalisation constant. Define the match set as the set of integers belonging to a cycle of length one, $M(\pi) = \{i \in \{1,2 ... n \} : \pi(i)=i \}$( i.e, the fixed point of the permutation). How does the expected size of the match set, $$ E_{N,n}(| M| ) $$ qualitatively grow with n for any value of $N \geq 1$? Here $E_{N,n}$ is the expectation with respect to the probability measure above.

I am particularly interested in the case of integers $N \geq 2$. The problem is very interesting on its own, for N=1 the problem is well known and $E_{N,n}(| M| ) = 1$ for any $n \in \mathbb{N}$, see for example https://golem.ph.utexas.edu/category/2019/12/random_permutations_part_6.html.

Answer 1

The normalization constant is in fact $Z_{N,n} = N(N+1) \cdots (N+n-1)$. Let $X \subset S_n$ be the set of permutations fixing some point, say $n$. Now elements of $X$ are like elements of $S_{n-1}$ except they have one more cycle, so the total Ewens mass in $X$ is $N Z_{N,n-1} = N\cdot N(N+1)\cdots(N+n-2)$, so $P(X) = N/(N+n-1)$. By linearity of expectation the expected number of fixed points is $nN/(N+n-1)$.

Note this has the right behavior at $N=1$ (uniform distribution), $N = 0$ (uniform distribution on $n$-cycles), and $N = \infty$ (trivial distribution), so "it must be right".

This is fairly standard and there are similar estimates for cycles, fixed sets, etc, all generalizing properties of the uniform distribution. Have a look at Section 3 of this paper if you are interested: https://arxiv.org/abs/1808.08892

Answer 2

You are looking for $$\mathbb{E}[|M|]=\sum _{i=0}^ni\cdot \sum _{\substack{\pi \\\text{having j cycles,i of size 1}}}\frac{N^{i+j-i}}{Z_{N,n}}.$$ Now, the number of derangements (permutations without fixed points) of $n-i$ with $j-i$ cycles is given by $${n\brack j-i}-\left |\bigcup _{\ell=1}^n A_\ell\right |,$$ where ${n\brack k}$ are the Stirling numbers of first kind and $A_{\ell}$ are permutations with $j-i$ cycles in which $\ell$ is fixed. Use inclusion exclusion by showing that $$\left |\bigcap_{x\in X}A_x\right |={n-|X|\brack j-i-|X|}.$$ The proof should look like the one for derangements.

At the end of the day the original sum looks like $$\frac{1}{Z}\sum _{i=0}^ni\binom{n}{i}\cdot \sum _{j=i}^nN^{j}\left (\sum _{k=0}^{n-i}(-1)^k\binom{n-i}{k}{n-i-k \brack j-i-k}\right ),$$ and $Z=\sum_{i=0}^nN^i{n\brack i}=N^{\overline{n}},$ where the overline means rising factorial.

Edit: Implementing this seems that $\mathbb{E}[|M|]$ goes to $N$. To complete the argument, notice that you can exchange the sum of $j$ and $k$ to get $$\frac{1}{N^{\overline{n}}}\sum _{0\leq k,i\leq n}i\binom{n}{i}\binom{n-i}{k}(-1)^kN^{i+k}N^{\overline{n-i-k}}$$ and if you study the term inside, you will get that looks like $$\frac{\binom{n}{i+k}}{\binom{N+n-1}{i+k}i!k!}$$ and so this will go to $1/(i!k!)$ and then you will be getting $$\sum _{k,i}i\frac{(-N)^iN^k}{i!k!}=Ne^{-N}e^{N}=N$$