# Probability bounds for Hutchinson’s estimator using Hanson-Wright inequality

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.