How can I estimate the following value where $A,B$ are $d\times d$ matrices and expectation is taken over all random permutations of the product?
$$E_\text{shuffle}[\operatorname{Tr}\underbrace{AA\cdots A}_s \underbrace{BB\cdots B}_s]$$
In my application $A$ is a positive definite diagonal matrix, $B$ is positive definite symmetric rank-1, $\|A+B\|<1$. I need to estimate this in $O(d)$ time for large $d$ and $s\approx d$, any tips?
Empirically, this distribution appears to concentrate around the mean:
The following appears to hold empirically, is it true?
$$\operatorname{Tr}(ABABAB\ldots AB) \le E_\text{shuffle}[\operatorname{Tr}\underbrace{AA\cdots A}_s \underbrace{BB\cdots B}_s] \le \operatorname{Tr}AA\cdots AA BB\cdots BB$$
Any pointers to the relevant theory appreciated!
Motivation: to estimate $\operatorname{Tr}[(A+B)^{2s}]$ which gives error after $2s$ steps of SGD to solve linear problem with eigenvalues $h$ by following Eq.5 of Bordelon. $A,B$ is obtained from $h$ like this.
