Angluin's algorithm is a well known approach for learning black boxes as minimal deterministic finite automata in polynomial time. In order to infer finite state machines instead of automata, different variants of this algorithm have been proposed. These algorithms rely on two types of queries which can be asked to an oracle: output and equivalence queries. If the black box is not equivalent to the learnt model, the oracle replies with a counterexample. The complexity of these algorithms depends on the length of the counterexamples provided by the oracle. The aim of this paper is to compare the average practical complexity of three of these algorithms in the case of poor oracles, in particular when the counterexamples are constructed with random walks.