Nonbacktracking covariance high moments and an independent coarse norm bound

Apply F1 to the original nested rectangular array and, as necessary, its transpose. Orient the centered truncated matrix with $p$ rows and $n$ columns, $p\le n$, and divide by $\sqrt{n}$. In this proof the original sequence index is $h$, $n=N_h=\max (h,p_h)$, $p=\min (h,p_h)$, and $y_n=p\mathrm{/}n\to y\in (0,1]$. These dimensions are comparable to $h$; all probability series below are summed over $h$. Enlarge the slow truncation threshold by a fixed factor to bound the centered entries by $L_n={\delta }_n\sqrt{n}$ with ${\delta }_n\ge 1\mathrm{/}\log (n+2)$, ${\delta }_n\to 0$. F1 gives independent centered entries, variance at most one, and $E\mathrm{\mid }x{\mathrm{\mid }}^q\le C{L}_n^{q-3}$ for $q\ge 3$. Define $Y=(x_{ij}\mathrm{/}\sqrt{n})$ and the restricted matrices $T_{\mathrm{\ell }}$ as in the statement. The same arguments hold if the orientation changes infinitely often.

Fix $\mathrm{\ell }\ge 1$. Set $N=4m\mathrm{\ell }$, with integer $m$ chosen so that $m\mathrm{/}\log n\to \mathrm{\infty }$ and ${\delta }_n(m\mathrm{/}\log n{)}^2\to 0$; for example $m=\lceil \log n{\delta }_n^{-1\mathrm{/}8}\rceil$. Since ${\delta }_n\ge 1\mathrm{/}\log n$, $N$ is polylogarithmic. Reversing each admissible path exchanges its endpoints and preserves its real weight, so $T_{\mathrm{\ell }}$ is real symmetric. Thus its even-power trace bounds $\mathrm{\parallel }{T}_{\mathrm{\ell }}{\mathrm{\parallel }}^{2m}$. Expand $E\mathrm{tr}{T}_{\mathrm{\ell }}^{2m}$ into closed alternating walks of length $N$, split into $2m$ consecutive nonbacktracking blocks of length $2\mathrm{\ell }$. Bound absolute expectations termwise. Any edge appearing exactly once vanishes by centering and independence.

Canonicalize row and column labels separately by order of first appearance. Innovations lead to a previously unvisited vertex and form a spanning tree of the visited vertices. Let $k$ be their number, so $k+1$ vertices are visited. Classify the second occurrence of each innovation edge as T3; all other noninnovation occurrences are T4. There are exactly $k$ T3 occurrences and $d=N-2k$ T4 occurrences. A T4 class is a distinct unoriented edge supporting at least one T4 occurrence; let $t$ be their number. Then $0\le t\le d$, and $t=0$ implies $d=0$. Every innovation edge appears at least twice.

Moment bound. An innovation edge of multiplicity two contributes at most one. An innovation edge of multiplicity $q\ge 3$ contributes at most $C{L}_n^{q-3}$. A noninnovation edge of multiplicity $q\ge 2$ contributes at most $C{L}_n^{q-1}$, a deliberately weaker bound valid for $L_n\ge 1$. Consequently the product is bounded by $C^t{L}_n^{d-t}$. This follows by summing exponents: an innovation edge contributes $q-2-1_{q\ge 3}$, while a noninnovation edge contributes $q-1$; the resulting total is $N-2k-t$.

Coding bound, including a replacement for Lemmas 5.5–5.6. At each time keep the forest $F$ of innovation edges seen exactly once. At a T3 step the endpoint is selected among the neighbors of the current vertex in $F$. Call the step regular if there are at least two such neighbors; otherwise its endpoint is forced. Let $Q$ be the number of nonempty edge components of $F$ not containing the current vertex. An innovation leaves $Q$ unchanged. A regular T3 step increases $Q$ by one (deleting its edge leaves a nonempty component on the departure side); an irregular T3 leaves $Q$ unchanged. A T4 step leaves $F$ unchanged and changes $Q$ by at most one. Since $F$ starts and ends empty, there are at most $d$ regular T3 steps.

At any time the degree of the current vertex in $F$ is at most $2t+1$. To prove this, delete that vertex from the full innovation tree. Each incident open edge determines one branch. Except for the possible branch containing the initial vertex, the prefix walk crosses the cut of such a branch an even number of times. Its innovation-tree edge has been crossed exactly once, so some T4 class must cross this cut with odd multiplicity. A fixed T4 edge can join at most two branches at the deleted vertex. There are $t$ classes, proving the bound. This parity argument allows classes whose first T4 occurrence is in the future by harmless overcounting.

Given innovation and T3 positions, choose the $t$ T4 edge classes in at most $(k+1{)}^{2t}$ ways and assign all T4 positions to classes in at most $t^d$ ways. Innovation endpoints are forced by canonical order. At any T3 position there are at most $2t+1$ choices, and at most $d$ positions can be regular. A decision tree of depth at most $d$ with branching at most $2t+1$ has at most $(2t+1{)}^d$ leaves (pad shorter branches with forced dummy choices); no separate selection of regular positions is required. T4 endpoints are forced by current vertex and chosen class, or the code is invalid. Thus the remaining coding factor is at most $(k+1{)}^{2t}{t}^d(2t+1{)}^d\le (k+1{)}^{2t}{3}^d(t+1{)}^{2d}$. Interpret $0^0=1$.

In block $b$, let $a_b$ count adjacent innovation/noninnovation pairs. Such a pair must have a NEW noninnovation edge: its departure vertex was just introduced, and immediate reversal is prohibited inside a block. It is therefore the first T4 occurrence of its class. Consequently $\sum a_b\le t$. Innovation runs have at most $a_b+1$ components; their alternating row/column innovations differ in number by at most one each. If $r,s$ count row and column innovations, then $k=r+s$ and $\mathrm{\mid }r-s\mathrm{\mid }\le t+2m$. Hence $r\ge (k-t-2m)\mathrm{/}2$.

For given $a_b$, innovation positions in block $b$ have at most $\left(\genfrac{}{}{0px}{}{2\mathrm{\ell }+1}{2a_b+1}\right)$ patterns: a binary string with $a_b$ transitions $1\to 0$ has this count, by specifying its alternating run endpoints, including a possible terminal run. Their product is at most $(2\mathrm{\ell }+1{)}^{2t+2m}$. There are at most $(\mathrm{\ell }+1{)}^{2m}$ choices of the $a_b$. Once innovation positions are fixed, T3 positions have at most $\left(\genfrac{}{}{0px}{}{N-k}{k}\right)$ choices. Labelings contribute at most $p^{r+1}{n}^s=n^{k+1}{y}_n^{r+1}\le n^{k+1}{y}_n^{(k-t-2m)\mathrm{/}2}$, for $0<y_n\le 1$.

Combining all factors, with $A=(2\mathrm{\ell }+1)(\mathrm{\ell }+1)$, gives $E\mathrm{tr}{T}_{\mathrm{\ell }}^{2m}\le n{A}^{2m}{y}_n^{-m}{\sum }_{1\le k\le N\mathrm{/}2}\left(\genfrac{}{}{0px}{}{N-k}{k}\right)y_n^{k\mathrm{/}2}{\delta }_n^{N-2k}{3}^{N-2k}{\sum }_{t=0}^{N-2k}{q}_{n,k}^t(t+1{)}^{2(N-2k)},$ where $q_{n,k}=C(2\mathrm{\ell }+1{)}^2(k+1{)}^2\mathrm{/}(\sqrt{n{y}_n}{\delta }_n)$. This derivation uses absolute values and requires no symmetry of the real entry law.

Uniformly in $k$, $q_{n,k}=n^{-1\mathrm{/}2+o(1)}$. Set $a=-\log q_{n,k}$, so eventually $(\log n)\mathrm{/}3\le a\le \log n$. For $d\ge 1$, ${\sum }_{t\ge 0}{e}^{-at}(t+1{)}^{2d}\le 2e^{a\mathrm{/}2}\max \{1,(4d\mathrm{/}(ae){)}^{2d}\}\le 2n[C_1\max \{1,N\mathrm{/}\log n{\}}^2{]}^d\mathrm{.}$ Indeed split the exponential into two halves, sum one geometric factor, and maximize $u^{2d}{e}^{-au\mathrm{/}2}$ for $u=t+1\ge 1$. For $d=0$ the finite inner sum is exactly one. Thus, after enlarging a fixed constant, let ${\epsilon }_n=C_2{\delta }_n\max \{1,N\mathrm{/}\log n{\}}^2\to 0$; the trace is at most $2n^2{A}^{2m}{y}_n^{-m}{\sum }_k\left(\genfrac{}{}{0px}{}{N-k}{k}\right)y_n^{k\mathrm{/}2}{\epsilon }_n^{N-2k}\le 2n^2{A}^{2m}{y}_n^{-m}(y_n^{1\mathrm{/}4}+{\epsilon }_n{)}^N\mathrm{.}$

For the final inequality, $\left(\genfrac{}{}{0px}{}{N-k}{k}\right)\le \left(\genfrac{}{}{0px}{}{N}{2k}\right)$: map a $k$-subset of $\{1,\dots ,N-k\}$ to the $2k$-subset formed by the adjacent pairs $(b_i+i-1,b_i+i)$; these are disjoint and recover the original subset. The sum is consequently bounded by the binomial expansion with nonnegative coefficients. Since $N=4m\mathrm{\ell }$, the last display equals $2n^2[A{y}_n^{(\mathrm{\ell }-1)\mathrm{/}2}{]}^{2m}(1+o(1){)}^N$.

For $\eta >A{y}^{(\mathrm{\ell }-1)\mathrm{/}2}$, Markov's inequality gives $P(\mathrm{\parallel }{T}_{\mathrm{\ell }}\mathrm{\parallel }\ge \eta )\le 2n^2{e}^{-cm}$ eventually, which is summable since $m\mathrm{/}\log n\to \mathrm{\infty }$. Borel–Cantelli and a countable sequence of $\eta$ prove the stated fixed-length norm bound. This completes all graph estimates locally.

In particular, $\mathrm{lim\hspace{0.17em}sup}\mathrm{\parallel }{T}_1\mathrm{\parallel }\le 6$. Since $Y{Y}^{\mathsf{T}}=T_1+D$ with $D=\mathrm{diag}(Y{Y}^{\mathsf{T}})$ and $\mathrm{\parallel }D-I\mathrm{\parallel }\to 0$ by F1, $\mathrm{lim\hspace{0.17em}sup}\mathrm{\parallel }Y{\mathrm{\parallel }}^2\le 7$. On the event of eventual truncation equality, the original oriented normalized matrix differs from $Y$ by the constant matrix with every entry ${\mu }_h\mathrm{/}\sqrt{N_h}$. Its norm is $\sqrt{p}\mathrm{\mid }{\mu }_h\mathrm{\mid }\to 0$ by F1, since a constant $p\times n$ matrix of entry $a$ maps a vector to $a$ times its coordinate sum in every row and has norm $\mathrm{\mid }a\mathrm{\mid }\sqrt{pn}$. Thus the original normalized matrices have an eventual finite norm bound. Changing the normalization from $\sqrt{N_h}$ to $\sqrt{h}$ multiplies this norm by the bounded factor $\sqrt{N_h\mathrm{/}h}$. This proves the independent coarse bound.