1

I'm trying to appropriate myself some notions related to Markov chains (for which I'm not at all a specialist) and I have this question about the notion of "number of visits" in a certain state.

Let $(X_t)_{t \in \mathbb{N}}$ be a homogeneous Markov chain with transition matrix $(P_{i,j})$ and states ${1,2,…,n}$.

I define the number of visits to state $j$ by $$N_j = \sum_{t=0}^\infty \mathbb{1}_{X_t = j}$$

Does it make sense to define the mean number of visits to state $j$ starting from state $i$ by $v_{j,i} = \mathbb{E} (N_j \, | \, X_0=i)$ ?

In that case, is it right to write the following: $$ v_{j,i} = \mathbb{E} \left((\sum_{t=0}^\infty \mathbb{1}_{X_t = j}) \, | \, X_0=i \right) = \mathbb{E} \left( \sum_{t=0}^\infty (\mathbb{1}_{X_t = j} \, | \, X_0=i) \right) = \sum_{t=0}^\infty \mathbb{E}(\mathbb{1}_{X_t = j} \, | \, X_0=i) = \sum_{t=0}^\infty P^t_{i,j} $$

If it is, I then say that a state $j$ in recurrent if and only if $v_{j,j} = \infty$ and transient if and only if $v_{j,j} < \infty$. Am I right in using these definitions?

Thank you for any comments that would help me better understand if something is wrong...

Andrew
  • 483
  • Yes, this is correct, although I would define $\mathbb{N}={1, 2, 3, ...}$ which seems different from your implicit definition of $\mathbb{N}$. – Michael Jun 10 '22 at 21:05
  • I see... You mean I should have wrote $v_{j,i} = \mathbb{E}(\mathbb{1}{X_0=j} , | , X_0=i) + \sum{t=1}^\infty \mathbb{E}(\mathbb{1}{X_t = j} , | , X_0=i) = = \mathbb{E}(\mathbb{1}{X_0=j} , | , X_0=i) + \sum_{t=1}^\infty P^t_{i,j}$ ? In order to distinguish between $i \neq j$ and $i=j$ ? – Andrew Jun 11 '22 at 12:26
  • It is just that you wrote $(X_t){t \in \mathbb{N}}$ as your Markov chain, but I think you also want to include time $t=0$ so you could have $(X_t){t=0}^{\infty}$ as your Markov chain. – Michael Jun 11 '22 at 19:46

2 Answers2

1

The standard definition of recurrence for a state $j$ in a time-homogenous Markov chain, is that starting from $j$, the chain eventually returns to $j$ with probability 1. This is equivalent to $v_{jj}=\infty$. Indeed, if $x$ is recurrent, then after the first return, there is another one with probability 1, etc. Iterating and intersecting countably many events of probability 1, we see that assuming $j$ is recurrent, the number of returns is infinite almost surely. Conversely, if the probability of return is $q<1$, then the number of returns is a geometric variable with parameter $p=1-q$ and mean $v_{jj}=1/p$. See any standard book on Markov chains, e.g. [1] or Section 21.1 page 291 in [2]. The graduate probability textbooks by Durrett and by Billingsley also discuss this.

[1] James Robert Norris. Markov chains. Cambridge university press, 1998.

[2] Levin, David A., and Yuval Peres. Markov chains and mixing times. Vol. 107, American Mathematical Soc., 2017. PDF available at https://yuvalperes.com/markov-chains-and-mixing-times-2/

Yuval Peres
  • 21,955
0

$v_{j,j}=\infty$ is not a priori sufficient for recurrence. In principle, you could have something like $P(N_j=n \mid X_0=j) \propto 1/n^2$. In this case $j$ would not be recurrent but the mean number of visits is infinite anyway.

For a time-homogeneous chain what you want is actually true but this should be viewed as a theorem, not an immediate consequence of the definitions. One way to prove it is to prove that $P(N_j \geq n)=P(N_j \geq 1)^n$ using the strong Markov property and the time homogeneity and then use $E[N_j]=\sum_{n=1}^\infty P(N_j \geq n)=\sum_{n=1}^\infty P(N_j \geq 1)^n$, which is $\infty$ if and only if $P(N_j \geq 1)=1$.

Note that in the above I am redefining $N_j=\sum_{t=1}^\infty 1_{X_t=j}$ (ignoring time $0$). You can count the initial state as a "visit" if you want, that's just not what I wrote above.

Everything else you said makes sense/is correct.

Ian
  • 101,645
  • I am not sure if I understand: A non-absorbing state $i$ is recurrent if and only if the Green's function $G(i,i)\overset{\text{Def.}}=\mathsf E_{X_0=i}(N_i)$ is equal to $\infty$, this can be found for instance in Satz 17.34(b) of Achim Klenke, Wahrscheinlichkeitstheorie, 3. Auflage (2012). – Maximilian Janisch Jun 12 '22 at 19:36
  • 1
    @MaximilianJanisch Thanks for your comment, I rephrased. I actually haven't seen this result, does it assume time-homogeneity? – Ian Jun 12 '22 at 21:07
  • Yes it does indeed! But OP talks about "homogeneous" processes :) – Maximilian Janisch Jun 12 '22 at 22:28
  • $v_{j,j}$ is already defined as an expectation. It is not random. – Yuval Peres Jun 15 '22 at 16:05
  • @YuvalPeres Just a minor notation error. You know what I meant, but I'll fix it anyway. – Ian Jun 15 '22 at 16:14
  • Actually I don't know what you meant. Note the chain was assumed to be time-homogenous by the OP, as there is only one transition matrix. – Yuval Peres Jun 15 '22 at 16:16
  • @YuvalPeres If you read the sentence in context it is not hard to see it was supposed to be the random number of visits rather than the expected number of visits. I don't understand how this second sentence is related; did you think I meant that $v$ was a random transition matrix? If so that seems rather intentionally obtuse IMO... – Ian Jun 15 '22 at 16:17
  • Thanks for clarifying, indeed, the notational error could have been understood from context. The second sentence was also due to my initial misunderstanding of your notational error. I thought you meant to say that $v_{jj}=\infty$ is not sufficient in a non-homogenous chain. – Yuval Peres Jun 15 '22 at 16:32
  • @YuvalPeres Is it sufficient? I don't actually know. This proof certainly doesn't work. – Ian Jun 15 '22 at 16:44
  • It is not sufficient in general for chains that are not time homogenous. – Yuval Peres Jun 15 '22 at 16:47