Suppose we're generating a sequence of 0s and 1s. We want a specific pattern 0011, and we are given this transition matrix with arbitrary probabilities
$$ \begin{bmatrix} p & q \\ q & p \\ \end{bmatrix} $$
where the first column and row is for 0, and the second column and and row are for 1.
Using this transition matrix, how do we end up with a transition matrix for patter 0011: (Our states are {1,0,00,001,0011}) $$ \begin{bmatrix} p&q&0&0&0 \\ q&0&p&0&0 \\ 0&0&p&q&0 \\ 0&q&0&0&p \\ 0&0&0&0&1 \\ \end{bmatrix} $$
I really have no idea how they arrived to this matrix. I am very lost. Any help is appreciated.
the first 2x2 matrix tells that you switch symbols (from 0 to 1 or from 1 to 0) with probability $q$.
The second 5x5 matrix provides a path towards state 0011. Let us analyze it more carefully:
from state "1", you switch to "0" with probability $q$
from state "0", you switch to state "00" with probability $p$
from state "00", you switch to state "001" with probability $q$
from state "001", you switch to state "0011" with probability $p$
once in state "0011" you remain there forever
To obtain the 5x5 matrix algorithmically from the 2x2 matrix, note that:
first block: the two way principal minor in the upper left corner of the 5x5 matrix matrix equals the 2x2 matrix, except for one entry which is replaced from $p$ to 0. This entry is now used to represent a transition to the second block
second block: the next two way principal minor of the 5x5 matrix matrix again equals the 2x2 matrix, except for two entries which are now replaced from $q$ and $p$ to 0 and 0. These entries are now used to represent a transition back to the first block or to the last block
last block: the last entry of the 5x5 matrix is a self-transition
In summary: the 5x5 matrix contains 3 blocks -- the first block captures the transitions to generate "00", the second block captures the transitions to generate "11" and the last block is a self transition.