Thread Subject:

Please help me to generate a markov chain.

I have a initial state (out of n states ) , a transition probability matrix and number of steps. How to generate a markov chain.Please help......

"DEVANAND " <devanandiamin7@gmail.com> wrote in message <hokljp$c4f$1@fred.mathworks.com>...
> I have a initial state (out of n states ) , a transition probability matrix and number of steps. How to generate a markov chain.Please help......

  What is it you mean when you ask "to generate a markov chain"? Do you just want to calculate the probabilities of the various states after a number of steps, given the initial state. That is simply a matter of matrix multiplication. Or perhaps you wish to simulate this markov chain with actual matlab variables using the 'rand' function. You need to describe what you want in some detail.

  In either case could you please show us what you have accomplished so far in this problem.

  I assume when you say "a transition probability matrix", you mean that the chain satisfies the Chapman–Kolmogorov stationary condition.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <holf1i$92h$1@fred.mathworks.com>...
> "DEVANAND " <devanandiamin7@gmail.com> wrote in message <hokljp$c4f$1@fred.mathworks.com>...
> > I have a initial state (out of n states ) , a transition probability matrix and number of steps. How to generate a markov chain.Please help......
>
> What is it you mean when you ask "to generate a markov chain"? Do you just want to calculate the probabilities of the various states after a number of steps, given the initial state. That is simply a matter of matrix multiplication. Or perhaps you wish to simulate this markov chain with actual matlab variables using the 'rand' function. You need to describe what you want in some detail.
>
> In either case could you please show us what you have accomplished so far in this problem.
>
> I assume when you say "a transition probability matrix", you mean that the chain satisfies the Chapman–Kolmogorov stationary condition.
>
> Roger Stafford

sir,
    I actually wanted to test if computer can generate music.While searching internet I found a page in wikipedia on markov chains and its application in music.I found also 2 transition matrices(one a firstorder and other second order markov chain) where the states are music notes. To be true , I doesnot have any prior knowledge on markov chain.But was interested to simulate my experiment using MATLAB. In Matlab but I saw only Hidden markov chains. A command 'hmmgenerate' which has a syntax as below

 [seq,states] = hmmgenerate(len,TRANS,EMIS)

takes a known Markov model, specified by transition probability matrix TRANS and emission probability matrix EMIS, and uses it to generate
    *A random sequence seq of emission symbols
    *A random sequence states of states
The length of both seq and states is len.

But now I am not clear about EMISSION MATRIX. I was trying to get some code related to markov chain for my experiment.My aim is to simulate the experiment in matlab and then learn the basics. Do you have any suggestion for me. Which books are good for these topics to read.

DEVANAND T

"DEVANAND " <devanandiamin7@gmail.com> wrote in message <hp1e6n$6hj$1@fred.mathworks.com>...
> sir,
> I actually wanted to test if computer can generate music.While searching internet I found a page in wikipedia on markov chains and its application in music.I found also 2 transition matrices(one a firstorder and other second order markov chain) where the states are music notes. To be true , I doesnot have any prior knowledge on markov chain.But was interested to simulate my experiment using MATLAB. In Matlab but I saw only Hidden markov chains. A command 'hmmgenerate' which has a syntax as below
>
> [seq,states] = hmmgenerate(len,TRANS,EMIS)
>
> takes a known Markov model, specified by transition probability matrix TRANS and emission probability matrix EMIS, and uses it to generate
> *A random sequence seq of emission symbols
> *A random sequence states of states
> The length of both seq and states is len.
>
> But now I am not clear about EMISSION MATRIX. I was trying to get some code related to markov chain for my experiment.My aim is to simulate the experiment in matlab and then learn the basics. Do you have any suggestion for me. Which books are good for these topics to read.
>
> DEVANAND T

  From your reply you apparently want to simulate an actual Markov chain defined by a probability transition array using the 'rand' function. For your own home-grown chain generator, let us suppose that your "notes" are represented by the integers from 1 to n. For an m-th order Markov chain, let M be an m+1-dimensional array of size n x n x n x ... x n in which the first dimension columns, M(:,s_n-1,s_n-2,...,s_n-m), give the probabilities of transition to the values 1:n given each combination of previous states, s_n-1,s_n-2,...,s_n-m.

  Then use a for-loop to work your way forward step-by-step from an initial set of m successive states (notes) to the next state as follows:

 p = M(:,s_n-1,s_n-2,...,s_n-m); % Get the appropriate column of M
 % Then generate the next state, s_n, with these probabilities
 [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]);
 (Store this newly created s_n in a vector of successive "notes")

where s_n will be the next state. At the next trip through the for-loop, you will of course be using the updated (shifted)
 M(:,s_n,s_n-1,s_n-2,...,s_n-m+1).

  The result will be a Markov chain of as many steps beyond the initial set of states as trips you choose to take through the for-loop.

  For this to work properly you need to ensure that each of the columns of M consist of non-negative quantities whose sum is one. (If you want to create random columns with this property you might like to use my 'randfixedsum' at

 http://www.mathworks.com/matlabcentral/fileexchange/9700 )

  (Note: The above use of 'histc' may not be the most efficient way of choosing the next s from just a single value of rand. You might consider using a specialized binary search technique instead.)

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hp65fe$d88$1@fred.mathworks.com>...
> "DEVANAND " <devanandiamin7@gmail.com> wrote in message <hp1e6n$6hj$1@fred.mathworks.com>...
> > sir,
> > I actually wanted to test if computer can generate music.While searching internet I found a page in wikipedia on markov chains and its application in music.I found also 2 transition matrices(one a firstorder and other second order markov chain) where the states are music notes. To be true , I doesnot have any prior knowledge on markov chain.But was interested to simulate my experiment using MATLAB. In Matlab but I saw only Hidden markov chains. A command 'hmmgenerate' which has a syntax as below
> >
> > [seq,states] = hmmgenerate(len,TRANS,EMIS)
> >
> > takes a known Markov model, specified by transition probability matrix TRANS and emission probability matrix EMIS, and uses it to generate
> > *A random sequence seq of emission symbols
> > *A random sequence states of states
> > The length of both seq and states is len.
> >
> > But now I am not clear about EMISSION MATRIX. I was trying to get some code related to markov chain for my experiment.My aim is to simulate the experiment in matlab and then learn the basics. Do you have any suggestion for me. Which books are good for these topics to read.
> >
> > DEVANAND T
>
> From your reply you apparently want to simulate an actual Markov chain defined by a probability transition array using the 'rand' function. For your own home-grown chain generator, let us suppose that your "notes" are represented by the integers from 1 to n. For an m-th order Markov chain, let M be an m+1-dimensional array of size n x n x n x ... x n in which the first dimension columns, M(:,s_n-1,s_n-2,...,s_n-m), give the probabilities of transition to the values 1:n given each combination of previous states, s_n-1,s_n-2,...,s_n-m.
>
> Then use a for-loop to work your way forward step-by-step from an initial set of m successive states (notes) to the next state as follows:
>
> p = M(:,s_n-1,s_n-2,...,s_n-m); % Get the appropriate column of M
> % Then generate the next state, s_n, with these probabilities
> [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]);
> (Store this newly created s_n in a vector of successive "notes")
>
> where s_n will be the next state. At the next trip through the for-loop, you will of course be using the updated (shifted)
> M(:,s_n,s_n-1,s_n-2,...,s_n-m+1).
>
> The result will be a Markov chain of as many steps beyond the initial set of states as trips you choose to take through the for-loop.
>
> For this to work properly you need to ensure that each of the columns of M consist of non-negative quantities whose sum is one. (If you want to create random columns with this property you might like to use my 'randfixedsum' at
>
> http://www.mathworks.com/matlabcentral/fileexchange/9700 )
>
> (Note: The above use of 'histc' may not be the most efficient way of choosing the next s from just a single value of rand. You might consider using a specialized binary search technique instead.)
>
> Roger Stafford

Thanks very much for such a detailed and helpful reply.I have written a script for 1st order markov chain and trying for 2nd order.

DEVANAND T

> Thanks very much for such a detailed and helpful reply.I have written a script for 1st order markov chain and trying for 2nd order.
>
> DEVANAND T

Hi,
I am a new matlab user, and I also trying to use markov chain..
could you show me how you build your first order markov chain, please
because I have my Probability transition matrix, but now I dont know how to do to
predict the next step using this matrix.
I could maybe take advantage of your code to finish mine
best regards
Yoann

"DEVANAND " <devanandiamin7@gmail.com> wrote in message <hpbf5d$f77$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hp65fe$d88$1@fred.mathworks.com>...
> > "DEVANAND " <devanandiamin7@gmail.com> wrote in message <hp1e6n$6hj$1@fred.mathworks.com>...
> > > sir,
> > > I actually wanted to test if computer can generate music.While searching internet I found a page in wikipedia on markov chains and its application in music.I found also 2 transition matrices(one a firstorder and other second order markov chain) where the states are music notes. To be true , I doesnot have any prior knowledge on markov chain.But was interested to simulate my experiment using MATLAB. In Matlab but I saw only Hidden markov chains. A command 'hmmgenerate' which has a syntax as below
> > >
> > > [seq,states] = hmmgenerate(len,TRANS,EMIS)
> > >
> > > takes a known Markov model, specified by transition probability matrix TRANS and emission probability matrix EMIS, and uses it to generate
> > > *A random sequence seq of emission symbols
> > > *A random sequence states of states
> > > The length of both seq and states is len.
> > >
> > > But now I am not clear about EMISSION MATRIX. I was trying to get some code related to markov chain for my experiment.My aim is to simulate the experiment in matlab and then learn the basics. Do you have any suggestion for me. Which books are good for these topics to read.
> > >
> > > DEVANAND T
> >
> > From your reply you apparently want to simulate an actual Markov chain defined by a probability transition array using the 'rand' function. For your own home-grown chain generator, let us suppose that your "notes" are represented by the integers from 1 to n. For an m-th order Markov chain, let M be an m+1-dimensional array of size n x n x n x ... x n in which the first dimension columns, M(:,s_n-1,s_n-2,...,s_n-m), give the probabilities of transition to the values 1:n given each combination of previous states, s_n-1,s_n-2,...,s_n-m.
> >
> > Then use a for-loop to work your way forward step-by-step from an initial set of m successive states (notes) to the next state as follows:
> >
> > p = M(:,s_n-1,s_n-2,...,s_n-m); % Get the appropriate column of M
> > % Then generate the next state, s_n, with these probabilities
> > [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]);
> > (Store this newly created s_n in a vector of successive "notes")
> >
> > where s_n will be the next state. At the next trip through the for-loop, you will of course be using the updated (shifted)
> > M(:,s_n,s_n-1,s_n-2,...,s_n-m+1).
> >
> > The result will be a Markov chain of as many steps beyond the initial set of states as trips you choose to take through the for-loop.
> >
> > For this to work properly you need to ensure that each of the columns of M consist of non-negative quantities whose sum is one. (If you want to create random columns with this property you might like to use my 'randfixedsum' at
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/9700 )
> >
> > (Note: The above use of 'histc' may not be the most efficient way of choosing the next s from just a single value of rand. You might consider using a specialized binary search technique instead.)
> >
> > Roger Stafford
>
> Thanks very much for such a detailed and helpful reply.I have written a script for 1st order markov chain and trying for 2nd order.
>
> DEVANAND T

In: histc(rand,[-inf;cumsum(p(1:n-1));inf]);

Isn't it p(1:n)? p has the dimension nx1. If you just call it with p(1:n-1) you cut off the last possible state for your calculation.

Stefan

"Stefan Depeweg" wrote in message <ik8llt$bnu$1@fred.mathworks.com>...
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hp65fe$d88$1@fred.mathworks.com>...
> > > .......
> > > [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]);
> > > .......
>
> In: histc(rand,[-inf;cumsum(p(1:n-1));inf]);
>
> Isn't it p(1:n)? p has the dimension nx1. If you just call it with p(1:n-1) you cut off the last possible state for your calculation.
>
> Stefan
- - - - - - - - - - -
  In reply to your question, Stefan, where (almost a year ago) I said

 [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]); ,

in accordance with the definition of histc, the n-th, next-to-last of the n+1 "edges" intervals there would be:

 sum(p(1:n-1)) <= rand < inf.

Since the p-values are assumed to all be non-negative and to have a sum of one, this interval would actually be

 sum(p(1:n-1)) <= rand <= 1 = sum(p(1:n))

which has width of p(n), and is just what was intended. None of the n possible values is left out. (The last "edges" value of course would be an impossible "rand == inf" and would never occur.)

  The reason for not just using cumsum(p) was to guard against possible round-off errors in calculating 'cumsum'. Any erroneous final value slightly below one would provide a small chance for an invalid bin value for s_n of n+1 which I wanted to avoid.

  (As I mentioned before, using histc on a single rand value may not be the most efficient way of determining which interval rand falls in. A simple binary search procedure might be better.)

Roger Stafford

Hey,
thank you for your reply! I am asking the question because currently I am implementing a Markov Process for my bachelor thesis.

I have the following problem:

I have 4 "1th order" Markov processes that are coupled in a circle. That means, if we look at one markov process there is the following dependance:

Pr(s1(t) | s1(t-1), s2(t-2), s4(t-2)) ( the 1 in s1 should refer to markov process 1

Pr(s2(t) | s2(t-1), s1(t-2), s3(t-2)) (for markov process 2)
...


that means the next state of one markov process does not only depend on its past state but also on the state of the neighboring processes at t-2.

Now I am thinking about the normalisation constraints for my transition matrix:

Lets say every process has n states. Then for every process I have a n x n x n x n Transition-Matrix in which the first dimension columns, give the probabilities of transition to the values 1:n given each combination of previous states, s1(t-1) s2(t-2) s4(t-2) (in this example if we would look at process 1)

Could you may help me by saying what exactly should sum up to 1 in this matrix? For me its very hard to think about it when the dimension are higher than 2.

Regards

Stefan

"Roger Stafford" wrote in message <ik911l$86q$1@fred.mathworks.com>...
> "Stefan Depeweg" wrote in message <ik8llt$bnu$1@fred.mathworks.com>...
> > > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hp65fe$d88$1@fred.mathworks.com>...
> > > > .......
> > > > [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]);
> > > > .......
> >
> > In: histc(rand,[-inf;cumsum(p(1:n-1));inf]);
> >
> > Isn't it p(1:n)? p has the dimension nx1. If you just call it with p(1:n-1) you cut off the last possible state for your calculation.
> >
> > Stefan
> - - - - - - - - - - -
> In reply to your question, Stefan, where (almost a year ago) I said
>
> [t,s_n] = histc(rand,[-inf;cumsum(p(1:n-1));inf]); ,
>
> in accordance with the definition of histc, the n-th, next-to-last of the n+1 "edges" intervals there would be:
>
> sum(p(1:n-1)) <= rand < inf.
>
> Since the p-values are assumed to all be non-negative and to have a sum of one, this interval would actually be
>
> sum(p(1:n-1)) <= rand <= 1 = sum(p(1:n))
>
> which has width of p(n), and is just what was intended. None of the n possible values is left out. (The last "edges" value of course would be an impossible "rand == inf" and would never occur.)
>
> The reason for not just using cumsum(p) was to guard against possible round-off errors in calculating 'cumsum'. Any erroneous final value slightly below one would provide a small chance for an invalid bin value for s_n of n+1 which I wanted to avoid.
>
> (As I mentioned before, using histc on a single rand value may not be the most efficient way of determining which interval rand falls in. A simple binary search procedure might be better.)
>
> Roger Stafford