Stein's Method

The goal is to find a Stein pair for our random variable \[ \begin{align} % U_{\pi} = \sum_{i,j,k \in [n]} f(\pi_i, \pi_j, \pi_k)X_i X_j X_k, U_{\pi} = \sum_{i,j,k \in [n]} f(i, j, k)X_{\pi_i} X_{\pi_j} X_{\pi_k}, \end{align} \] where \(\pi\) is uniformly distributed over the symmetric group \(S_n\) and \(n\) is the number of edges of our (fixed) graph. That is, \((U_{\pi}, U_{\sigma})\) are exchangeable, and satisfy three conditions: \[ \begin{align} &\mathbb{E}[U_{\sigma} - U_{\pi} | U_{\pi}] = - \lambda U_{\pi} + o(\lambda) \label{eqn:linearity} \\ &\mathbb{E}[(U_{\sigma} - U_{\pi})^2 | U_{\pi}] = 2\lambda + o(\lambda) \\ &\mathbb{E}[|U_{\sigma} - U_{\pi}|^3] = o(\lambda) \end{align} \]

To do so, let us introduce random variables \(P, Q, R\) that are uniform on \([n]\). Then, define a new permutation \(\sigma\) as \[ \begin{align} \sigma = \begin{cases} \pi & \mbox{if } P,Q,R \not\in \triangle \\ \pi \circ c(P,Q,R) & \mbox{if } P,Q,R \in \triangle \end{cases} \end{align} \] where \(c(i,j,k)\) denotes a permutation that cycles \((i,j,k)\) and leaves the rest of the indices unchanged.

Firstly, it is clear that \(\sigma\) is also uniform over \(S_n\). What’s not so clear is whether or not they are exchangeable11 According to Chatterjee, it suffices to show that they have the same distribution.

Now we are ready to prove the linearity condition \(\eqref{eqn:linearity}\). First, suppose we are in the setting \((P,Q,R) \in \triangle\). Then, let us decompose the triple sum into sums depending on how many indices lie in the set \(\left\{ P,Q,R \right\}\): \[ \begin{align} \sum_{i,j,k} \equiv \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 0} + \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 1} + \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 2} + \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 3} \end{align} \] Let’s go through the sums one by one, comparing them to their counterpart in \(U_{\pi}\). In the first sum, since none of the indices overlap, \(\sigma\) and \(\pi\) perform the identical permutation, so \[ \begin{align} \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 0} % f(\sigma_i, \sigma_j, \sigma_k)X_i X_j X_k f(i, j, k)X_{\sigma_i} X_{\sigma_j} X_{\sigma_k} = \sum_{|\left\{ i,j,k \right\} \cap \left\{ P,Q,R \right\}| = 0} % f(\pi_i, \pi_j, \pi_k)X_i X_j X_k, f(i, j, k)X_{\pi_i} X_{\pi_j} X_{\pi_k}, \end{align} \] giving the same sum as in \(U_{\pi}\). In the last sum, we have summands of the form \[ \begin{align} % f(\sigma_P, \sigma_Q, \sigma_R)X_P X_Q X_R f(P, Q, R)X_{\sigma_P} X_{\sigma_{Q}} X_{\sigma_R} = % f(\pi_Q, \pi_R, \pi_P)X_P X_Q X_R. f(P, Q, R)X_{\pi_Q} X_{\pi_R} X_{\pi_P} = f(P, Q, R)X_{\pi_P} X_{\pi_Q} X_{\pi_R}. \end{align} \] so again the summands match up. In the third sum, we have sums of the form \[ \begin{align} \sum_{k \not\in \left\{ P,Q,R \right\}} % f(\sigma_P, \sigma_Q, \sigma_k)X_P X_Q X_k f(P, Q, k)X_{\sigma_P} X_{\sigma_Q} X_{\pi_k} % =\sum_{k \not\in \left\{ P,Q,R \right\}} % f(P, Q, k)X_{\pi_Q} X_{\pi_R} X_{k}. \end{align} \] Here we use the fact that we’ve conditioned on \((P,Q,R) \in \triangle\), so that \(f(P, Q, k) = 0\) whenever \(k \neq R\). Thus, all the sums from both \(U_{\sigma}\) and \(U_{\pi}\) are zero. That leaves us with the second sum, which are of the form \[ \begin{align} \sum_{j,k \not\in \left\{ P,Q,R \right\}} f(P, j, k)X_{\sigma_P} X_{\pi_j} X_{\pi_k} = \sum_{j,k \not\in \left\{ P,Q,R \right\}} f(P, j, k)X_{\pi_Q} X_{\pi_j} X_{\pi_k} \end{align} \] Altogether, we have that whenever \((P,Q,R) \in \triangle\), \[ \begin{align} U_{\sigma} = U_{\pi} &+ \text{sums of the form} \sum_{j,k \not\in \left\{ P,Q,R \right\}} f(P, j, k)X_{\pi_Q} X_{\pi_j} X_{\pi_k} \\&- \text{sums of the form} \sum_{j,k \not\in \left\{ P,Q,R \right\}} f(P, j, k)X_{\pi_P} X_{\pi_j} X_{\pi_k} \end{align} \] So, at this point, we want the sums to be over \(j,k \in [n]\) instead of \(j,k \not\in \left\{ P,Q,R \right\}\). I’m unsure how to handle that, but let’s assume for the moment that I can change the sums. Then, we have that \[ \begin{align} \mathbb{E}[U_{\sigma} - U_{\pi} | \pi] &= \mathbb{P}[(P,Q,R) \in \triangle] \cdot \mathbb{E}[U_{\sigma} - U_{\pi} | \pi, (P,Q,R) \in \triangle] \\ &= \frac{|\triangle|}{\binom{n}{3}}\mathbb{E}[U_{\sigma} - U_{\pi} | \pi, (P,Q,R) \in \triangle], \end{align} \] which involves terms of the form \[ \begin{align} \mathbb{E} \sum_{j,k} f(P, j, k)X_{\pi_Q} X_{\pi_j} X_{\pi_k} \end{align} \] and \[ \begin{align} \mathbb{E} \sum_{j,k} f(P, j, k)X_{\pi_P} X_{\pi_j} X_{\pi_k}. \end{align} \] But the last term simplifies: \[ \begin{align} \mathbb{E} \sum_{j,k} f(P, j, k)X_{\pi_P} X_{\pi_j} X_{\pi_k} = \frac{1}{n} \sum_{i,j,k} f(i, j, k)X_{\pi_i} X_{\pi_j} X_{\pi_k} = \frac{1}{n} U_{\pi} \end{align} \] The first term is a little weirder: \[ \begin{align} \mathbb{E} \sum_{j,k} f(P, j, k)X_{\pi_Q} X_{\pi_j} X_{\pi_k} &= \frac{1}{n^2} \sum_{i,j,k,l} f(i, j, k)X_{\pi_l} X_{\pi_j} X_{\pi_k} \\&= \frac{1}{n^2} \sum_{i,j,k} f(i, j, k) X_{\pi_j} X_{\pi_k} \left(\sum_{l} X_{\pi_l} \right) \end{align} \] Combining the other two terms, we get something like \[ \begin{align} \frac{1}{n^2} \left(\sum_{l} X_{\pi_l} \right) \cdot \sum_{i,j,k} f(i, j, k) \left[ X_{\pi_i}X_{\pi_j} + X_{\pi_j} X_{\pi_k} + X_{\pi_i}X_{\pi_k} \right]. \end{align} \] I think we’ll need to put some conditions on this term. But the conclusion (glossing over some missing steps) is that22 The interesting thing about the summand is that triangles with all the same signs have the same value of 3, and triangles with different signs have the same value of -1, so it’s sort of counting the equivalence of signs. \[ \begin{align} \mathbb{E}[U_{\sigma} - U_{\pi} | \pi] &= -\frac{|\triangle|}{\binom{n}{3}} \frac{1}{n} U_{\pi} \\+ \frac{|\triangle|}{\binom{n}{3}} \frac{1}{n^2} &\left(\sum_{l} X_{\pi_l} \right) \cdot \sum_{i,j,k} f(i, j, k) \left[ X_{\pi_i}X_{\pi_j} + X_{\pi_j} X_{\pi_k} + X_{\pi_i}X_{\pi_k} \right], \end{align} \] which sort of looks like \(\eqref{eqn:linearity}\)?