Average over Random Permutations

Question

Consider $S_{n}$ the symmetric group and for each $\sigma\in S_{n}$ let $U_{\sigma}$ be its $n\times n$ permutation matrix. Let $A$ be an Hermitian $n\times n$ matrix. I'm interested in computing the average $$ \mathbb{E}(A):=\sum_{\sigma \in S_{n}}{w(\sigma) U_{\sigma} A U_{\sigma}^{*}} $$

where the $w(\sigma)$ are some positive weight adding up to one.

For instance some natural weights are the ones coming from the Ewens's probability distribution of parameter $\theta>0$ on $S_{n}$ defined as

$$ w(\sigma)=\frac{\theta^{K(\sigma)}}{\theta(\theta+1)\ldots(\theta+n-1)} $$

where $K(\sigma)$ is the number of disjoint cycles of $\sigma$. The case of $\theta=1$ is simply the uniform distribution on $S_{n}$. For the case $\theta=1$, it is known that $$ \mathbb{E}(A)=\alpha \frac{ee^{T}}{n} + \Bigg(\frac{\mathrm{Tr}(A)-\alpha}{n-1}\Bigg)\Bigg(I_{n}-\frac{ee^{T}}{n}\Bigg) $$ where $e$ is the vector $e^{T}=(1,1,\ldots,1)$ and $\alpha=\frac{e^{T}Ae}{n}$.

My question are:

• Is there anything known about the averages for the more general case of $\theta>0$.

• Are there known asymptotics results as $n\to\infty$?

Answer 1

You can calculate this directly. All you need to know is the probability that $(\sigma(i),\sigma(j))=(k,l)$ for each pair $(k,l)$. Write $e_i$ for the $i$th basis vector, $v=\sum_i e_i$. Let $E = \mathbb{E}(A)$. Then:

$$ e_i^T E e_i = \frac{\theta-1}{\theta+n-1} e_i^TAe_i + \frac{1}{\theta+n-1}\mathrm{Tr} A$$ and \begin{equation*} \begin{split} &(\theta+n-1)(\theta+n-2)e_i^T E e_j\\\\ &= v^TAv - \mathrm{Tr} A + (\theta-1) \left[e_i^TAv+v^TAe_j+e_j^TAe_i-e_i^TAe_i+e_j^TAe_j\right] + (\theta-1)^2 e_i^TAe_j \end{split} \end{equation*}

More details: $E_{ij}$ is the average of $A_{\sigma(i)\sigma(j)}$ over $\sigma$. When $i=j$ you get $E_{ii} = p A_{ii} + \frac{1-p}{n-1}\sum_{k\neq i} A_{kk}$ where $p$ is the probability that $\sigma(i)=i$. To calculate $p$ note that when $\sigma(n)=n$, the restriction of $\sigma$ to $[1,n-1]$ has precisely one less cycle. It follows that $\sum_{\sigma(n)=n}w_n(\sigma) = \frac{\theta}{\theta+n-1} \sum_{\tau\in S_{n-1}} w_{n-1}(\tau)$ where $w_n$ is the weighing above on $S_n$.

Similarly, for $i\neq j$ we have a sum over $A_{kl}$ with different weights. Easy cases include $k=i, l=j$ (this is $\frac{\theta^2}{(\theta+n-1)(\theta+n-2)}$ for the same reason as the diagonal), $k=j, l=i$ (this is $\frac{\theta}{(\theta+n-1)(\theta+n-2)}$ since now there is only one more cycle than the restriction to $[1,n-2]$), $k=i, l\neq i,j$ or $k\neq i,j, l=j$ (this is $\frac{\theta}{\theta+n-1}\left(1-\frac{\theta}{\theta+n-2}\right)$ since we fix one co-ordinate but not the other).

A bit more difficult is the case $k=j, l\neq i,j$ and $i\neq i,j, l=i$. Again for $i=n, j=n-1$ this means that $n, n-1$ are consecutive on a cycle of length at least $3$. The probability that $n$ is on a cycle of length $3$ is the complement of the probability that it is on a cycle of length $1$ or $2$ (that is $\frac{\theta}{\theta+n-1} + (n-1)\frac{\theta}{(\theta+n-1)(\theta+n-2)}$. Given that, the successor to $n$ on the cycle is uniformly distributed, so the probability that $k=j, l\neq i,j$ is $\frac{1}{n-1} \left(1 - \frac{\theta}{\theta+n-1} + (n-1)\frac{\theta}{(\theta+n-1)(\theta+n-2)}\right)$.

Finally, the probability that $k,l$ are distinct from $i,j$ is the complement of the above cases, and if so then the pair $k,l$ is uniformly distributed on the (n-2)(n-3) possibilities. It turns out each of these possibilities has probability $\frac{1}{(\theta+n-1)(\theta+n-2)}$.