A converse Lyapunov theorem is established for discrete-time stochastic systems with non-unique solutions. In particular, it is shown that global asymptotic stability in probability implies the existence of a continuous Lyapunov function, smooth outside of the attractor, that decreases in expected value along solutions. The keys to this result are mild regularity conditions imposed on the set-valued mapping that characterizes the update of the system state, and the ensuing robustness of global asymptotic stability in probability to sufficiently small state-dependent perturbations.