I've been stuck on these problems for a while. I keep banging my head against the wall, but my calculations are incorrect each time. I sum the probabilities together for each possibility (it's a letter + it's a letter etc.), but I must have gotten the wrong impression from my lecturer's notes about markov chains.
- What is the probability that the next 3 symbols are digits?
(.7 + .2 + .2)
- What is the probability that the next 2 symbols are digits and the 2 symbols after that are letters?
(1-.5) + .3 + .3
- Predict the probability
that the symbol two away from the current letter is also a letter.
.3 + .2 + .2
Edit: As you can tell by these calculations, I am confused.
Note: the way the matrix is written is as a row-stochastic matrix (rows sum to one). Many other texts prefer writing markov chains as column-stochastic matrices instead (where columns add to one). Keep this in mind when reading other books and literature. What follows will be in regards to row-stochastic matrices
The current symbol is a letter (given as a part of the problem statement). We ask what is the probability that the next symbol is a digit?
The fact that the current symbol is a letter implies that we should look at the first row. Where we want to end up corresponds to which column to read. The probability of going from state one(letter) to state two(digit) lies at the first row second column entry. In this case the entry is a $.1$. In other words, $Pr(letter\mapsto digit)=0.1$
When starting as a digit, we want to see what the probability that the following letter is again a digit. Looking at the second row (since that is the current state), we look at the second column entry (since that is where we want to find the probability of ending up). We see in the matrix that this is an $0.3$. In other words, $Pr(digit\mapsto digit)=0.3$
Starting as a letter, what is the probability that the next two characters are both digits? Well, first it would have to be going from letter to digit, and then from digit to digit.
$Pr(letter\mapsto digit\mapsto digit) = Pr(letter\mapsto digit)\cdot Pr(digit\mapsto digit) = 0.1\cdot 0.3$
How about starting as a letter and the next three characters all being digits?
What about the next two being digits and the two after that being letters?
$Pr(letter\mapsto digit\mapsto digit\mapsto letter\mapsto letter) = Pr(letter\mapsto digit)\cdot Pr(digit\mapsto digit)\cdot Pr(digit\mapsto letter)\cdot Pr(letter\mapsto letter)$
For the third part, note that you can choose to either draw yourself a tree diagram and solve it that way, but it is more convenient to use properties of stochastic matrices. Simply raising the matrix to the power $n$ corresponds to moving $n$ time-steps away. In other words, the row $a$ column $b$ entry corresponds to the probability to move from state $a$ to state $b$ in exactly $n$ steps.
Approaching directly via tree diagram though, one can break into cases based on what the inbetween character is. It will be one of the following: $letter\mapsto letter\mapsto letter$, $letter\mapsto digit\mapsto letter$, $letter\mapsto other\mapsto letter$. Applying a mixture of addition principle and multiplication principle, we have: $Pr(letter\mapsto ?\mapsto letter) = Pr(letter\mapsto letter)Pr(letter\mapsto letter) + Pr(letter\mapsto digit)Pr(digit\mapsto letter) + Pr(letter\mapsto other)Pr(other\mapsto letter)$
A few other reminders:
$Pr(A~\text{or}~B~\text{happening})=Pr(A\cup B)$
$Pr(A~\text{and}~B~\text{happening})=Pr(A\cap B)$
Inclusion exclusion (two event version): $Pr(A\cup B) = Pr(A)+Pr(B)-Pr(A\cap B)$
Addition principle for mutually exclusive events: $Pr(A\cup B)= Pr(A)+Pr(B)$
Multiplication principle (two event version): $Pr(A\cap B)= Pr(A)\cdot Pr(B\mid A)$
Multiplication principle for independent events: $Pr(A\cap B)=Pr(A)\cdot Pr(B)$