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$?


1 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)}$.

  • $\begingroup$ Thanks Lior. I did not check all your calculations yet but the first equation is right. This was much simpler than I thought! $\endgroup$
    – ght
    Jul 15, 2011 at 23:52
  • 1
    $\begingroup$ Hi Lior, I added a line-break to make the display fit properly; hope that's ok with you. $\endgroup$
    – Suvrit
    Jul 16, 2011 at 0:21
  • 1
    $\begingroup$ @ght: Should I post the details of the calculation? They are not very enlightening. I can also email them to you. $\endgroup$ Jul 16, 2011 at 16:35
  • 1
    $\begingroup$ @Lior: Not all the details but can you please post the main steps so I can "award" you the answer. Thanks! $\endgroup$
    – ght
    Jul 16, 2011 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.