Suppose $z_i$ are IID zero-centered $d$-dimensional Gaussian random variables with unit-trace covariance $\Sigma$ and $g(z_i)$ is the sum of its components.

Consider the following random walk:

$$x_s=\frac{1}{s}\left(g(z_1)z_1+\ldots+g(z_s)z_s\right)$$

Let $f_s=\|x_s\|^2$. For large $d$, expected value of $E[1/f_s]$ is bounded above for $s\to\infty$ and smoothly interpolates between two extremes for intermediate $s$. Where is the halfway point located? Simple relation seems to exist between this point and measure of uniformity of $\Sigma$ eigenvalues.

I'm observing the following: $$s>\frac{1}{\operatorname{Tr}\Sigma^2} \text{ implies } 2E\left[\frac{1}{f_s}\right]>\frac{1}{Ef_1}+\frac{1}{Ef_\infty}$$

- Why does $\operatorname{Tr}(\Sigma^2)$ matter here?
- How do I prove the inequality above?

(PS, the following relationship is also observed when $d>100$:

$$\begin{equation} E\left[\frac{1}{f_s}\right]> \left( \frac{1}{s} Ef_1 + \frac{s-1}{s}Ef_\infty\right)^{-1}\label{y3}\tag{y3} \end{equation} $$

**Motivation**

this equation, if it holds, sets an easy to compute limit for the number of SGD updates that can be performed in parallel when observations are Gaussian (this random walk is in denominator of Eq 1.5 here), saturation corresponds to step size scaling unfavorably. Intriguingly, similar harmonic mean relationship holds for other choices of $f$ which correspond to different ways of setting step size. For instance it holds when $f_s$ is Frobenius norm of Wishart matrix with $s$ degrees of freedom, or spectral norm of Wishart matrix with $s$ degrees of freedom (details).

The quantity which upper bounds the value in the graph above, $1/Ef_\infty$ seems to be equal to $R$, the "effective rank" of the Gaussian, described in Lemma 5 of Bartlett paper. That paper shows that high value of $R$ makes the problem easy for statistical estimation. Proving the formula above would help prove that high $R$ also makes the estimation procedure easy to parallelize.

link to Eq $\eqref{y3}$