A converse Lyapunov theorem is established for discrete-time stochastic systems modeled by a set-valued mapping under mild regularity conditions. For this class of systems, it is shown that strong global recurrence is a necessary and sufficient condition for the existence of a smooth Lyapunov function that decreases in expected value along solutions outside of the set that is strongly globally recurrent. Robustness of strong global recurrence to sufficiently small perturbations is also established. (C) 2013 Elsevier Ltd. All rights reserved.