  Random walk is one of the most classical and well-studied model in
probability theory. For two correlated random walks on lattice, every step of
the random walks has only two states, moving in the same direction or moving in
the opposite direction. This paper presents a decomposition method to study the
dependency structure of the two correlated random walks. By applying
change-of-time technique used in continuous time martingales (see for example
[1] for more details), the random walks are decomposed into the composition of
two independent random walks $X$ and $Y$ with change-of-time $T$, where $X$ and
$Y$ model the common movements and the counter movements of the correlated
random walks respectively. Moreover, we give a sufficient and necessary
condition for mutual independence of $X$, $Y$ and $T$.
