  A sliding window algorithm receives a stream of symbols and has to output at
each time instant a certain value which only depends on the last $n$ symbols.
If the algorithm is randomized, then at each time instant it produces an
incorrect output with probability at most $\epsilon$, which is a constant error
bound. This work proposes a more relaxed definition of correctness which is
parameterized by the error bound $\epsilon$ and the failure ratio $\phi$: A
randomized sliding window algorithm is required to err with probability at most
$\epsilon$ at a portion of $1-\phi$ of all time instants of an input stream.
This work continues the investigation of sliding window algorithms for regular
languages. In previous works a trichotomy theorem was shown for deterministic
algorithms: the optimal space complexity is either constant, logarithmic or
linear in the window size. The main results of this paper concerns three
natural settings (randomized algorithms with failure ratio zero and
randomized/deterministic algorithms with bounded failure ratio) and provide
natural language theoretic characterizations of the space complexity classes.
