Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm trying to learn Stein's method by working through parts of Approximate Computation of Expectations, but I don't follow two of his bounds ((55) and (57)) in his proof of Hoeffding's combinatorial CLT on pages 38-42.

We have an $nxn$ array of numbers $\{a_{i,j}}$ such that for every $i$, $\sum_j a_{i,j} = 0$ and for every $j$, $\sum_i a_{i,j} = 0$, and also $\sum_i \sum_j a^2_{i,j} = n-1$. $\pi$ is a uniformly random permutation of $(1,\ldots,n$), and $(I,J)$ has probability $\frac{1}{n(n-1)}$ assigned to each $(i,j)$ for $i \neq j$.

For (55), we have that $$E[(W'-W)^2|\pi] = \frac{2}{n(n-1)}[(n-1)+(n+2)\sum_ia^2_{i\pi(i)} + \sum_{i \neq j} (a_{i \pi(j)}a_{j \pi(i)} + a_{i \pi(i)}a_{j \pi(j)})]$$.

How does Stein show that $$Var(E[(W'-W)^2|\pi]) \le C[\frac{1}{n^2} \sum_i Var(a^2_{i \pi(i)}) + \frac{1}{n^4} \sum_{i,j}(Var(a_{i \pi(j)}a_{j \pi(i)} + a_{i \pi(i)}a_{j \pi(j)}))$$ for some constant C?

Given the equality above, I don't think that knowing $W$ or $W'$ is necessary, but they form an exchangeable pair and their definitions are on page 39. Stein claims the bound follows from the equality and that "it is not hard to see."

For (57), we have that $$E|W'-W|^3 = E|a_{I\pi(J)} + a_{J\pi(I)} -a_{I\pi(I)}-a_{J\pi(J)}|^3$$.

How does Stein show that $$E|W'-W|^3 \leq \frac{C}{n^2}\sum_{i,j}|a_{ij}|^3$$ for some constant C?

Many thanks for the help.

share|improve this question
Minor point: I think your first "desired" formula is missing a Var somewhere, compared with the relevant page of the book which you've linked to. –  Yemon Choi Aug 10 '10 at 6:23
Thanks for spotting the mistake. I've edited the original post. –  Nelson Ray Aug 10 '10 at 15:32
I see how to show the second part now. It follows readily from the $c_r$ inequality, but I'm still working on the first part. –  Nelson Ray Aug 10 '10 at 16:33
This is pretty messy but not really hard. Given $i$, $\pi(i)$ is uniformly distributed in $1,\dots,n$; given $i\neq j$, the pair $(\pi(i),\pi(j))$ is uniformly distributed among distinct pairs. Given this information you can "just" grind it out (though it may take a few pages). There may also be a clever way to group things to make it fall out easily, but I don't see it offhand. –  Mark Meckes Aug 10 '10 at 17:06
Hi Mark, I started off that way initially and got stuck on some of the covariance calculations. I didn't think it was what Stein had in mind when he said "it is not hard to see," but I guess I can spend a bit more time on that approach. –  Nelson Ray Aug 10 '10 at 17:29

Your Answer


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

Browse other questions tagged or ask your own question.