write down the transition probability matrix for a certain pattern 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.
