Periodicity of DiGraph/MarkovChain

[oyamad]

• Original PR: MARKOV: More efficient implementation for computing stationary distributions #79 (comment)
• Comment: Add states/nodes to MarkovChain/DiGraph #237 (comment)

[oyamad]

For example, what period do we want to say the following Markov chain has?

P = [[0, 0.5, 0, 0, 0.5],
     [0, 0, 0.5, 0, 0.5],
     [0.5, 0, 0, 0, 0.5],
     [0, 0, 0, 0, 1],
     [0, 0, 0, 1, 0]]

My argument is that the communication class [0, 1, 2] is transient and therefore can be ignored, so that the period of this mc should be determined by that of the recurrent class [3, 4] which is 2. So this mc is periodic.

What about the digraph defined by the above matrix? In a digraph there is no concept of transience, so [0, 1, 2] should not be ignored. Then, if the period of a digraph is defined to be the greatest common divisor of the lengths of all cycles, then it is 1 and so this digraph is aperiodic.

But actually in the DiGraph code I left the period of a non-strongly connected digraph to be undefined, to avoid different conclusions between MarkovChain and DiGraph.

[oyamad]

And what about this?

Q = [[0, 1, 0, 0, 0],
     [0, 0, 1, 0, 0],
     [1, 0, 0, 0, 0],
     [0, 0, 0, 0, 1],
     [0, 0, 0, 1, 0]]

Should the period of the Markov chain/digraph be 6, 1, or undefined?

[jstac]

OK, I remember better now. You thought about all of this very carefully.

My comment in #237 (thanks for opening a new issue) is mainly about the error, which to the casual user of the code makes it seem like the code is broken. It's not, but that's a likely impression.

What do you think about returning the string "undefined" instead?

Regarding the specific cases, I don't mind too much what convention we adopt. As you say, it's possible to make arguments from different perspectives.

(From what I saw in a quick read, for a digraph, gcd of the length of the cycles = 1 seemed like a common definition of aperiodicity, while for finite MCs, all states aperiodic seems like the standard definition of aperiodicity.)

[oyamad]

What do you think about returning the string "undefined" instead?

What if the user uses it in a script with d = g.period and accesses d? I think it is better to explicitly raise an Error. It also allows one to write

try:
    d = g.period
except NotImplementedError:
    ...

[jstac]

@oyamad I'm not sure, to be honest. I guess it felt strange that I got an error message when I requested a property. That's why it felt like the implementation was broken. It seems like if there's a property I should be able to access it without getting an error message.

So I prefer the string "undefined".

But I can see your point of view too. If you are happy with it the way it is you can close this issue.

[oyamad]

To me it seems natural that, given that it is left undefined for a reducible Markov chain, the period is not implemented and when it is accessed a NotImplementedError is explicitly raised. I am not sure which is more "pythonic" (if they are ordered in terms of the degree of "pythonicity"). I would like to hear opinions from other people.

[davidrpugh]

I think it is better to explicitly raise NotImplementedError (possibly with
custom error message explaining why the error was raised).

On Wed, Apr 13, 2016 at 2:07 PM, Daisuke Oyama notifications@github.com
wrote:

To me it seems natural that, given that it is left undefined for a
reducible Markov chain, the period is not implemented and when it is
accessed a NotImplementedError is explicitly raised. I am not sure which
is more "pythonic" (if they are ordered in terms of the degree of
"pythonicity"). I would like to hear opinions from other people.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#245 (comment)