I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the minimal automaton computing this function.
Automaton $A$ computes $f$ if it recognizes the language $L_f=\left\{ x \in \{ 0, 1 \} ^n | f(x)=1 \right\}$.
The result that I want to get is that there exist hard Boolean functions - requiring superpolynomial number of states for any probabilistic (with arbitrary rational probabilities) two-way automaton that computes the function.
This result can be proven for deterministic automata:
Theorem. There exists an infinite sequence of Boolean functions $f_1, f_2, \ldots$ of $n_1, n_2, \ldots$ ($n_1 < n_2 < \ldots$) variables such that for every sequence of 2DFAs $A_{f_1}, A_{f_2}, \ldots$ such that $A_{f_i}$ computes $f_i$ the number of states grows superpolynomially - for every polynomial $p$ there exists $i$ such that the number of states $\left| P_{f_i} \right| > p(n_i)$.
Sketch of proof. We will use counting argument.
The alphabet including the endmarkers is $\Sigma = \left\{ 0, 1, \vdash, \dashv \right\}$.
The number of determinstic two-way automata with $k$ states is no more than $(3 \cdot k)^{ \left| \Sigma \right| \cdot k } = 2^{4 \cdot k \cdot \log_{2}{3k} }$ - for every state and every symbol (hence the $\left| \Sigma \right| \cdot k$ part) there is a transition to some state and the transition itself can be one of 3 types - moving the head left, right or not moving (hence the $(3 \cdot k)$ part).
The number of Boolean functions on $n$ variables is $2^{2^n}$.
If $k = p(n)$ then the number of automata is no more than $2^{p'(n)}$ (where $p(n)$ and $p'(n)$ are polynomials) which is less than $2^{2^n}$ therefore there are more Boolean functions than automata of polynomial size. So there must be a Boolean function without a polynomial size automata $\blacksquare$
This result can also be extended to nondeterministic automata.
The number of 2NFAs with $k$ states is no more than $ 2^{3 \cdot k \cdot k \cdot \left| \Sigma \right|} = 2^{12 \cdot k^2}$ (because every transition from a state to a state with a given symbol and head movement can either be there or not be) which for $k$ polynomialy related to $n$ is still $2^{p(n)}$.
Now let's consider probabilistic automata. That is, for each transition from a state to a state with given input symbol and head movement there is a probability from a set $S \subseteq [0,1]$ assigned to it. Of course the probabilities for all transitions from a given state and input symbol must sum to 1. We will consider bounded-error computation - the automaton has to give the correct answer with probability $\geq \frac{2}{3}$.
If $S = \left\{ 0, \frac{1}{2}, 1 \right\}$ (these are sometimes called coin-flipping automata) then the result still holds - there are no more than $3^{3 \cdot k^2 \cdot \left| \Sigma \right|} = 2^{12 \cdot \log_{2}{3} \cdot k^2}$ such automata.
The result also holds for any other set $S$ ($S$ is allowed to depend on $n$) that is considerably smaller than $2^{2^n}$. The number of such automata is no more than $\left| S \right|^{12 \cdot k^2}$. For example $\left| S \right| = 2^{1.99^n}$ would be fine.
The question: What happens if we allow all rational probabilities? Does there exist a hard Boolean function for such probabilistic two-way automata?
Intuitively, going from probabilities from a quite large set $S$ to arbitrary rational probabilities shouldn't make a big difference, however the problem is that this counting argument doesn't work anymore.
This question for logical circuits was answered here (and the proof also extends to automata that works polynomial time, but not if the working time is unbounded).
