I have a function $f$ defined over a bit vector of length $n$. Equivalently, this is a function defined on the set of integers $[0,\ldots,2^n-1]$. I would like to compute the mean or variance or some other statistics of $f$ over the entire domain: $$\overline{f} = \frac{1}{2^n}\sum_{i=0}^{2^n}f(i)$$ It turns out that $f$ is quite difficult to evaluate, and so I can't possibly evaluate the entire sum. Instead, I sample the bit vector space with a random walk, treating each bit as a binary dimension. Each step of the random walk flips a bit at random.

**What is the proper way to compute statistics if $f$ is sampled using such a random walk?**

In other words, what kind of weight factor or metric should be used for the sum? My gut feeling tells me that the space will not be sampled uniformly, so simply averaging all the samples on a walk will not be correct.