search

QuantEcon / QuantEcon.py

A community based Python library for quantitative economics
https://quantecon.org/quantecon-py/
MIT License
1.94k stars 2.26k forks source link

Periodicity of DiGraph/MarkovChain #245

Open oyamad opened 8 years ago

oyamad commented 8 years ago
oyamad commented 8 years ago

1. 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.

2. 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 commented 8 years ago

3. 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 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

@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 commented 8 years ago

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 commented 8 years ago

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 https://github.com/QuantEcon/QuantEcon.py/issues/245#issuecomment-209429228