1

I'm watching the David Silver series on YT which has raised a couple of questions:

In the Markov process (or chain), how are the directions to each successive state defined? For example, how are the arrow directions defined for the MP below? What's stopping our sample episodes from choosing A -> C -> D -> F?

enter image description here

Also, how is the probability transition matrix populated? From David's example, the probabilities seem to have already been set. For example:

enter image description here

nbro
  • 39,006
  • 12
  • 98
  • 176
mason7663
  • 603
  • 3
  • 10

1 Answers1

4
  1. It's not possible, as in the chain illustrated there are no transitions between A and C, C and D, and D and F. Only sequences where transitions exist are possible. The choice of transitions is arbitrary; it depends on what you want to model with it.

As DuttaA says in his comment, you can imagine that all nodes are linked with all other nodes, but those links have a transition probability of 0.0; so the probability of observing the sequence ACDF is actually 0.0 as well. In order to make the diagram more easy to understand, zero-probability transitions are generally not shown.

  1. There is no prescribed method of populating the transition probabilities. You can define the probabilities manually, randomly, or however you like. You could derive them from observable training data.

Re updating: this depends on the application. If you are modelling a process with known probabilities, you would not update the probabilities; if you are modelling a dynamic process which changes over time, then this is something you might want to consider. However, from my own experience (HMMs in speech recognition), once they have been assigned, they are generally kept as they are.

A Markov chain is really a fairly basic model; it gets more complex with a Hidden Markov Model, where you would generally use a learning algorithm to assign the transition and emission probabilities.

Oliver Mason
  • 5,322
  • 12
  • 32
  • 2
    I think form the question OP can't grasp the fact that the arrows indicate transition possibility and no arrow indicate 0 transition probablity, which means an arrow with 0 probablity. You might want to elaborate that. –  Feb 29 '20 at 18:28
  • Yes, DuttaA, thanks. So I guess the transitions are dictated in the Probability Transition Matrix? If so, then I presume the sequences are set as Oliver Mason says in point 2. So, if they’re set randomly, how are the probabilities updated to their ‘real’ probabilities (or does that not happen?). – mason7663 Feb 29 '20 at 21:15
  • @DuttaA Thanks for your comments; I have extended my answer. – Oliver Mason Feb 29 '20 at 21:21
  • Thanks for updating, Oliver. If, for example, the environment is a board game and its states are the various position the game pieces may be in, how would the PTM be initialised? How would it be (if it is?) updated? – mason7663 Feb 29 '20 at 21:57
  • 1
    It's probably best to put that in a new question; and give a concrete example of a game. – Oliver Mason Feb 29 '20 at 22:12