  We study a random unitary circuit model of an impurity moving through a
chaotic medium. The exchange of information between the medium and impurity is
controlled by varying the velocity of the impurity, $v_d$, relative to the
speed of information propagation within the medium, $v_B$. Above supersonic
velocities, $v_d> v_B$, information cannot flow back to the impurity after it
has moved into the medium, and the resulting dynamics are Markovian. Below
supersonic velocities, $v_d< v_B$, the dynamics of the impurity and medium are
non-Markovian, and information is able to flow back onto the impurity. We show
the two regimes are separated by a continuous phase transition with exponents
directly related to the diffusive spreading of operators in the medium. This is
demonstrated by monitoring an out-of-time-order correlator (OTOC) in a scenario
where the impurity is substituted at an intermediate time. During the Markovian
phase, information from the medium cannot transfer onto the replaced impurity,
manifesting in no significant operator development. Conversely, in the
non-Markovian phase, we observe that operators acquire support on the newly
introduced impurity. We also characterize the dynamics using the coherent
information and provide two decoders which can efficiently probe the transition
between Markovian and non-Markovian information flow. Our work demonstrates
that Markovian and non-Markovian dynamics can be separated by a phase
transition, and we propose an efficient protocol for observing this transition.
