You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'Combining Stein’s method with heat kernel techniques, we study the function $Tr(AO)$, where $A$ is a fixed $n \times n$ matrix over $\mathbb{R}$ such that $Tr(AA^t)=n$, and $O$ is from the Haar measure of the orthogonal group $O(n,\mathbb{R})$. It is shown that the total variation distance of the random variable $Tr(AO)$ to a standard normal random variable is bounded by $\frac{2 \sqrt{2}}{n-1}$, slightly improving the constant in a bound of Meckes, which was obtained by completely different methods.'
address:
- |
    Department of Mathematics\
    University of Southern California\
    Los Angeles, CA, 90089, USA
- |
    Department of Statistics and Applied Probability\
    National University of Singapore\
    Singapore 117546
author:
- Jason Fulman
- Adrian Röllin
date:
- 
- 'Version of September 8, 2011'
title: 'Stein’s method, heat kernel, and linear functions on the orthogonal groups'
---

Introduction {#intro}
============

Let $O(n,\mathbb{R})$ denote the group of $n \times n$ real orthogonal matrices, and let $O$ be from the Haar measure on $O(n,\mathbb{R})$. Let $A$ be a fixed $n \times n$ real matrix, satisfying the constraint $Tr(AA^t)=n$, and let $W=Tr(AO)$. Letting $\Phi(x) = \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^x e^{-t^2/2} dt$ denote the cumulative distribution function of a standard normal random variable, a result of D’Aristotile, Diaconis and Newman [@DDN] is that $$sup_{Tr(AA^t)=n \atop -\infty<x<\infty} |{\mathbb{P}}(W \leq x) - \Phi(x)| \rightarrow 0$$ as $n \rightarrow \infty$. A recent paper of Meckes [@Me] shows that for all $n \geq 2$, the total variation distance between the law of $W$ and a standard normal is at most $\frac{2 \sqrt{3}}{n-1}$. In this paper we use a very different construction than that of Meckes and obtain a slightly better total variation bound of $\frac{2 \sqrt{2}}{n-1}$.

As Meckes observes, this problem has quite a bit of history. Borel in [@B] showed that if $X$ is a random vector on the $n-1$ dimensional unit sphere, with first coordinate $X_1$, then ${\mathbb{P}}(\sqrt{n} X_1 \leq t)
\rightarrow \Phi(t)$ as $n \rightarrow \infty$. Since the first column of a Haar distributed orthogonal matrix is uniformly distributed on the sphere, Borel’s theorem follows from the central limit theorem for $W$, taking $A= \sqrt{n} \oplus {\bf 0}$. Various generalizations of Borel’s theorem, focusing on blocks of entries of a Haar distributed orthogonal matrix, can be found in the papers [@DEL], [@DF], [@Ji].

In the special case that $A=I$, $W$ becomes the trace of a Haar distributed orthogonal matrix. Diaconis and Mallows (see [@D]) proved that $Tr(O)$ is approximately normal. Stein [@St2] proved there exists a constant $C_r$ so that the total variation distance between $Tr(O)$ and a standard normal is at most $C_r (n-1)^{-r}$, and Johansson [@J] proved a central limit in the Kolmogorov metric with error term $O(e^{-cn})$ for some $c>0$. Diaconis and Shahshahani [@DS] proved multivariate central limit theorems (without error terms) for the joint limiting distribution of $Tr(O),Tr(O^2),\cdots,Tr(O^k)$, with $k$ fixed. Fulman [@F] used heat kernel methods to prove central limit theorems with error terms for $Tr(O^k)$ with $k$ growing; this was extended to the multivariate setting by Döbler and Stolz [@DoSt].

Another reason for studying $Tr(AO)$ is the similarity with Hoeffding’s combinatorial central limit theorem [@H], which proves a central limit theorem for $Tr(AP)$ where $P$ is a random permutation matrix. Stein’s method has been used to give explicit bounds for Hoeffding’s theorem; see [@Bol] or [@CGS].

It should be possible to extend the results in the current paper to a multivariate setting. Indeed, Chatterjee and Meckes [@CM] prove bounds in the Wasserstein metric between the distribution of $Tr(A_1 O),\cdots,Tr(A_k O)$ and a multivariate normal, where $A_1,\cdots,A_k$ are fixed and $O$ is from Haar measure of the orthogonal group; see also Collins and Stolz [@CS] for an extension of [@CM] (without error terms) to compact symmetric spaces.

Extensions of our results to the unitary and symplectic groups appear in the companion paper [@F2], which slightly improves Meckes’ constant in the unitary case [@Me]. For the unitary groups there is also an interesting recent paper [@KMS] which uses characteristic functions and a heavy dose of analysis to prove a central limit theorem for $Tr(AU)$ with error term $O(n^{-2+b})$ where $0 \leq b <1$ depends on the leading order asymptotics of the greatest singular value of $A$.

Although our results are only a slight improvement of those of Meckes [@Me], the heat kernel is a remarkable tool appearing in many parts of mathematics (see [@La] for a spirited defense of this statement with many references), and we suspect that the blending of heat kernel techniques with Stein’s method will be useful for other problems.

The organization of this paper is as follows. \[zonal\] gives background on symmetric functions and the orthogonal group. \[heatsec\] gives background on the heat kernel and Laplacian of the orthogonal group. \[O\] uses tools from \[zonal\] and \[heatsec\] to prove our main results.

Symmetric functions and the orthogonal group {#zonal}
============================================

In this paper we use the zonal polynomial $Z_{\lambda}$ (with parameter 2) defined in Section 7.2 of Macdonald [@Mac]. To show the usefulness of symmetric functions, we give a quick proof that $W=Tr(AO)$ is asymptotically normal, if $O$ is from Haar measure of the orthogonal group and $A$ satisfies $AA^t=n$. As noted in Meckes [@Me] one can assume without loss of generality that $A$ is diagonal: let $A=UDV$ be the singular value decomposition of $A$. Then $W=Tr(UDVO)=Tr(DVOU)$, and the distribution of $VOU$ is the same as the distribution of $O$ by the translation invariance of Haar measure.

The key to proving a central limit theorem for $W$ is the following lemma from page 423 of [@Mac] (which should also prove useful for carrying the results of [@KMS] over to the orthogonal case). For its statement, recall that the hooklength of a box $x$ is $1$ + number of boxes in same row as $x$ to right of $x$ + number of boxes in same column of $x$ beneath $x$. In the diagram below representing a partition of 7, each box is filled with its hook length: $$\begin{array}{c c c c} \framebox{6}& \framebox{4}& \framebox{2}&
\framebox{1} \\ \framebox{3}& \framebox{1}&& \\ \framebox{1} &&&
\end{array}.$$

\[mom1\] Let $Z_{\lambda}$ be the zonal polynomial (with parameter 2) and let $h(2 \lambda)$ be the product of the hooklengths of the partition $2 \lambda$, whose rows have length twice those of $\lambda$. Let $A$ have singular values $a_1,\cdots,a_n$. Then $$\int_{O(n,\mathbb{R})} exp(t \cdot Tr[AO]) dO = \sum_{\lambda} \frac{t^{|2 \lambda|}}{h(2 \lambda)}  \frac{Z_{\lambda}(a_1^2,\cdots,a_n^2)}
{Z_{\lambda}(1,\cdots,1)} .$$

Lemma \[mom1\] immediately implies that ${\mathbb{E}}(W)=0$. Since by page 410 of [@Mac] one has that $Z_1(a_1^2,\cdots,a_n^2)=a_1^2+\cdots+a_n^2=n$, it follows that $Var(W)=1$. Lemma \[mom1\] also implies the following central limit theorem for $W$.

Let $A$ satisfy $Tr(AA^t)=n$, and let $O$ be from the Haar measure of the orthogonal group $O(n,\mathbb{R})$. Then as $n \rightarrow \infty$, $W=Tr(AO)$ tends to the standard normal distribution with mean 0 and variance 1.

Lemma \[mom1\] implies that ${\mathbb{E}}(W^r)=0$ for $r$ odd, so suppose that $r$ is even. From page 409 of [@Mac], $$Z_{\lambda}(1,\cdots,1) = \prod_{(i,j) \in \lambda} (n-i+2j-1).$$ With $\lambda$ fixed this is asymptotic to $n^{|\lambda|} (1+O(1/n))$.

Recall we can assume that $A$ is diagonal with entries $(a_1,\cdots,a_n)$. Hence by Lemma \[mom1\], ${\mathbb{E}}[Tr(AO)^r]$, with $A$ fixed, $r$ fixed and even, is asymptotic to $$\begin{aligned}
& & \frac{r!}{n^{r/2}} \sum_{|\lambda|=r/2} \frac{Z_{\lambda}(a_1^2,\cdots,a_n^2)}{h(2 \lambda)} \\
& = & \frac{r!}{n^{r/2} 2^{r/2} (r/2)!} \sum_{|\lambda|=r/2} \frac{2^{r/2} (r/2)! Z_{\lambda}(a_1^2,\cdots,a_n^2)}{h(2 \lambda)} \\
& = & \frac{r!}{n^{r/2} 2^{r/2} (r/2)!} (a_1^2+\cdots+a_n^2)^{r/2} \\
& = & \frac{r!}{2^{r/2} (r/2)!}. \end{aligned}$$ The penultimate equality was from page 406 of [@Mac].

It follows that for fixed $r$, $E(W^r)$ is $0$ for $r$ odd, and is asymptotic to $(r-1) \cdots (3)(1)$ for $r$ even. The method of moments ([@D]) implies that $W$ is asymptotically normal with mean 0 and variance 1.

It will also be useful to work with Schur functions $s_{\lambda}(AO)$ evaluated on the eigenvalues of $AO$. An in-depth treatment of Schur functions is in Chapter 1 of [@Mac]. From pages 421-422 of [@Mac], one can express the integral of a Schur function over the orthogonal group in terms of zonal polynomials as follows:

\[rains1\] Let $s_{\lambda}$ be the Schur function and $Z_{\lambda}$ be the zonal polynomial with parameter 2. Then for any partition $\lambda$ of length $\leq n$, $$\int_{O(n,\mathbb{R})} s_{\lambda}(AO) dO = \begin{array}{ll}
\frac{Z_{\kappa}(a_1^2,\cdots,a_n^2)}
{Z_{\kappa}(1,\cdots,1)} & \mbox{if \ $\lambda=2 \kappa$}\\
0 & \mbox{otherwise}
\end{array}$$

The power sum symmetric functions $p_{\lambda}$ will also be useful. To define these, given a matrix $M$, if $\lambda$ is an integer partition and $m_j$ denotes the multiplicity of part $j$ in $\lambda$, we set $p_{\lambda}(M)= \prod_j Tr(M^j)^{m_j}$. For example, $p_{5,3,3}(M)=Tr(M^5)Tr(M^3)^2$. Sometimes we suppress the $M$ and use the notation $p_{\lambda}$. Lemma \[express\], from page 114 of [@Mac], expresses power sum symmetric functions in terms of Schur functions $s_{\lambda}$, and will be used later in the paper.

\[express\] Let $\chi^{\lambda}_{\rho}$ denote the value of the irreducible character of the symmetric group parameterized by $\lambda$ on the conjugacy class of elements of type $\rho$. Then $$p_{\rho} = \sum_{\lambda} \chi^{\lambda}_{\rho} s_{\lambda} .$$

Heat kernel and Laplacian of the orthogonal group {#heatsec}
=================================================

Recall that a pair $(W,W')$ of random variables is called exchangeable if $(W,W')$ has the same distribution as $(W',W)$. To construct an exchangeable pair to be used in our applications, we use the heat kernel of $G$. See [@G], [@Ro] for a detailed discussion of heat kernels on compact Lie groups. The papers [@L],[@Liu], [@R] illustrate combinatorial uses of heat kernels on compact Lie groups, and [@Liu] also discusses the use of the heat kernel for finite groups.

The heat kernel on $G$ is defined by setting for $x,y \in G$ and $t \geq 0$, $$\label{heat} K(t,x,y) =
\sum_{n \geq 0} e^{-\lambda_n t} \phi_n(x) \overline{\phi_n(y)},$$ where the $\lambda_n$ are the eigenvalues of the Laplacian repeated according to multiplicity, and the $\phi_n$ are an orthonormal basis of eigenfunctions of $L^2(G)$; these can be taken to be the irreducible characters of $G$.

We use the following properties of the heat kernel. Here $\Delta$ denotes the Laplacian of $G$, and $e^{t \Delta}$ is defined as $I+ t \Delta+ t^2 \frac{\Delta^2}{2!} + \cdots$. Part 2 of Lemma \[spectral\] is immediate from the expansion , and parts 1 and 3 of Lemma \[spectral\] are on page 198 of [@G].

\[spectral\] Let $G$ be a compact Lie group, $x,y \in G$, and $t \geq 0$.

1.  $K(t,x,y)$ converges and is non-negative for all $x,y,t$.

2.  $\int_{y \in G} K(t,x,y) dy = 1$, where the integration is with respect to Haar measure of $G$.

3.  $e^{t \Delta} \phi(x) = \int_{y \in G} K(t,x,y) \phi(y) dy$ for smooth $\phi$.

The symmetry in $x$ and $y$ of $K(t,x,y)$ shows that the heat kernel is a reversible Markov process with respect to the Haar measure of $G$. It is a standard fact [@RR], [@Stn] that reversible Markov processes lead to exchangeable pairs $(W,W')$. Namely suppose one has a Markov chain with transition probabilities $K(x,y)$ on a state space $X$, and that the Markov chain is reversible with respect to a probability distribution $\pi$ on $X$. Then given a function $f$ on $X$, if one lets $W=f(x)$ where $x$ is chosen from $\pi$ and $W'=f(x')$ where $x'$ is obtained by moving from $x$ according to $K(x,y)$, then $(W,W')$ is an exchangeable pair. In the special case of the heat kernel on a compact Lie group $G$, given a function $f$ on $G$, one can construct an exchangeable pair $(W,W')$ by letting $W=f(O)$ where $O$ is chosen from Haar measure, and $W'=f(O')$, where $O'$ is obtained by moving time $t$ from $O$ via the heat kernel. To define the exchangeable pair $(W,W')$ used in this paper, we further specialize by setting $f(O)=Tr(AO)$.

To analyze the heat kernel on the orthogonal groups, we need to understanding the corresponding Laplacian. Proposition 2.7 of the paper [@L] gave an explicit description of the Laplacian for $SO(n,\mathbb{R})$. The same calculations work for $O(n,\mathbb{R})$ (which shares the same Lie algebra with $SO(n,\mathbb{R})$), and yield the following result.

\[Oform\] Let $A$ satisfy $Tr(AA^t)=n$. Then

1.  $$\Delta_{O(n)} p_1(AO) = - \frac{(n-1)}{2} p_1(AO).$$

2.  $$\Delta_{O(n)} p_{1,1}(AO) = -(n-1) p_{1,1}(AO) - p_2(AO) + n .$$

Main results {#O}
============

To begin we describe the exchangeable pair $(W,W')$. Namely $W=Tr(AO)=p_1(AO)$, where as explained earlier one can assume $A$ is diagonal. We fix $t>0$, and motivated by \[heatsec\], define $$W' = e^{t \Delta}(W) = W + \sum_{k \geq 1} \frac{t^k}{k!} \Delta^k(W).$$

Lemma \[Ocond1\] computes the conditional expectation ${\mathbb{E}}[W'|O]$.

\[Ocond1\] $${\mathbb{E}}[W'|O] = \left( 1 - \frac{t(n-1)}{2} \right) W + O(t^2).$$

Applying part 3 of Lemma \[spectral\] and part 1 of Lemma \[Oform\], $$\begin{aligned}
 {\mathbb{E}}[W'|O] & = & e^{t \Delta}(W)\\
& = &  W + t \Delta W + O(t^2) \\
& = & W + t \frac{-(n-1)}{2} W + O(t^2),\end{aligned}$$ as desired.

Lemma \[Ocond2\] computes ${\mathbb{E}}[(W'-W)^2|O]$.

\[Ocond2\] $${\mathbb{E}}[(W'-W)^2|O] = t [ n - p_2(AO)] + O(t^2) .$$

Clearly $${\mathbb{E}}[(W'-W)^2|O] = {\mathbb{E}}[(W')^2|O] - 2W {\mathbb{E}}[W'|O] + W^2.$$ By part 3 of Lemma \[spectral\] and part 2 of Lemma \[Oform\], $$\begin{aligned}
{\mathbb{E}}[(W')^2|O] & = & W^2 + t \Delta p_{1,1}(AO) + O(t^2) \\
& = & W^2 + t \left[-(n-1) p_{1,1}(AO) - p_2(AO) + n \right] + O(t^2).\end{aligned}$$

By Lemma \[Ocond1\], $-2 W {\mathbb{E}}[W'|O]$ is equal to $$-2W^2 + t (n-1)p_{1,1}(AO) + O(t^2).$$ Thus $${\mathbb{E}}[(W')^2|O] - 2W {\mathbb{E}}[W'|O] + W^2 = t[n - p_2(AO)] + O(t^2).$$

Lemma \[Ovar\] bounds the variance of $p_2(AO)$.

\[Ovar\] Suppose that $n \geq 4$. Then $Var[p_2(AO)] \leq 2$.

By definition, $Var[p_2(AO)]={\mathbb{E}}[p_{2,2}(AO)] - ({\mathbb{E}}[p_2(AO)])^2$.

From Lemma \[express\], $$p_2(AO) = -s_{(1,1)}(AO) + s_2(AO).$$ Then Lemma \[rains1\] gives that $\int_{O(n,\mathbb{R})} -s_{(1,1)}(AO) dO= 0$ and (combined with page 410 of [@Mac]) that $$\int_{O(n,\mathbb{R})} s_2(AO) dO = \frac{Z_{1}(a_1^2,\cdots,a_n^2)}{Z_{1}(1,\cdots,1)} = \frac{a_1^2+\cdots+a_n^2}{n} = 1.$$ Thus ${\mathbb{E}}[p_2(AO)] = 1$.

To compute $ {\mathbb{E}}[p_{2,2}(AO)]$, Lemma \[express\] gives that $$p_{2,2}(AO) = \chi^{4}_{(2,2)} s_4 + \chi^{(3,1)}_{(2,2)} s_{(3,1)} + \chi^{(2,2)}_{(2,2)} s_{(2,2)}
+ \chi^{(2,1,1)}_{(2,2)} s_{(2,1,1)} + \chi^{(1,1,1,1)}_{(2,2)} s_{(1,1,1,1)} .$$ Lemma \[rains1\] and the character table of $S_4$ then give that

$$\begin{aligned}
{\mathbb{E}}[p_{(2,2)}(AO)] & = &  {\mathbb{E}}[\chi^{4}_{(2,2)} s_4(AO) + \chi^{(2,2)}_{(2,2)} s_{(2,2)}(AO)] \\
& = & {\mathbb{E}}[s_4(AO) + 2 s_{(2,2)}(AO)] \\
& = & \frac{Z_2(a_1^2,\cdots,a_n^2)}{Z_2(1,\cdots,1)} + 2 \frac{Z_{(1,1)}(a_1^2,\cdots,a_n^2)}{Z_{(1,1)}(1,\cdots,1)}.\end{aligned}$$

From pages 382 and 383 of [@Mac], it follows that $$\frac{Z_2(a_1^2,\cdots,a_n^2)}{Z_2(1,\cdots,1)} = \frac{n^2 + 2 (a_1^4+\cdots+a_n^4)}{n^2+2n}$$ and that $$\frac{Z_{(1,1)}(a_1^2,\cdots,a_n^2)}{Z_{(1,1)}(1,\cdots,1)} = \frac{n^2-(a_1^4+\cdots+a_n^4)}{n^2-n}.$$

Thus $$Var[p_2(AO)] = \left[ \frac{n^2}{n^2+2n} + \frac{2n^2}{n^2-n} -1 \right] - (a_1^4+\cdots+a_n^4) \left[ \frac{2}{n^2-n} - \frac{2}{n^2+2n} \right]$$ By the method of Lagrange multipliers, $a_1^4+\cdots+a_n^4$ is minimized subject to the constraint $a_1^2+\cdots+a_n^2=n$ when $a_1=\cdots=a_n=1$. But $$\left[ \frac{n^2}{n^2+2n} + \frac{2n^2}{n^2-n} -1 \right] - n\left[ \frac{2}{n^2-n} - \frac{2}{n^2+2n} \right] = 2,$$ implying that $Var[p_2(AO)] \leq 2$, as claimed.

Next we compute expected values of low order moments of $W'-W$.

\[Olow\] Suppose that $n \geq 4$. Then

1.  ${\mathbb{E}}(W'-W)^2 = t (n-1) + O(t^2)$.

2.  ${\mathbb{E}}(W'-W)^4 = O(t^2)$.

3.  ${\mathbb{E}}|W'-W|^3 = O(t^{3/2})$.

Lemma \[Ocond2\] implies that ${\mathbb{E}}(W'-W)^2 = t {\mathbb{E}}\left[ n-p_2(AO) \right] + O(t^2)$. By the proof of Lemma \[Ovar\], ${\mathbb{E}}[p_2(AO)] = 1$. Thus $${\mathbb{E}}(W'-W)^2 = t(n-1) + O(t^2),$$ as claimed.

For part 2, first note that since $${\mathbb{E}}[(W'-W)^4] = {\mathbb{E}}(W^4) - 4 {\mathbb{E}}(W^3W') + 6 {\mathbb{E}}[W^2(W')^2] - 4 {\mathbb{E}}[W (W')^3] + {\mathbb{E}}[(W')^4],$$ exchangeability of $(W,W')$ gives that $$\begin{aligned}
{\mathbb{E}}(W'-W)^4 & = & 2 {\mathbb{E}}(W^4) -8 {\mathbb{E}}(W^3W') + 6 {\mathbb{E}}[W^2(W')^2] \\
& = & 2 {\mathbb{E}}(W^4) -8 {\mathbb{E}}[W^3 {\mathbb{E}}[W'|O]] + 6 {\mathbb{E}}[W^2 {\mathbb{E}}[(W')^2|O]].\end{aligned}$$

By Lemma \[Ocond1\], $${\mathbb{E}}[W'|O] = \left( 1 - \frac{t(n-1)}{2} \right) W + O(t^2),$$ and by the proof of Lemma \[Ocond2\], $${\mathbb{E}}[(W')^2|O] = W^2 + t \left[-(n-1) p_{1,1}(AO) - p_2(AO) + n \right] + O(t^2).$$ Thus $$\begin{aligned}
& & {\mathbb{E}}(W'-W)^4 \\
& = & 2 {\mathbb{E}}(W^4) - 8 {\mathbb{E}}(W^4) + 6 {\mathbb{E}}(W^4) \\
& & + t \left[ 4(n-1) {\mathbb{E}}(W^4) + 6 {\mathbb{E}}[W^2 [-(n-1)p_{1,1}(AO)-p_2(AO)+n]] \right] \\ & & + O(t^2) \\
& = & t \left[ - 2(n-1) {\mathbb{E}}[p_{1,1,1,1}(AO)] - 6 {\mathbb{E}}[p_{2,1,1}(AO)] +6n \right] + O(t^2),\end{aligned}$$ where we used that ${\mathbb{E}}(W^2)=1$.

From Lemma \[express\], $p_{1,1,1,1}(AO)$ is equal to $$\chi^{4}_{(1,1,1,1)} s_4 + \chi^{(3,1)}_{(1,1,1,1)} s_{(3,1)} + \chi^{(2,2)}_{(1,1,1,1)} s_{(2,2)}
+ \chi^{(2,1,1)}_{(1,1,1,1)} s_{(2,1,1)} + \chi^{(1,1,1,1)}_{(1,1,1,1)} s_{(1,1,1,1)} .$$ From Lemma \[rains1\] and the fact that $\chi^{4}_{(1,1,1,1)}=1$ and $\chi^{(2,2)}_{(1,1,1,1)}=2$, it follows that $$\begin{aligned}
{\mathbb{E}}[p_{1,1,1,1}(AO)] & = & {\mathbb{E}}[s_4(AO) + 2 s_{2,2}(AO)] \\
& = & \frac{Z_2(a_1^2,\cdots,a_n^2)}{Z_2(1,\cdots,1)} + 2 \frac{Z_{1,1}(a_1^2,\cdots,a_n^2)}{Z_{1,1}(1,\cdots,1)},\end{aligned}$$ where $Z_{\lambda}$ denotes the zonal polynomial with parameter two.

Similarly, $p_{2,1,1}(AO)$ is equal to $$\chi^{4}_{(2,1,1)} s_4 + \chi^{(3,1)}_{(2,1,1)} s_{(3,1)} + \chi^{(2,2)}_{(2,1,1)} s_{(2,2)}
+ \chi^{(2,1,1)}_{(2,1,1)} s_{(2,1,1)} + \chi^{(1,1,1,1)}_{(2,1,1)} s_{(1,1,1,1)} .$$ From Lemma \[rains1\] and the fact that $\chi^{4}_{(2,1,1)}=1$ and $\chi^{(2,2)}_{(2,1,1)}=0$, it follows that $${\mathbb{E}}[p_{2,1,1}(AO)] = {\mathbb{E}}[s_4(AO)] = \frac{Z_2(a_1^2,\cdots,a_n^2)}{Z_2(1,\cdots,1)} ,$$ with $Z_{\lambda}$ the zonal polynomial with parameter 2.

As in the proof of Lemma \[Ovar\], one has that $$\frac{Z_2(a_1^2,\cdots,a_n^2)}{Z_2(1,\cdots,1)} = \frac{n^2 + 2 (a_1^4+\cdots+a_n^4)}{n^2+2n}$$ and that $$\frac{Z_{(1,1)}(a_1^2,\cdots,a_n^2)}{Z_{(1,1)}(1,\cdots,1)} = \frac{n^2-(a_1^4+\cdots+a_n^4)}{n^2-n}.$$ Plugging in these values, one obtains that $$\begin{aligned}
& & {\mathbb{E}}(W'-W)^4 \\
& = & -2(n-1) t \left[ \frac{n^2+2(a_1^4+\cdots+a_n^4)}{n^2+2n} + \frac{2(n^2-(a_1^4+\cdots+a_n^4))}{n^2-n} \right] \\
&  & -6t \left[ \frac{n^2+2(a_1^4+\cdots+a_n^4)}{n^2+2n} \right]  + 6nt + O(t^2) \\
& = & O(t^2), \end{aligned}$$ proving part 2 of the theorem.

For part 3 of the theorem, one uses the Cauchy-Schwarz inequality to obtain that $${\mathbb{E}}|W'-W|^3 \leq \sqrt{{\mathbb{E}}(W'-W)^2 {\mathbb{E}}(W'-W)^4}.$$ Part 3 then follows from parts 1 and 2 of the theorem.

\[niceh\] Let $f$ be a twice differentiable function with bounded second derivative. Then $${\mathbb{E}}[f'(W)-Wf(W)] = {\mathbb{E}}\left[ \frac{p_2(AO)-1}{n-1} f'(W) \right].$$

Since $(W,W')$ is an exchangeable pair, $$\begin{aligned}
0 & = & {\mathbb{E}}[(W'-W)[f(W)+f(W')]] \\
& = & {\mathbb{E}}[(W'-W)[2f(W)+[f(W')-f(W)]]] \\
& = & 2 {\mathbb{E}}[(W'-W)f(W)] + {\mathbb{E}}[(W'-W)(f(W')-f(W))].\end{aligned}$$

Now by Lemma \[Ocond1\], $$\begin{aligned}
2 {\mathbb{E}}[(W'-W)f(W)] & = & 2 {\mathbb{E}}[ f(W) {\mathbb{E}}[(W'-W)|O]] \\
& = & -t (n-1) {\mathbb{E}}[ f(W) W] + O(t^2).\end{aligned}$$

By Taylor’s theorem and Lemma \[Ocond2\], it follows that $$\begin{aligned}
{\mathbb{E}}[(W'-W)(f(W')-f(W))] & = & {\mathbb{E}}[(W'-W) [f'(W) (W'-W)] + R] \\
& = & {\mathbb{E}}[ f'(W) {\mathbb{E}}[(W'-W)^2|O] + R] \\
& = & {\mathbb{E}}[ t f'(W) [ n - p_2(AO)] +R] + O(t^2), \\\end{aligned}$$ with $|R| \leq \frac{||f^{''}||}{2} |W'-W|^3$, where $||\cdot||$ denotes the supremum norm. From part 3 of Lemma \[Olow\], it follows that $R=O(t^{3/2})$.

Summarizing, we have that $$\begin{aligned}
0 & = & 2 {\mathbb{E}}[(W'-W)f(W)] + {\mathbb{E}}[(W'-W)(f(W')-f(W))] \\
& = & -t (n-1) {\mathbb{E}}[ f(W) W] + t {\mathbb{E}}[ f'(W) [ n - p_2(AO)]] + O(t^{3/2}).\end{aligned}$$ Dividing both sides of this equation by $t$ and then letting $t \rightarrow 0$ completes the proof.

Now we prove our main result.

The total variation distance between $W$ and a standard normal is at most $\frac{2 \sqrt{2}}{n-1}$.

Note that the total variation distance between two random variables $W$ and $Z$ can be described as

$$d_{TV}(W,Z) = sup_h | {\mathbb{E}}h(W) - {\mathbb{E}}h(Z) |,$$ where the supremum ranges over all h that are continuous and bounded from below by $0$ and from above by $1$ and have compact support.

Any such function $h$ can be approximated by $C^{\infty}$ functions in the supremum norm. For fixed $h$ let $h_m$ be a sequence of $C^\infty$ functions such that $|| h - h_m || \rightarrow 0$ as $m \rightarrow \infty$ where $||\cdot||$ denotes the supremum norm.

Let $f_m$ be the solution to the Stein equation $$f_m'(x) - xf_m(x) = h_m(x) -{\mathbb{E}}h_m(Z),$$ where $Z$ has the standard normal distribution. Since we approximate $h$ by a compactly supported $C^{\infty}$ function, Formula (47) on page 25 of [@Stn] allows us to assume that $||f_m^{''}||$ is bounded. Applying Lemma \[niceh\] (so taking $T(AO) = \frac{p_2(AO)-1}{n-1}$ in the formulas below), we have

$$\begin{aligned}
& & | {\mathbb{E}}h(W) - {\mathbb{E}}h(Z) | \\
   &  \leq & 2 || h - h_m || + | {\mathbb{E}}h_m(W) - {\mathbb{E}}h_m(Z) | \\
   &  \leq & 2  || h - h_m || + | {\mathbb{E}}[ f'_m(W) - W f_m(W) ] | \\
   &  \leq & 2 || h - h_m || + \sqrt{Var(T)} || f'_m || \\
   &  \leq & 2 || h - h_m || + 2 \sqrt{Var(T)} || h_m - {\mathbb{E}}h_m(Z) || \\
   &  \leq & (2+ 4 \sqrt{Var(T)}) || h - h_m || + 2 \sqrt{Var(T)} || h - {\mathbb{E}}h(Z) ||.\end{aligned}$$

(The inequality $|| f'_m || \leq 2 || h_m - {\mathbb{E}}h_m(Z) ||$ is Formula (46) on page 25 of Stein [@Stn]).

Letting $m \rightarrow \infty$ we therefore have $$| {\mathbb{E}}h(W) - {\mathbb{E}}h(Z) | \leq 2 \sqrt{Var(T)} || h  - {\mathbb{E}}h(Z) ||$$ for any continuous function h. As $|| h - {\mathbb{E}}h(Z) || \leq 1$ and $Var(T) \leq \frac{2}{(n-1)^2}$ by Lemma \[Ovar\], the total variation bound now follows.

Acknowledgements {#acknowledgements .unnumbered}
================

Fulman was partially supported by NSF grant DMS 0802082. We thank Thierry Lévy for help computing with the orthogonal group Laplacian.

[99]{}

Bolthausen, E., An estimate of the remainder in a combinatorial central limit theorem, [*Z. Wahrsch. Verw. Gebiete*]{} [**66**]{} (1984), 379-386.

Borel, E., Sur les principes de la theorie cinétique des gaz, [*Annales de l’ecole Normal Sup.*]{} [**23**]{} (1906), 9-32.

Chatterjee, S. and Meckes, E., Multivariate normal approximation using exchangeable pairs, [*ALEA Lat. Am. J. Probab. Math. Stat.*]{} [**4**]{} (2008), 257-283.

Chen, L. H. Y., Goldstein, L., and Shao, Q., Normal approximation by Stein’s method. Probability and its Applications (New York). Springer, Heidelberg, 2011.

Collins, B. and Stolz, M., Borel theorems for random matrices from the classical compact symmetric spaces, [*Ann. Probab.*]{} [**36**]{} (2008), 876-895.

D’Aristotile, A., Diaconis, P., and Newman, C., Brownian motion and the classical groups, in [*Probability, statistics and their applications: papers in honor of Rabi Bhattacharya*]{}, 97–116, IMS Lecture Notes Monogr. Ser., 41, Inst. Math. Statist., Beachwood, OH, 2003.

Diaconis, P., Application of the method of moments in probability and statistics. Moments in mathematics (San Antonio, Tex., 1987), 125-142, Proc. Sympos. Appl. Math., 37, Amer. Math. Soc., Providence, RI, 1987.

Diaconis, P., Eaton, M., and Lauritzen, S., Finite de Finetti theorems in linear models and multivariate analysis, [*Scand. J. Statist.*]{} [**19**]{} (1992), 289-315.

Diaconis, P. and Freedman, D., A dozen de Finetti style results in search of a theory, [*Ann. Inst. H. Poincaré Probab. Statist.*]{} [**23**]{} (1987), 397-423.

Diaconis, P. and Shahshahani, M., On the eigenvalues of random matrices. Studies in applied probability. [*J. Appl. Probab.*]{} [**31A**]{} (1994), 49-62.

Döbler, C. and Stolz, M., Stein’s method and the multivariate CLT for traces of powers on the classical compact groups, arXiv:1012.3730 (2010).

Fulman, J., Stein’s method, heat kernel, and traces of powers of elements of compact Lie groups, arXiv:1005.1306 (2010).

Fulman, J., Stein’s method, heat kernel, and linear functions on the unitary and symplectic groups, preprint.

Grigor’yan, A., Heat kernel and analysis on manifolds, AMS/IP Studies in Advanced Mathematics, 47. American Mathematical Society, Providence, RI; International Press, Boston, MA, 2009.

Hoeffding, W., A combinatorial central limit theorem, [*Ann. Math. Statistics*]{} [**22**]{} (1951), 558-566.

Jiang, T., Maxima of entries of Haar distributed matrices, [*Probab. Theory Related Fields*]{} [**131**]{} (2005), 121-144.

Johansson, K., On random matrices from the compact classical groups, [*Ann. of Math.*]{} [**145**]{} (1997), 519-545.

Jorgenson, J. and Lang, S., The ubiquitous heat kernel. Mathematics unlimited—2001 and beyond, 655–683, Springer, Berlin, 2001.

Keating, J. P., Mezzadri, F. and Singphu, B., Rate of convergence of linear functions on the unitary group, [*J. Phys. A*]{} [**44**]{} (2011), no. 3, 035204, 27 pp.

Levy, T., Schur-Weyl duality and the heat kernel measure on the unitary group, [*Adv. Math.*]{} [**218**]{} (2008), 537-575.

Liu, K., Heat kernels, symplectic geometry, moduli spaces and finite groups, in [*Surveys in differential geometry: differential geometry inspired by string theory*]{}, 527-542, Surv. Differ. Geom., 5, Int. Press, Boston, MA, 1999.

Macdonald, I. G., Symmetric functions and Hall polynomials. Second edition. The Clarendon Press, Oxford University Press, New York, 1995.

Meckes, E., Linear functions on the classical matrix groups, [*Trans. Amer. Math. Soc.*]{} [**360**]{} (2008), 5355-5366.

Rains, E. M., Combinatorial properties of Brownian motion on the compact classical groups, [*J. Theoret. Probab.*]{} [**10**]{} (1997), 659-679.

Rinott, Y. and Rotar, V., On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics, [*Ann. Appl. Probab.*]{} [**7**]{} (1997), 1080-1105.

Rosenberg, S., The Laplacian on a Riemannian manifold. An introduction to analysis on manifolds. London Mathematical Society Student Texts, 31. Cambridge University Press, Cambridge, 1997.

Stein, C., The accuracy of the normal approximation to the distribution of the traces of powers of random orthogonal matrices. Stanford University Statistics Department technical report no. 470, (1995).

Stein, C., Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes-Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986.