  Consider a nearest neighbor random walk on the two-dimensional integer
lattice, where each vertex is initially labeled either `H' or `V', uniformly
and independently. At each discrete time step, the walker resamples the label
at its current location (changing `H' to `V' and `V' to `H' with probability
$q$). Then, it takes a mean zero horizontal step if the new label is `H', and a
mean zero vertical step if the new label is `V'. This model is a randomized
version of the deterministic rotor walk, for which its recurrence (i.e.,
visiting every vertex infinitely often with probability 1) in two dimensions is
still an open problem. We answer the analogous question for the the
horizontal-vertical walk, by showing that the horizontal-vertical walk is
recurrent for $q \in (\frac{1}{3},1]$.
