COMP 2190

A video submission proposing a explanation and solution to the Markov Chain question on the COMP 2190 midterm review.

Sorry that the text is so hard to read. Try exploding to full screen view. It still won't be legible, but it may help a little bit.

"[0:14] Hello, so this is a video response to the forum thread where you put proposed answers to review questions; because-, video because its hard to draw pictures and matrices and I'm wanting to cover the-, the Markov chain question.

[0:36] So in- in answering this, we're looking at this matrix here. [0:42] And the check that shows that this would be a valid state transition matrix is that the rows sum to one. They should each sum to one. They represent state transitions from a state i to state j, so they should all uniquely sum to one because of what you'd call conservation of mass.

[1:12] So, if we want wanted to draw a state diagram that corresponded to this matrix M, what you can do is, since there's four rows there'll be four unique states, and for each state we just, say, choose a row; so I'll say first state is A, B, then C, then D. So, A, B, C, D. And so, the probability of transiting from A to A is zero. So, I could draw a loop here, but I didn't [gesturing at A]. The probability of transiting from A to B is 50%. The probability of transiting from A to C is 0.4, 40%. And 10% transiting from A to D. And so you just walk down the rows like this. If you're in colum- if you're in row D, then the probability from transiting from D to A would be 0.25, and D to D would be zero. So, nothing there. [2:25] C for instance has a 0.2 percent chance of re-entering state C after one iteration. [but see fade in correction at 2:27]

[2:36] So, how do we operate on, on this [gestures at matrix]? We're given this initial state, what we do is take this, this transition matrix and we take its transpose [2:49]. So we've got the state transition matrix [gesture: upper block of numbers in inset window], we take the transpose of that matrix [gesture: second block of numbers], and then for a given state, x sub i [gesture: third block, the input vector], we transit to the next state by multiplying the transpose of the state transition matrix [gesture: second block of numbers] by that state [gesture: third block]. And what we get out is the next state [gesture: bottom block, the output vector]. And this process could keep continuing. We could take this [gesture: bottom block] state and multiply on the left by this transpose [gesture: second block], or equivalently we could just keep taking powers of the transpose if we want- wanted a sort of a known step, state. So that would be the way to operate. In this case we have the i'th state [3:43, cursor highlighting] is gonna just pick out the second column [3:47] of the transpose [gesture: up and down second column of transpose matrix, second block], and so it does.

[3:53] So one multiplication of the transpose of the transition matrix times a state gives you the next state."

Category:

Education

Tags:

• markov
• matrix
• computer
• science

[Arcsecant]

Indeed, this Markov chain is meant to represent population systems (animals, chemical species, etc.) and would probably not be well suited to applications such as encryption.

[Carsonetric]

Why not do a transpose for at least two iterations and show the relative probability of passing from any initial point on the first matrix to any chosen concluding point on the matrix produced after the second iteration? Then is the resultant probability of passing from the initial point to the concluding point uniformly distributed? If it can be easily predicted then this Markov Chain is useless for encryption purposes!