We consider random walks evolving in dynamic random environments and propose a criterion which, if satisfied, allows to decompose the random walk trajectory into i.i.d. increments, and ultimately to prove limit theorems. This criterion, dubbed the random Markov property, involves the construction of a random field built from the environment that has to satisfy a certain Markovian-like property along with some mixing estimates. We apply this criterion to correlated environments such as Boolean percolation and renewal chains featuring polynomial decay of correlations. Based on a joint work with Julien Allasia, Oriane Blondel, and Augusto Teixeira.