  We prove stochastic stability of chaotic maps for a general class of Markov
random perturbations (including singular ones) satisfying some kind of mixing
conditions. One of the consequences of this statement is the proof of Ulam's
conjecture about the approximation of the dynamics of a chaotic system by a
finite state Markov chain. Conditions under which the localization phenomenon
(i.e. stabilization of singular invariant measures) takes place are also
considered. Our main tools are the so called bounded variation approach
combined with the ergodic theorem of Ionescu-Tulcea and Marinescu, and a random
walk argument that we apply to prove the absence of ``traps'' under the action
of random perturbations.
