TITLE: Averaging over random walk on binary lattice
QUESTION [4 upvotes]: 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.

REPLY [1 votes]: I'm not sure, but I think what you meant to ask was a practical question: how many random walk samples do I need in order to get a certain precision in estimating $\mathbb{E}(f)$?
This question has been studied for many Markov chains, but ultimately, to get an answer you must know something about $f$. Here is a reference, which gives you tail bounds in terms of $\max(|f|)$, $Var(f)$ and the spectral gap of the Markov chain. There are probably more accessible papers, specifically for the case of the hypercube (but I don't know any specific one).
{"set_name": "stack_exchange", "score": 4, "question_id": 71944}