I am trying to work out a probability bounds for the Hutchinson’s estimator for the trace $text{tr}(A)$ of a $ntimes n$ matrix $A$ (not necessarily symmetric):

$$

text{tr}^H(A) = frac{1}{N}sum_{i=1}^Nmathbf{x}_i’Amathbf{x}_i,

$$

where $mathbf{x}_i$ is a zero-mean, unit variance random vector with independent random components. $mathbf{x}_i$‘s are indpendent. Here I just assume that $mathbf{x}_i$ consists of $n$ independent standard normal components. Essentially, I want to find $N = N(epsilon, delta)$ so that with probability at most $delta$, the estimator has an error of $epsilon$.

I am thinking about using Hanson-Wright inequality which says that for a random vector $mathbf{x}$ with i.i.d. standard normal component, we have

$$

mathbb{P}(|mathbf{x}’Amathbf{x} – text{tr}(A)| geq t) leq 2expleft(-cminleft(frac{t}{||A||}, frac{t^2}{||A||^2_{HS}}right)right).

$$

However, I can’t figure out how to incorporate Hanson-Wright to $text{tr}^H(A)$. Can anyone give some hint?

P.S. I am not even sure if Hanson-Wright can be used, but given it’s similarity to the Hutchinsons estimator, I feel like it should be the way to go.