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.



Averaging over random walk on binary lattice
If you make a small adjustment to your random walk, it becomes easier to analyze.


Consider the random walk where instead of flipping a bit at random, you replace a random bit with either 0 or 1 randomly. This is equivalent to the lazy random walk -- flip a random bit with probability 1/2, and stay the same otherwise. This is "nicer" than the non-lazy walk, because if we view it as a Markov chain, the non-lazy walk is periodic (i.e. if you start at $\vec 0$, after an even number of steps you always have an even number of 1's), while the lazy walk is not.


In the (lazy) random walk, after $O(n \log n)$ steps, your position in the random walk is as close as you'd like to being uniformly distributed (exactly how close depending on constants). A full proof of this (via Markov chain coupling) is shown in section 5.3.3 of *Markov Chains and Mixing Times* by Levin, Peres, and Wilmer, available [here](http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf).


So, asymptotically, the (lazy) random walk is in fact uniformly distributed.


Specifically, if you drop all but every $kn\log n$ steps of the chain (for some relatively small $k$, depending on how close to uniformly distributed you need), you can definitely average the samples without weighting. I think that you should be able to average without weighting without dropping any values as well, though I cannot see how to show that off the top of my head.


