# Expected value of the evaluation of Boolean circuits of depth $2n$

I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.

Let $C_{n}$ be the Boolean circuit satisfying the following conditions:

1. the depth of $C$ is $2n$,
2. the gates of odd level are binary $\operatorname{AND}$ gates,
3. the gates of even level are binary $\operatorname{OR}$ gates.

The circuit $C_{n}$ computes a function $f_n$ which associates to each binary word of length $2^{2n}$ a Boolean value. For instance, for $n = 1$, $f_1(1010) = 0$ and $f_1(0011) = 1$, as shown in the
figure below:

For $0 \leqslant k \leqslant 2^{2n}$, let $L_k = \{ u \in \{0, 1\}^{2^{2n}} \mid |u|_1 = k \}$, a language of size $$\binom{2^{2n}}{k} = \frac{2^{2n}!}{k! (2^{2n} - k)!}$$ Here is an instance of the problem I have in mind: if 40\% of the bits of the input $x$ are equal to $1$, what is the expected value of $f_n(x)$? Here are a few more precise instances of this problem.

1. Compute the average value of $f_n(x)$ on $L_k$, that is, $$\frac{k! (2^{2n} - k)!}{2^{2n}!} \sum_{x \in L_k} f_n(x),$$

2. In particular, let $c \in [0,1]$ be a real number and let $c_n = \lfloor c2^{2n}\rfloor$. Can one estimate the average value of $f_n(x)$ on $L_{c_n}$, that is, $$\frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)\ ?$$

3. Does the limit of the previous expression exists when $n$ tends to $\infty$? $$\lim_{n \to \infty} \frac{1}{\binom{2^{2n}}{c_n}} \sum_{x \in L_{c_n}} f_n(x) = \lim_{n \to \infty} \frac{c_n! (2^{2n} - c_n)!}{2^{2n}!} \sum_{x \in L_{c_n}} f_n(x)$$

• Can you be more explicit on the definition of $C_n$ ? Do you mean that the circuits is actually the full binary alternating formula of depth $2n$ ? (each gates is fan-out $1$ and fan-in $2$) or is it any circuits satisfying your specifications (with arity $2$ gates?) ?
– C.P.
Jul 17, 2018 at 15:54
• Thanks for the comment.Each gate has fan-in $2$, so $C_n$ is indeed the full binary alternating formula of depth $2n$. I edited the question accordingly. Jul 17, 2018 at 16:23
• If I haven't made any obvious mistakes, then for uniformly distributed inputs over $\{0,1\}^{2^{2n}}$, the probability of evaluating to zero satisfies $p(n)=p^2(n-1)*(2-p(n-1))^2$, which seems to converge to $1$ very quickly. This would answer your third question in the $c_n\le \frac{1}{2}2^{2n}$ case. Jul 17, 2018 at 18:45
• @Ariel For any $c$ I feel like the recursion still holds when $n$ is large, due to the concentration of weight in each part. Jul 19, 2018 at 19:29