  We consider the discrete time unitary dynamics given by a quantum walk on
$\Z^d$ performed by a particle with internal degree of freedom, called coin
state, according to the following iterated rule: a unitary update of the coin
state takes place, followed by a shift on the lattice, conditioned on the coin
state of the particle. We study the large time behavior of the quantum
mechanical probability distribution of the position observable in $\Z^d$ for
random updates of the coin states of the following form. The random sequences
of unitary updates are given by a site dependent function of a Markov chain in
time, with the following properties: on each site, they share the same
stationnary Markovian distribution and, for each fixed time, they form a
deterministic periodic pattern on the lattice.
  We prove a Feynman-Kac formula to express the characteristic function of the
averaged distribution over the randomness at time $n$ in terms of the nth power
of an operator $M$. By analyzing the spectrum of $M$, we show that this
distribution posesses a drift proportional to the time and its centered
counterpart displays a diffusive behavior with a diffusion matrix we compute.
Moderate and large deviations principles are also proven to hold for the
averaged distribution and the limit of the suitably rescaled corresponding
characteristic function is shown to satisfy a diffusion equation.
  An example of random updates for which the analysis of the distribution can
be performed without averaging is worked out. The random distribution displays
a deterministic drift proportional to time and its centered counterpart gives
rise to a random diffusion matrix whose law we compute. We complete the picture
by presenting an uncorrelated example.
