We propose the study of Markov chains on groups as a "quasi-isometry invariant" theory that encompasses random walks. In particular, we focus on certain classes of groups acting on hyperbolic spaces including (non-elementary) hyperbolic and relatively hyperbolic groups, acylindrically hyperbolic 3-manifold groups, as well as fundamental groups of certain graphs of groups with edge groups of subexponential growth. For those, we prove a linear progress result and various applications, and these lead to a Central Limit Theorem for random walks on groups quasi-isometric to the ones we consider.