Let M be a two–way probabilistic one–counter automaton (2P1CA) that works with bounded error, say it accepts every word w that is in the language with probability ≥ 2/3 and rejects every other word with probability ≥ 2/3.
Fix an input word w of length n.
During the run of M on w a configuration consists of

• the finite control state of M (|Q| possibilities)
• the current head position i (0 ≤ i ≤ n-1)
• the content of the counter c ∈ ℕ .

Thus a configuration can be written as (q,i,c).
If we “freeze” the input word w (i.e. treat it as part of the machine) and forget the accepting / rejecting sink states, the probabilistic behaviour of M on w is nothing but an infinite-state Markov chain

 Pw = (Q × {0,…,n-1}) × ℕ

in which the counter can be incremented, decremented (while it is >0) or left unchanged, and the head can move one position to the left or right or stay, exactly as prescribed by M’s transition function.
Markov chains of this exact shape are called probabilistic one-counter processes, or (in the queueing-theory literature) quasi-birth–death (QBD) processes with m := |Q|·n “phases’’ (all pairs (q,i)) and an unbounded “level’’ (the counter value c).

For such Markov chains the probability of ever hitting a designated set of absorbing states (here: the accepting configurations) from a designated start state (here: (q0,0,0)) can be computed to any desired precision in deterministic polynomial time. The key references are

• K. Etessami & M. Yannakakis, “Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Non-linear Equations”, JACM 56(1), 2009.
• K. Etessami, A. Stewart & M. Yannakakis, “Polynomial-time algorithms for probabilistic pushdown automata”, LICS 2012 (building on SODA 2005).

These papers give a polynomial-time algorithm for probabilistic pushdown automata in general; a 2P1CA is the very special case in which the pushdown alphabet consists of one symbol, so their algorithm applies directly and becomes even simpler (the non-linear equations collapse to linear ones).

Algorithmic consequence.
Given M, w and its error bound ε (here ε = 1/3), we

1. construct the linear system that describes the reachability (acceptance) probabilities in the QBD Pw; the system has O(|Q|·n) unknowns and rational coefficients that have size polynomial in |M| and n;

2. solve this linear system (Gaussian elimination or any strongly polynomial linear-algebra routine) with a precision of, say, ±ε/2;

3. compare the resulting value p(M,w) with the threshold 1/2 (or 2/3, or any other fixed rational that separates acceptance from rejection).

All three steps use deterministic time polynomial in n and |M|, and at most a polynomial number of bits of working memory, so the decision problem “does M accept w with probability ≥ 2/3 ?’’ is in P. As a consequence

Languages recognised with bounded error by 2-way probabilistic one-counter automata belong to the complexity class P.

State of the art.
• No better upper bound (e.g. NL, L, …) is known.
• It is also open whether every language in P can be recognised by a 2P1CA with bounded error; i.e. we do not know whether the containment is strict.

In short

Best upper bound currently known:  Languages recognised by bounded-error two-way probabilistic one-counter  automata are contained in deterministic polynomial time, i.e. in P.