Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

classify

Classify Markov chain states

Syntax

bins = classify(mc)
[bins,ClassStates,ClassRecurrence,ClassPeriod] = classify(mc)

Description

example

bins = classify(mc) partitions states of the discrete-time Markov chain mc into disjoint communicating classes and returns the class labels bins identifying the communicating class to which each state belongs.

example

[bins,ClassStates,ClassRecurrence,ClassPeriod] = classify(mc) additionally returns the states in each class ClassStates, whether the classes are recurrent ClassRecurrence, and class periods ClassPeriod.

Examples

collapse all

Consider this theoretical, right-stochastic transition matrix of a stochastic process.

Create the Markov chain that is characterized by the transition matrix P.

P = [0.5 0.5 0 0; 0.5 0.4 0.1 0; 0 0 0 1; 0 0 1 0];
mc = dtmc(P);

Plot a directed graph of the Markov chain. Visually identify to which communicating classes the states belong by using node colors.

figure;
graphplot(mc,'ColorNodes',true);

States 3 and 4 belong to a communicating class with period 2. States 1 and 2 are transient.

Programmatically identify to which communicating classes the states belong.

bins = classify(mc)
bins =

     1     1     2     2

bins is a 1-by-4 vector of communicating class labels. Elements of bins correspond to the states in mc.StateNames. For example, bins(3) = 2 indicates that state 3 is in communicating class 2.

Identify the communicating classes of a Markov chain. Then, determine whether the classes are recurrent and their periodicity.

Generate a random seven-state Markov chain. Specify that 40 random elements in the transition matrix should be zero.

rng(1);
mc = mcmix(7,'Zeros',40);

Plot a directed graph of the Markov chain. Visually identify to which communicating classes the states belong by using node colors.

figure;
graphplot(mc,'ColorNodes',true)

Identify the communicating classes in mc. Then, determine:

  • To which communicating class the states belong

  • Whether the communicating classes are recurrent

  • The period of each class.

[bins,ClassStates,ClassRecurrence,ClassPeriod] = classify(mc)
bins =

     6     4     6     3     2     5     1


ClassStates =

  1x6 cell array

    {["7"]}    {["5"]}    {["4"]}    {["2"]}    {["6"]}    {1x2 string}


ClassRecurrence =

  1x6 logical array

   0   0   0   0   0   1


ClassPeriod =

     1     1     1     1     1     2

There are seven classes in mc. All states are compose their own communicating class, except states 3 and 1, which compose class 6. Class 6 is the only recurrent class; classes 1 through 5 are transient. Class 6 has period 2; all other classes are aperiodic.

Identify the communicating classes of a Markov chain. Then, extract any recurrent subchains from the Markov chain.

rng(1);
mc = mcmix(7,'Zeros',40);

Identify all communicating classes in the Markov chain and whether the classes are recurrent.

[bins,~,ClassRecurrence] = classify(mc);
recurrentClass = find(ClassRecurrence,1)
recurrentState = find((bins == recurrentClass))
recurrentClass =

     6


recurrentState =

     1     3

Class 6, composed of states 1 and 3, is the only recurrent class in mc.

Create a subchain from class 6 by specifying at least one state in the subchain. Plot a digraph of the subchain.

sc = subchain(mc,recurrentState);

figure;
graphplot(sc,'ColorNodes',true);

Input Arguments

collapse all

Discrete-time Markov chain with NumStates states and transition matrix P, specified as a dtmc object.

Output Arguments

collapse all

Communicating class membership labels for each state, returned as a numeric vector of length NumStates. bins(j) is the label for the communicating class to which state j belongs. Bin values range from 1 through NumClasses.

State names in each class, returned as a cell vector of length NumClasses containing string vectors. ClassNames{j} is the list of states names in class j. State names are specified in mc.StateNames.

Class recurrence flags, returned as a logical vector of length NumClasses.

ClassRecurrence(j) indicates whether class j is recurrent (true) or transient (false).

Class periods, returned as a numeric vector of length NumClasses. ClassPeriod(j) is the period of class j. Aperiodic classes have period 1.

Note

The order of classes in ClassStates, ClassRecurrence, and ClassPeriod corresponds to the class numbers assigned in bins.

More About

collapse all

Communicating Class

Communicating classes of a Markov chain are the equivalence classes formed under the relation of mutual reachability. That is, two states are in the same class if and only if each is reachable from the other with nonzero probability in a finite number of steps.

Communicating classes are equivalent to strongly connected components in the associated digraph [2]. See graphplot.

Irreducible Chain

An irreducible chain is a Markov chain consisting of a single communicating class.

Unichain

A unichain is a Markov chain consisting of a single recurrent class and any transient classes that transition to the recurrent class.

Algorithms

  • classify determines recurrence and transience from the outdegree of the supernode associated with each communicating class in the condensed digraph [1]. An outdegree of 0 corresponds to recurrence; an outdegree that is greater than 0 corresponds to transience. See graphplot.

  • classify determines periodicity using a breadth-first search of cycles in the associated digraph, as in [3]. Class period is the greatest common divisor of the lengths of all cycles originating at any state in the class.

References

[1] Gallager, R.G. Stochastic Processes: Theory for Applications. Cambridge, UK: Cambridge University Press, 2013.

[2] Horn, R. and C. R. Johnson. Matrix Analysis. Cambridge, UK: Cambridge University Press, 1985.

[3] Jarvis, J. P. and D. R. Shier. "Graph-Theoretic Analysis of Finite Markov Chains." In Applied Mathematical Modeling: A Multidisciplinary Approach. Boca Raton: CRC Press, 2000.

Introduced in R2017b

Was this topic helpful?