Given a balanced Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, is there a sampling strategy that needs less than $O(2^n)$ samples to estimate the average length of contiguous sequences of 1's?  Balanced means over all possible x's $f(x)=0$ 50% of the time, $f(x)=1$ 50% of the time. Pointers to background papers related to this topic would be much appreciated.
Estimating the average contiguous sequence length of a balanced boolean function
cc.complexity theory;co.combinatorics;boolean functions