Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This has essentially been answered below, but just to provide a reference: the ergodic theorem for Markov chains shows that the empirical averages of the original chain Victor considers converge to the average of $f$ with respect to the stationary measure. See for example Theorem 4.1 in Brémaud's Markov Chains. The fact that Victor's chain is periodic does not matter for this result. That it is irreducible and has a finite state space is enough. –  Paul Tupper Aug 3 '11 at 17:30
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
The average over the first $N$ steps of the chain is the average of the averages of $k n \log n$ interleaved subsequences; if each of those is close to uniform, so is their average. But instead of flipping $k n \log n$ random bits, why not just flip (or not flip) each of the $n$ bits with probability $1/2$, to get a random point that is explicitly uniformly distributed? –  Robert Israel Aug 3 '11 at 4:41
1  
I can't flip more than one bit at a time or I lose a great deal of efficiency when computing $f$. Otherwise, I would really just sample the space randomly without this Markov or random walk nonsense. –  Victor Liu Aug 3 '11 at 6:28
    
Victor, you should really add this bit of information in the question. –  Ori Gurel-Gurevich Aug 4 '11 at 0:58
add comment

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.

share|improve this answer
    
As Victor commented elsewhere, there is another reason: the cost of computing $f$ after flipping a single bit might be significantly less than for a new vector. –  Ori Gurel-Gurevich Aug 4 '11 at 1:42
    
Still: if you need $\gg 2^n$ steps with a random algorithm, but you can efficiently compute $f$ if you flip a single bit, you can enumerate the vertices of the hypercube reasonably efficiently flipping single bits at each stage. –  Anthony Quas Aug 4 '11 at 5:10
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.