Question

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.

Answer 1

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.

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.

Answer 2

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).

Answer 3

Of course @Robert Israel is right here. The point of MCMC is when you don't know the distribution explicitly. If you know the distribution in advance and can readily simulate it (as you can here) then you can start off a MC in a random configuration.

However there is another issue. In order for this Markov Chain sampling to be at all useful, you have to know something about your function, basically that it has some kind of "smoothness" properties. As an instructive example, consider the function $f$ that is 0 everywhere, but $2^n$ at a single point $x$ of the hypercube (so that $\bar f=1$).

Now if you run the MC proposed up to time $N$ and average the $f$ values along the orbit, your average is $2^n/N \times$ # visits to $x$. The number of visits to $x$ is approximately a Poisson random variable with parameter $N/2^n$.

Letting $Y$ be the (random) computed value of the mean, we have then $\mathbb{E}Y=1$ (the correct value), but Var$(Y)\approx \mathbb{E}Y^2\approx 2^n/N$. This means that for this example, if you want the variance to be much less than 1 (so that your expected error is small), you need $N\gg 2^n$ (i.e. it takes longer than just averaging $f$ over the hypercube).

On the other hand, if your $f$ is (for example) $f(x)=x_1+\ldots+x_n$ (the sum of the coordinates) then the MC estimate for $\bar f$ will converge much faster.