The cover time of a Markov chain on a finite state space is the expected time until all states are visited. We show that if the cover time of a discrete-time Markov chain with rational transitions probabilities is bounded, then it is a rational number. The result is proved by relating the cover time of the original chain to the hitting time of a set in another higher dimensional chain. We also extend this result to the setting where $k\geq 1 $ independent copies of a Markov chain are run simultaneously on the same state space and the cover time is the expected time until each state has been visited by at least one copy of the chain.
翻译:在有限的状态空间上,Markov链条的覆盖时间是所有各州被访问之前的预期时间。 我们显示,如果将离散时间的Markov链条的覆盖时间与合理过渡概率相连接,那么这是一个合理数字。 将原始链条的覆盖时间与另一个更高维链中一组的撞击时间联系起来, 就能证明这一结果。 我们还将这一结果扩大到一个位置, 即Markov链条的独立副本在同一个状态空间上同时运行, 而覆盖时间是预期的时间, 直到每个国家至少得到一个链条的覆盖时间。