# Change of summation using graph theory in U-statistics

In the paper Limit Theorems for a Triangular Scheme of U-Statistics with Applications to InterPoint Distances by S. Rao Jammalamadaka and Svante Janson, they used the language of graph theory to rewrite a sum, I am having a hard time figuring out the equivalence of the two summations, the definition and the equation are provided below:

Let $$X_1,X_2,...$$ be a sequence of i.i.d. random variables, and $$X, Y$$ are two independent RV(random variable[s]) with this common distribution. Let further, for each $$f_n(x,y),\ n=2,3,...$$ be a measurable symmetric function of two variables. The "triangular scheme" of U-statistics is defined by

$$\ U_n=\sum_{1\le i < j \le n} f_n(X_i,X_j)=\frac{1}{2}\sum_{i\ne j}f_n(X_i,X_j) \tag{2.1}$$

We will only consider bounded $$\{f_n\}$$

We divide $$f_n$$ into four parts by defining $$\mu_n=Ef_n(X,Y), \\ g_n(x) = Ef_n(x,Y)-\mu_n,\tag{2.2} \\h_n(x,y)=f_n(x,y)-g_n(x)-g_n(y)-\mu_n.$$

Note that $$Eg_n(X)=0=Eh_n(x,Y)=Eh_n(X,y)\tag{2.3}$$ and that $$h_n$$ is symmetric. We then write $$V_n = \sum_1^n g_n(X_i) \text{ and } W_n = \sum_{1\le i

Then when proving theorem 2.2, the language of graph theory is introduced: A weighted multigraph consists of a set $$\{ v_i\}$$ of vertices, a number $$e_{i,j}\ge 0$$ of (undirected) edges between each pair $$(v_i,v_j)$$ of vertices $$(i\ne j),$$ and an integer $$w_i \ge 0$$ for each vertex. If $$\Gamma$$ is a weighted multigraph, then $$e(\Gamma)$$ denotes $$\sum_{i the total number of edges. $$v(\Gamma)$$ denotes the number of vertices $$v_i$$ such that either $$w_i \ne 0 \text{or} e_{i,j}\ne 0 \text{for some } j.$$ $$w(\Gamma)\text{ denotes } \sum w_i$$ and $$\Gamma ! \text{denotes} \prod_{i.

Let $$G_N$$ be the set of all weighted multigraphs with $$\{ 1,..., N\}$$ as the set of vertices, and let $$G_{N,v,e,w}=\{ \Gamma \in G_N:\ v(\Gamma)=v, e(\Gamma)=e \text{ and } w(\Gamma)=w\}.$$

Finally, we define, for $$\Gamma \in G_n,$$ $$Z_n(\Gamma) = \prod_1^n g_n(X_i)^{w_i} \prod_{i Hence $$E(V_n^lW_n^m) = \sum_{i_p

There is another equation following which I don't know why the equivalence is valid:

By symmetry, we obtain $$E(V_n^lW_n^m)=\sum_v \binom{n}{v} \sum_{G_{v,v,m,l}}\frac{m!l!}{\Gamma!}EZ_n(\Gamma) \tag{2.16}$$

These sums would not be equivalent as stated, but you have misquoted them. Equation $$(2.15)$$ should end with $$E(V_n^l W_n^m) = \sum_{v=1}^n \sum_{G_{n,v,m,l}} \frac{m! l!}{\Gamma!} EZ_n(\Gamma)$$ and equation $$(2.16)$$ has $$E(V_n^l W_n^m) = \sum_v \binom nv \sum_{G_{v,v,m,l}} \frac{m! l!}{\Gamma!} EZ_n(\Gamma).$$ Note the change from $$G_{n,v,m,l}$$ to $$G_{v,v,m,l}$$. (To clarify, the sum with $$G_{n,v,m,l}$$ or $$G_{v,v,m,l}$$ in the subscript is a sum over all graphs $$\Gamma$$ in that set of graphs.)

The logic is that $$G_{n,v,m,l}$$ is the set of $$n$$-vertex graphs with some parameters in which only $$v$$ of the vertices are doing anything interesting. There are $$\binom nv$$ ways to choose which $$v$$ vertices are interesting, but (by symmetry) it doesn't really matter which $$v$$ vertices they are. So we may sum over the set of graphs in which the first $$v$$ vertices are the interesting ones, and then multiply by $$\binom nv$$.

The set of graphs in which the first $$v$$ vertices are the interesting ones is not quite $$G_{v,v,m,l}$$, but it might as well be. In $$G_{v,v,m,l}$$, there are only $$v$$ vertices, all of which are doing something interesting. We get from a graph in $$G_{n,v,m,l}$$ where the first $$v$$ vertices are interesting to a graph in $$G_{v,v,m,l}$$ just by dropping the last $$n-v$$ vertices, which doesn't change any of the parameters we care about.

Getting from the first formulation in $$(2.15)$$ to the second is where the graph theory comes in. The product $$\prod_{p=1}^m h_n(X_{i_p},X_{j_p})\prod_{q=1}^{l}g_n(X_{k_q})$$ is a product of $$h_n$$ applied to some $$m$$ pairs and $$g_n$$ applied to some $$l$$ singletons; the pairs and singletons can be repeated. Any such product can be represented as $$Z_n(\Gamma)$$ where $$\Gamma$$ is the following weighted multigraph:

• There are $$e_{ij}$$ edges between vertices $$v_i, v_j$$ when the factor $$h_n(X_i, X_j)$$ shows up $$e_{ij}$$ times in the product;
• The weight of vertices $$v_k$$ is $$w_k$$ when the factor $$g_n(X_k)$$ shows up $$w_k$$ times in the product.

This explains everything except for the factor $$\frac{m!l!}{\Gamma!}$$. That factor corresponds to the number of different terms in the first part of $$(2.15)$$ that correspond to the same $$EZ_n(\Gamma)$$ in the second part. Splitting up $$\Gamma!$$ as $$\prod_{i, we see that $$\frac{m!l!}{\Gamma!} = \frac{m!}{\prod_{i These two factors are multinomial coefficients. The factor $$\frac{m!}{\prod_{i equals the number of different orders in which the $$m$$ edges of $$\Gamma$$ can be considered, if we do not care about rearrangements of different copies of the same edge. The factor $$\frac{l!}{\prod_k w_k!}$$ equals the number of different orders in which the vertices of $$\Gamma$$ can be considered, if we use a vertex $$v_k$$ a total of $$w_k$$ times.

• I have corrected the formula, thanks Apr 15, 2022 at 4:10
• In addition, can you explain why the second equation of (2.15) is valid? Apr 15, 2022 at 4:20
• I have added an explanation. Apr 15, 2022 at 18:27