LFSR and Markov chain question This may seem an elementary question about LFSRs, and their link to Markov chains. LFSRs show Markov chain behaviour in that there can be a transition matrix defined over the LFSR, this follows from the very definition of the LFSR. Is there any formal formulation for the LFSR as a Markov chain?
In a standard linear feedback shift register (LFSR), the succession of states 
(generally taken to mean the shift register contents) is
predetermined; there is nothing random about the state transitions. Given
any state and the feedback polynomial, the next state can be readily computed.
Indeed, the states recur in periodic cycles.

In contrast, in a Markov chain, the next state cannot be determined from
knowledge of the current state; all we know are the (conditional)
probabilities that the next state is $S_j$ given that the current state is
$S_i$.  Think of it this way: the transition matrix of a $N$-state Markov
chain is a $N\times N$ matrix of transition probabilities. In contrast,
an LFSR with $N$ bits/symbols has $2^N$ (more generally, $q^N$) different
states, but its transition matrix is only an $N\times N$ matrix.  If you
were to write down the transition matrix in Markov-chain style, it would
be a $2^N\times 2^N$ matrix and all the transition probabilities (entries
in the matrix) would be either $0$ or $1$ and there would be exactly 
one $1$ in each row and in each column, that is, it would be a permutation
matrix.