Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/n \right) $ (in fact almost all of them are such).

This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)

I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$.
The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x_1, \ldots, x_n$ it outputs the correct result $f(x_1, \ldots, x_n)$ with probability $\geq 2/3$.

Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size?
The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?

The question I actually am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.

Update:

More formally I want to prove the following:


  There exists an infinite sequence of Boolean functions $f_1, f_2,
\ldots$ of $n_1, n_2, \ldots$ ($n_1 &lt; n_2 &lt; \ldots$) variables such
  that for every sequence of 2pfas $P_{f_1}, P_{f_2}, \ldots$ such that
  $P_{f_i}$ recognizes $f_i$ with 2-sided bounded error (that is for
  every word $x_1, \ldots, x_{n_i}$ accepts it with probability $\leq
\frac{1}{3}$ if $f_i(x_1, \ldots, x_{n_i}) =0$ and probability $\geq
\frac{2}{3}$ if $f_i(x_1, \ldots, x_{n_i})=1$) the number of states
  grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of
  states $\left| P_{f_i} \right| &gt; p(n_i)$.


If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?
You can still argue by counting. No matter how randomness is used, there is a way to fix the randomness in such a way that the function is computed correctly deterministically on at least $\frac{2}{3}2^n$ inputs. Thus assuming any function can be computed with error at most $\frac{1}{3}$ by some circuit in size $S$, any function can be described by a circuit of size $S$ together with a set of at most size $\frac{1}{3}2^n$ of inputs where the answer is incorrect.