# LFSR and Markov chain question [closed]

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?

-

## closed as unclear what you're asking by D.W., e-sushi♦, archie, poncho, fgrieuJul 24 '14 at 13:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

I find this question unclear. What do you have in mind as the statespace of the Markov chain? If the state is the entire state of the LFSR, then of course there is a trivial Markov chain, since it is a deterministic process, but this does not seem likely to be useful. So what did you have in mind? Let me put it another way. Why do you ask this question? What's the motivation or context where you plan to use this? How will you evaluate or use answers? As it stands the question seems a bit on the open-ended/ill-defined end. – D.W. Jun 18 '14 at 13:05
Yes, it does seem elementary, the context is to view the LFSR in other forms. The Berlekamp Massey algorithm gives an algorithm for this problem. In terms of numerical computations what would the equivalent Markov chain formulation take? So, if we did view the LFSR as a Markov chain what are the resources we would need, time, and space? – user14938 Jun 18 '14 at 13:10
I don't understand in what sense the Berlekamp-Massey algorithm is an algorithm for "this problem" - what problem? Please try to be more precise. Berlekamp-Massey has nothing to do with Markov chains; it has to do with recovering the LFSR initial fill and feedback polynomial, given observations of its output. As far as your last question in your comment: for what task? what Markov chain formulation? It's impossible to say what resources are needed, if we don't know what the task is. Again, LFSRs are a deterministic process, so modelling it as a Markov chain is not very helpful. – D.W. Jun 18 '14 at 13:14

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.