<p>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?  </p>

<p>Balanced means over all possible x's $f(x)=0$ 50% of the time, $f(x)=1$ 50% of the time. </p>

<p>Pointers to background papers related to this topic would be much appreciated.</p>

CC BY-SA 3.0
2013-06-26T22:53:23.917Z
How do you define the average length?
Sasho Nikolov
CC BY-SA 3.0
2013-06-26T23:22:29.403Z
Because the function is balanced, we know there are 2^(n-1) x_i's such that f(x_i)=1. So the average contiguous sequence length is  equal to the number of 1's divided number of unique contiguous sequences, ie Average = 2^(n-1)/(# of unique contiguous sequences of 1's)
Steve C
CC BY-SA 3.0
2013-06-27T07:07:07.037Z
I think the asker wants to know if the denominator can be approximated with some probability via sampling.
Shir
<cc.complexity-theory><co.combinatorics><boolean-functions>
Estimating the average contiguous sequence length of a balanced boolean function
Steve C
# Estimating the average contiguous sequence length of a balanced boolean function

(Asked by: username_0 on 2013-06-26)

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.

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions

> **Comments:**
> **username_1**: How do you define the average length?  
> **username_0**: Because the function is balanced, we know there are 2^(n-1) x_i's such that f(x_i)=1. So the average contiguous sequence length is  equal to the number of 1's divided number of unique contiguous sequences, ie Average = 2^(n-1)/(# of unique contiguous sequences of 1's)  
> **username_2**: I think the asker wants to know if the denominator can be approximated with some probability via sampling.  

---

## 0 answers

