Estimation of expected value of function of i.i.d. Bernoulli random variables

Abstract

We estimate the expected value of certain function $f:\{-1,1{\}}^n\to \mathbb{R}$. For example, with computer assistance, we show that if $\Delta$ is the Laplacian of the Cayley graph of $(\mathbb{Z}/15\mathbb{Z})\times (\mathbb{Z}/15\mathbb{Z})$ and $D$ is a diagonal $225\times 225$ matrix with entries chosen independently and uniformly from $\{-1,1\}$, then the expected value of the normalized trace of $(2I+D-\Delta {)}^{-1}$ is between $0.2006$ and $0.2030$.