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<j\le n} h_n(X_i,X_j),\tag{2.4}$$

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<j} e_{i,j},$ 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<j}e_{ij}! \prod_i w_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<j\le n}h_n(X_i,X_j)^{e_{ij}}\tag{2.14}.$$ Hence $$E(V_n^lW_n^m) = \sum_{i_p<j_p\le n \\ k_q \le n}E(\prod_{p=1}^m h_n(X_{i_p},X_{j_p})\prod_{q=1}^{l}g_n(X_{k_q}))\\ = \sum_{v=1}^n\sum_{G_{n,v,m,l}}\frac{m!l!}{\Gamma!}EZ_n(\Gamma) \tag{2.15}.$$

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}$$


1 Answer 1


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<j} e_{ij}! \prod_k w_k!$, we see that $$\frac{m!l!}{\Gamma!} = \frac{m!}{\prod_{i<j} e_{ij}!} \cdot \frac{l!}{\prod_k w_k!}.$$ These two factors are multinomial coefficients. The factor $\frac{m!}{\prod_{i<j} e_{ij}!}$ 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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .