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

I ran into an expression calculating the expected value of $\exp(i t \sigma)$ where $\sigma$ is the total number of cycles in a uniformly chosen $S_n$ element. The expression is $$E_n (\exp(i t \sigma)) = \Gamma(n + \exp(it)) / (\Gamma(\exp(it)) n!)$$ where $E_n$ denotes the expectation under the uniform distribution on $S_n$. The paper then claims that using Binet's form of Stirling approximation one can get $$E_n (\exp(it \sigma)) = n^{\exp(it) -1}/\Gamma(\exp(it)) (1 + o(1))$$

Then here comes the derivation I cannot understand: using the last expression, they claim one gets the following central limit theorem $$\lim_{n \to \infty} E_n(\exp(it (\sigma - \log n)/\sqrt{\log n})) = \exp( -1/2 t^2)$$ for any real $t$.

I would highly appreciate anyone who can tell me why this is true. It appears to be related to some property of the Gamma function over the complex number. The relevant paper is Shepp and Lloyd: Ordered lengths in a random permutation John Jiang

share|cite|improve this question
Welcome to MathOverflow. (I fixed your latex and a few typos.) – François G. Dorais Mar 26 '10 at 5:06
Note that by Taylor's theorem n^{exp(it)-1} = exp(log n * it - (log n)*t^2/2 + O((log n)*t^3)) and 1/Gamma(exp(it)) = 1 + O(t). Therefore n^{exp(it)-1}/Gamma(exp(it)) = exp(log n * it - (log n) * t^2/2 + O((log n)*t^3)). Now what happens when you multiply the above formula by exp(-log n * t) and then substitute t/sqrt(log n) for t? You get e^{-t^2/2} in the limit!! :-) – maks Mar 26 '10 at 5:17
[There is a small typo in the last line: multiply by exp(-log n * it)] – maks Mar 26 '10 at 5:18
I think that's "Ordered cycle lengths in a random permutation." – Douglas Zare Mar 26 '10 at 5:26
Thanks Maks! And Francois for fixing the typos. – John Jiang Mar 26 '10 at 6:20
up vote 6 down vote accepted

Note that $exp(it) = 1 + it - t^2/2 + O(t^3)$ uniformly in $t \in \mathbb{R}$. Thus $n^{exp(it)-1} = exp(it \cdot \log n - \log n \cdot t^{2}/2 + O(t^3 \cdot \log n))$ and also by Taylor's theorem $1/\Gamma(exp(it)) = 1 + O(t)$ when $t$ is small (but in fact also for all real $t \in \mathbb{R}$ by periodicity). Thus $$n^{exp(it)-1}/\Gamma(exp(it)) = exp(it \cdot \log n - \log n \cdot t^2/2 +O(t^3 \cdot \log n))$$ Multiplying both sides by $exp(- it \cdot \log n)$ and substituting $t := t \cdot (\log n)^{-1/2}$ we obtain as $n \rightarrow \infty$ the desired limit, $exp(-t^2/2)$.

share|cite|improve this answer
I added spaces in front of the inline formulas so that they do not extend off the side. – Douglas Zare Mar 26 '10 at 21:20

I was curious as to the more exact behaviour as $n\rightarrow\infty$ of this quantity. By following maks' derivation but using more terms (any CAS can be helpful here), one gets that the 'next' term in the asymptotic expansion is $$\exp(\frac{1}{6}\frac{it\cdot(6\gamma-t^2)}{\sqrt{\ln(n)}}).$$ $\pi^2$ shows up in the next term, $\zeta(3)$ in the next, $\zeta(4)$ (in term of $\pi^4$) next, $\zeta(5)$, etc.

share|cite|improve this answer

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.