4
$\begingroup$

Given a finite, ergodic Markov $\{X_i\}$, and two natural numbers $a>b$. Let

$$p=P\left[\forall n, \sum_{k=n}^{n+a-1} \mathbf{1}_m(X_k)\leq b\right]$$ where $\mathbf{1}_m(X_k) =1$ if $X_k=m$ and 0 otherwise.

Namely, $p$ is the probability that for any time interval of size $a$, the number of visits to state $m$ is less than or equal to $b$.

The question is the property of $p$ and how to compute it.

Obviously this questions is related to the limited distribution (which, by ergodicity, is equivalent to the stationary distribution), but I could not find the exact link, since stationary distribution talks about the limit, but here, the size of interval is finite. Moreover, I am not sure whether this type of questions has been studied. References would be appreciated. (Note: some imprecision has been corrected, according to an earlier answer.)

$\endgroup$

2 Answers 2

5
$\begingroup$

An ergodic finite Markov chain satisfies a $0-1$ law. If it is possible (i.e. probability $> 0$) to have more than $b$ visits to state $m$ in a time interval of length $a$, then with probability $1$ this will eventually happen. If it is not possible, then of course the probability is $0$.

EDIT:

Let $p_1$ be the probability, starting from state $m$, of having more than $b$ visits to state $m$ in the time interval $[0,a]$. Of course, if $p_1 = 0$, the probability of ever having more than $b$ visits to state $m$ in a time interval of length $a$ is $0$. Now suppose $p_1 > 0$. Since the Markov chain is ergodic, it will almost surely visit state $m$ infinitely many times. Let $T_1$ be the first time it visits state $m$, and $T_j$ for $j > 1$ the first time it visits state $m$ after $T_{j-1}+a$. Let $A_j$ be the event of having more than $b$ visits to state $m$ in time interval $[T_j, T_j+a]$. By the Markov property and stationarity, $A_j$ are independent, and each has probability $p_1$, so with probability $1$ infinitely many of them will occur.

$\endgroup$
2
  • $\begingroup$ I don't see any events in this question about which it would be immediately clear that they are tail. $\endgroup$
    – R W
    Jul 5, 2016 at 12:28
  • $\begingroup$ Hmm, OK, I'll reformulate my answer. $\endgroup$ Jul 5, 2016 at 16:57
3
$\begingroup$

You don't actually formulate your question, but I presume that you want to know about the probability $p=p(a,b,m)$ (strictly speaking, one has to specify the measure $P$ on the path space, but in fact it does not matter).

The answer is entirely combinatorial - the only thing one has to know about the transition probabilities is the minimal number of steps $T=T(m)$ necessary to return to the state $m$ with positive probability. Then, on one hand, in any sample path any two consecutive occurrences of $m$ will be distanced by at least $T$, and, on the other hand, by ergodicity almost every sample path will contain arbitrary long time intervals with every $T$-th state being $m$, which will give an answer to your question: this probability is either 0 or 1 depending on an explicit relationship between $a$ and $b$. For instance, if $T(m)=1$, then $p=1$ if and only if $b=a$.

By the way, if you want to talk about time intervals of length $a$, then the summation in the definition of $p$ should be from $k=n$ to $k=n+a-1$. There is also an inconsistency between your formula for $p$ (where the sum is $\le b$) and the sentence just below where you ask for the number of visits to be strictly less than $b$.

$\endgroup$
2
  • $\begingroup$ Many thanks for pointing out the mistakes in the formulation of the problem. I do not quite understand the statement "if T(m)=1, then p=1 if and only if b≤a". Say, the chain has only state m, and loop there; a=2>b=1. Obviously T(m)=1, and according to your claim, p=1, but obviously in this case, p=0 as the only sample path is m forever. $\endgroup$
    – maomao
    Jul 4, 2016 at 21:00
  • $\begingroup$ Sorry - got lost in the inequalities :) So, if $T=1$, then for any $a$ a.e. sample path contains a length $a$ interval which consists of $m$'s, so that $p=0$ for $b=0,1,\dots,a-1$ and $p=1$ for $b=1$. $\endgroup$
    – R W
    Jul 4, 2016 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.