Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space? Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $. 

It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (Szepietowski, 1994). (There is an ATM using sublogarithmic space for members but not for all non-members!) 

On the other hand,  Freivalds (1981) showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time (Greenberg and Weiss, 1986). Later, it was shown that no bounded-error $ o(\log\log n) $-space PTM can recognize a non-regular language in polynomial expected time (Dwork and Stockmeyer, 1990). My question is


  whether poly-time sublogarithmic-space PTMs recognize $ \mathtt{EQUALITY} $ with bounded-error.
I have found an answer to my own question. The result was given in Section 5 of Karpinski and Verbeek, 1987.

For any input of length $ n $, a PTM can construct $ \Theta(\log \log n) $ space with high probability (Section 4). (With a very small probability, the machine can also construct logarithmic space, and this might be seen as a "drawback" of the algorithm.) Then, the PTM can decide whether the numbers of $a$'s ($n$) and $b$'s ($m$) are equal with high probability by using $ O(\log \log n) $ space in polynomial time. 

The idea is as follows. If $ n \neq m $, then $ \exists k \leq 4 \log(n+m) $ such that $ n \not\equiv m \mod k $ (Alt and Mehlron, 1976). The PTM can pick a random $ k $ by using $ O(\log \log n) $ space. $ O(\log \log n) $ is also sufficient to keep a counter and so trying more than half of all possible $k$'s. The case of $ n \neq m $ can be detected with a probability more than $ 1 \over 2 $.