Problem 5 (Markov Process for Word Types). Assume that each word that a particular poet writes can be classified as a noun, verb, adjective, adverb, preposition, or conjunction, and that the poet has written at least word in the past. In the future, whenever a poet intends to write a word, they will look at the last word they wrote, and roll a 20-sided die that is equally likely to land on any of the whole numbers from 1 to 20, inclusive. If the last word they wrote was a noun, and they roll any number from 1 to 15, inclusive, then they write a verb. If they roll a number from 16 to 20, inclusive, then they write a conjunction. If the last word they wrote was a verb, and they roll a 1 or 2, then they write a noun. If they roll a number from 3 to 6, they write an adjective. If they roll from 7 to 12, they write an adverb. If they roll from 13 to 16, they write a preposition. If they roll from 17 to 20, they write a conjunction. If the last word they wrote was an adjective, and they roll from 1 to 14, they write a noun. If they roll from 15 to 20, they write another adjective.

Number 5 is a Markov process problem, like numbers 3 and 4.

Making the transition matrix is part (a), you label the rows and columns of the matrix and fill in the entries.

You can pick labels N, V, Adj, Adv, P, C for the six states. When your current state is "N" this means that the most recent word written was a noun, for example.

So our labels for the columns and rows of the transition matrix look like this:

N V Adj Adv P C

N

V

Adj

Adv

P

C

We have a 6 x 6 transition matrix, and we are to fill in each of the 36 entries with the given information.

The first piece of information says that if a 1 to 15 is rolled, then the word after a noun (such as "George") is a verb (second word in example: "George walks"), and if a 16 to 20 is rolled, then the word after a noun is a conjunction (second word in example: "George and"). So we see that the probabilities under "N" are 15/20 next to the "V" row, and 5/20 next to the "C" row. There must be 0's for the other "N" column entries, since 15/20 + 5/20 already adds up to 1. In decimal form, we get:

N V Adj Adv P C

N 0

V 0.75

Adj 0

Adv 0

P 0

C. 0.25

Similarly, you can fill in each of the other columns with the given information, to obtain this transition matrix. This is similar to the type of transition matrix used by Google for some of its natural language processing work.

For part (b), your current state is Adj so one way to think about this is that you have an initial distribution column matrix D_0 equal to (with the labels in the same order as above)

0

0

1

0

0

0

because you know the current state is Adj with 100% probability. And part (b) is asking you the probability the you'll have a preposition for the word after the next word. In other words, after two time periods, what will be in the P row? More precisely, what is in the P row of D_2? MATLAB can help you compute this, and it has a simple answer.