MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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