We investigate stochastic averaging theory for locally Lipschitz discrete-time nonlinear systems with stochastic perturbation and its applications to convergence analysis of discrete-time stochastic extremum seeking algorithms. Firstly, by defining two average systems (one is continuous time, the other is discrete time), we develop discrete-time stochastic averaging theorem for locally Lipschitz nonlinear systems with stochastic perturbation. Our results only need some simple and applicable conditions, which are easy to verify, and remove a significant restriction present in existing results: global Lipschitzness of the nonlinear vector field. Secondly, we provide a discrete-time stochastic extremum seeking algorithm for a static map, in which measurement noise is considered and an ergodic discrete-time stochastic process is used as the excitation signal. Finally, for discrete-time nonlinear dynamical systems, in which the output equilibrium map has an extremum, we present a discrete-time stochastic extremum seeking scheme and, with a singular perturbation reduction, we prove the stability of the reduced system. Compared with classical stochastic approximation methods, while the convergence that we prove is in a weaker sense, the conditions of the algorithm are easy to verify and no requirements (e. g., boundedness) are imposed on the algorithm itself.