Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions
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.