We proceed by induction on \(k\).

Our base case is \(k=1\), then:

which matches the formula since the summation over zero indices just gives the term \(Y_{ij}\).

Our inductive step is to assume that the formula holds for some \(k \ge 1\), i.e.,

We must show that it holds for \(k + 1\). Note that:

Thus, the formula holds for \(k + 1\).

By induction, the result holds for all \(k \ge 1\).

We can use the result from Lemma 5.1.1 to compute the trace of \(Y^k\):

By linearity of expectation.

We see from definition \(\ref{def:graph_walk_multi_index}\) that the path is defined as:

if we use each each edge \(w \in w_{\mathbf{i}}\), due to symmetry, we can write the product:

as required.

Using lemma 5.1.5, we already have that \(Y_{\mathbf{i}} = \prod _{w \in w_{\mathbf{i}}} Y_{w}\). We consider the following cases for each \((i, j)\):

\((i, j) \notin w_{\mathbf{i}}\): In this case, the entry \(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )} = 1\), making no contribution to the product.

\((i, j) \in w_{\mathbf{i}}\): In this case, the entry \(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}\) is equal to the number of times the unordered edge \(\{ i, j\} \) appears in the path \(w_{\mathbf{i}}\).

These two cover all possibilities, so putting them together we obtain

Indeed, if \((i,j)\notin w_{\mathbf i}\) then \(w_{\mathbf i}(\{ i,j\} )=0\) and the corresponding factor contributes \(Y_{ij}^{0}=1\), and if \((i,j)\in w_{\mathbf i}\) (hence also \((j,i)\) if \(j{\lt}i\)), the exponent \(w_{\mathbf i}(\{ i,j\} )\) counts exactly how many times the unordered edge \(\{ i,j\} \) appears in the walk, so the factor is \(Y_{ij}^{\, w_{\mathbf i}(\{ i,j\} )}\).

Because every unordered pair \(\{ i,j\} \) with \(1\le i\le j\le n\) is covered by one of these two cases and the product lists each edge exactly once.

Because each \(Y_{ij}\) is independent, we can write:

using lemma 5.1.6. Consider the following cases for each \((i, j)\) (we assume each \((i, j) \in w_{\mathbf{i}}\) since if they aren’t, then \(w_{\mathbf{i}}(i, j) = 0\) and this contributes nothing to the product):

\(\mathbf{i = j}\): in this case, we have \(Y_{ij} = Y_{ii}\), and therefore the edge \((i, i) \in E_{\mathbf{i}}^{s}\). Since each \(Y_{ii}\) is identically distributed for all \(i\), we have:

so the factor in the product above becomes \(\mathbb {E}(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}) = \mathbb {E}(Y_{11}^{w_{\mathbf{i}}(i, i)})\).

\(\mathbf{i {\lt} j}\): in this case, we have \(Y_{ij} \in E_{\mathbf{i}}^{c}\). Since each non diagonal entry \(Y_{ij}\) is identically distributed for all \(i \neq j\) (and by symmetry \(Y_{ij} = Y_{ji}\)), we have:

so the factor in the product above becomes \(\mathbb {E}(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}) = \mathbb {E}(Y_{12}^{w_{\mathbf{i}}(i, j)})\).

Plugging both of these cases into the earlier product over \(E_{\mathbf{i}}^{c}\) and \(E_{\mathbf{i}}^{s}\), we have:

as required.

Let \(\varphi \) be the permutation that maps \(w_\mathbf {i}\) to \(w_{\mathbf{j}}\) in the equivalence relation. Given \(Y_\mathbf {i} = Y_{i_1 i_2}Y_{i_2 i_3} \cdots Y_{i_{k-1} i_k}Y_{i_k i_1}\), we have

Observe that \(\{ i_{\lambda _l},i_{\lambda _{l+1}} \} \) is a singleton and only if \(\{ \varphi (i_{\lambda _l}),\varphi (i_{\lambda _{l+1}}) \} \) is a singleton. The fact that \(\{ i_{\lambda _l},i_{\lambda _{l+1}} \} = \{ i_{\lambda _\mu },i_{\lambda _{\mu +1}} \} \) if and only if \(\{ \varphi (i_{\lambda _l}),\varphi (i_{\lambda _{l+1}}) \} = \{ \varphi (i_{\lambda _\mu }),\varphi (i_{\lambda _{\mu +1}}) \} \) completes the proof.

This follows from ‘partitioning’ the summation appearing in Lemma 5.1.4 using the equivalence relation defined in Definition ??.

This follows from re-indexing the sum of Lemma 5.1.10 by using Lemma 5.1.9 and Lemma 4.0.21.

Combining with the renormalization factor \(n^{-1}\) of Proposition ?? gives

Substituting the term \(\mathbb {E}\operatorname{Tr}(\mathbf{Y}_\mathbf {i}^k)\) with the expression in Equation 5.1.12 gives

Let \((G,w) \in \mathcal{G}_k\) and let \(\mathbf{j}\) be the \(k\)-index generated by \((G,w)\). Suppose there exists an edge \(e \in E_\mathbf {j}\) such that \(w_\mathbf {j}(e) = 1\). This means, in Lemma 5.1.7, a singleton term \(\mathbb {E}(Y_{ij}^{w_\mathbf {j}(e)}) = \mathbb {E}(Y_{ij})\) appears. The rest of the proof follows from the assumption of Proposition ?? that \(\mathbb {E}(Y_{ij}) = 0\) for every \(i\) and \(j\).

This follows from applying the result of Lemma 5.1.14 to Lemma 5.1.13.

Use Nat.ascFactorial_eq_div. Or prove directly.

The only part that depends on \(n\) is the big fraction. Since we only care about \(w \ge 2\), \(|G_w| \le k/2 + 1\). Use the fact that the product \(n(n-1)\cdots (n-|G|+1)\) is asymptotically equal to \(n^{|G|}\) to conclude that the fraction is bounded and doesn’t explode.

Since \(|G_w|\le \# E+1 \le k/2+1\) and \(|G_w|\) is an integer, it follows that \(|G_w|\le (k-1)/2+1 = k/2 + 1/2\). Hence, in this case, all the terms in the (finite \(n\)-independent) sum in Equation 4.8 are \(O(n^{-1/2})\)

If \(|G_w| {\lt} k/2 + 1\), then there is at least one more \(n\) in the denominator than the numerator.

some lower bound stuff + other stuff?

Proof: use the fact that \(|G_w|=k/2+1\) and \(n(n-1)\cdots (n-k/2+1) \sim n^{k/2+1}\). Limit as n approaches infinity of \(O(n^{-1/2})\) is 0.

Follows directly.

Follows directly.

Follows directly.

Follows directly.

Proof slightly outdated.

Let \((G,w)\in \mathcal{G}^{k/2+1}_k\). Since \(w\) traverses each edge exactly twice, the number of edges in \(G\) is \(k/2\). Since the number of vertices is \(k/2+1\), Exercise (Prop) 4.3.1 shows that \(G\) is a tree. In particular there are no self-edges (as we saw already in Proposition 4.4).

1st equality: definition right after equation 4.4 in notes 2nd equality: proposition 4.4 (w < 3) and previous lemma (w = 1 –> 0) 3nd equality: definition (from main proposition) 4th equality: number of edges is k/2.

Follows directly from 4.7.5 and 4.8.

Expanding the variance by definition, we get:

use the linearity of expectation to factor out \(\frac{1}{n^{k+2}}\) from both expectations:

using 5.1.4, we can expand and square:

This follows a similar reasoning as in Lemma 5.1.9.

This follows from ‘partitioning’ the summation appearing in Lemma 5.2.1 using the equivalence relation defined in Definition 4.0.51.

This follows from re-indexing the sum of Lemma 5.2.4 using Lemma 4.0.52.

This follows from Lemma 5.1.7 and the independency of random variables.

Let \((G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j})\) be the ordered triple generated by the two \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\). By construction, there are finite number of edges \(e \in E_{\mathbf{i} \# \mathbf{j}}\). Moreover, there are finite number of integer values the counting function \(w_{\mathbf{i} \# \mathbf{j}}(\cdot )\) can take over \(E_{\mathbf{i} \# \mathbf{j}}\). This implies we can choose the maximum element of the set

and therefore \(\lambda \in \mathbb {N}\) so that \(\mathbb {E}(Y_{11}^\lambda ) = \max \mathscr {E}\). Using the fact that \(\mathbb {E}(Z) \leq \mathbb {E}(|Z|)\) for any random variable \(Z\),

This follows an identical reasoning as in Lemma 5.2.8.

By Lemma 5.2.7, we have

By Lemma 5.2.8, there exists \(\lambda _1 \in \mathbb {N}\) so that \(\mathbb {E} (Y_{11}^{w_{\mathbf{i} \# \mathbf{j} (e)}}) \leq r_n\) for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\). On the other hand, by Lemma 5.2.9, there exists \(\lambda _2 \in \mathbb {N}\) so that \(\mathbb {E} (Y_{12}^{w_{\mathbf{i} \# \mathbf{j} (e)}}) \leq r_m\) for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\). Then

Setting \(M_1 := 2k \cdot \max \{ r_{\lambda _1},r_{\lambda _2}\} \) satisfies the problem.

This follows a similar reasoning as in Lemma 5.2.8 with the counting function \(w_\mathbf {i}(\cdot )\).

This follows a similar reasoning as in Lemma 5.2.8 with the counting function \(w_\mathbf {i}(\cdot )\).

This follows an identical reasoning as in Lemma 5.2.8.

Combining the result of Lemma 5.2.10 and Lemma 5.2.13 gives

where \(M_2^{(\mathbf{i})}\) and \(M_2^{(\mathbf{j})}\) are the upper bounds acquired by Lemma 5.2.13 with repsect to \(\mathbf{i}\) and \(\mathbf{j}\), repsectively. Setting \(M_{2k} := \max \{ M_1, M_2^{(\mathbf{i})} \cdot M_2^{(\mathbf{j})} \} \) satisfies the problem.

By construction, every edge in the joined graph \(G_{{i}\# {j}}\) is traversed at least once by the union of the two paths \(w_{i}\) and \(w_{j}\). Suppose that \(e\) is an edge that is traversed only once. This means that \(w_{{i}\# {j}}(e) = 1\), and so it follows that the two values \(w_{i}(e),w_{j}(e)\) are \(\{ 0,1\} \). Hence, the above expansion and the fact that \(\mathbb {E}(Y_{11})=\mathbb {E}(Y_{12})=0\) show that \(\pi (G_{{i}\# {j}},w_{i},w_{j}) = 0\) in this case.

Follows directly.

Appealing again to 4.0.5, it follows that \(|G|\le k+1\). Hence, \(n(n-1)\cdots (n-|G|+1) \le n^{|G|} \le n^{k+1}\)

The (potentially enormous) number \(B_k=2M_{2k}\cdot \# \mathcal{G}_{k,k}\) is independent of \(n\), and so we have already proved that the variance is \(=O_k(1/n)\).