0
$\begingroup$

I am currently trying to come to grips with Markov Chains. I am confused by the nature of having a null recurrent state, which by definition is also recurrent. Say we have a Markov Chain starting at some $y\in E$ with a finite state space $E$. We know that $x$ is recurrent if and only if:

$P^{y}(\tau_{x} < \infty)=1$ where $\tau_{x}:=\inf\{n \in \mathbb N:X_{n}=x\}$ can be seen as the entry time of the Markov Chain into state $x$.

and thus $X_{n}=x$ for infinitely many $n \in \mathbb N$ and therefore the expected value of these visits to state $x$, i.e. $\mathbb E^{y}[\sum_{n \geq 0}1_{\{X_{n}=x\}}]=\infty$

Then, by definiton, this same recurrent state $x$ can be considered null recurrent if the expected mean recurrence time is infinite, i.e. $\mathbb E^{x}[\tau_{x}]=\infty$.

This seems extremely counterintuitive: null recurrence basically explains that the expected mean recurrence time to state $x$ of the Markov Chain is infinite. But since $x$ is recurrent, $X_{n}=x$ for infinitely many $n$ and $\tau_{x} < \infty$ almost surely.

In other words,

If a random variable $X$ is finite then how can its expectation $\mathbb E [X]$ be infinite?

Any explanations, and intuitions would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Apologies if I'm guessing wrong here, but it seems you're troubled by the possibility that some r.v. $R$ can be both (1) $P(R < \infty) = 1$ and yet (2) $E[R] = \infty$. In your MC context, $R$ is $\tau_x$, but my guess is that it isn't any aspect of MC that's troubling you. However, (1) and (2) together should not be troubling at all -- there are lots of r.v. on $\mathbb{N}$ with infinite expectation. $\endgroup$ – antkam May 10 at 13:08
  • $\begingroup$ @antkam Yes, that is my actual question. It seems unintuitive that a finite r.v. $X$ can still have an infinite expectation $\mathbb E [X]$ $\endgroup$ – SABOY May 10 at 18:21
3
$\begingroup$

As others have stated, there is no way for a recurrent state in a finite-state Markov chain to be null recurrent. It is possible in an infinite-state Markov chain; for example, in the simple $50$-$50$ random walk on the integers, all the states are null recurrent. (This was in saulspatz's original answer, but it was edited out.)

As to the general question of how a random variable can take on values that are finite, and yet have infinite expectation: That is indeed counter-intuitive, and yet there are undeniably examples of such random variables. One such is involved in the St Petersburg paradox. None of the potential rewards is infinite, but the expected value is.

Here's another example: Let $X$ be a discrete random variable on $\mathbb{N}$, such that

$$ P(X = k) = \frac{6}{\pi^2k^2} \qquad k \geq 1 $$

This is a probability distribution, by the Basel problem, but the expectation is

\begin{align} E(X) & = \sum_{k=1}^\infty kP(X = k) \\ & = \frac{6}{\pi^2} \sum_{k=1}^\infty \frac1k \\ & = \infty \end{align}

Strange but true!

$\endgroup$
2
$\begingroup$

I believe it is impossible to have a null-recurrent state in a finite-state Markov chain. Given a finite-state Markov chain $C$ with a recurrent state $s$, consider the chain $C'$ obtained by making $s$ absorbing. That is, the process stops once we get to $s$. Now there is a specific formula for the expected time to absorption in a finite-state absorbing Markov chain, which gives a finite value. Thus, $C$ cannot have been null-recurrent.

$\endgroup$
  • $\begingroup$ Nice example. The OP said "finite state space $E$" -- can this happen in a finite state space? I'd imagine not but cannot think of a quick proof. $\endgroup$ – antkam May 10 at 13:04
  • $\begingroup$ @antkam I overlooked that, thanks. My intuition is the same as yours; I'll have to think about a proof, though. $\endgroup$ – saulspatz May 10 at 13:07
1
$\begingroup$

The answer by @BrianTung is great, so I just wanna supplement with some observations, bringing it back to Markov Chains. Let $\tau_{xx}$ be the time, starting from state $x$, to revisit state $x$. If no revisit ever occurs, we define (for that same point) $\tau_{xx} = \infty$.

So informally, $\tau_{xx}$ takes values in $\mathbb{N} \cup \{\infty\}$. Then we can think of the difference between transient and recurrent as simply:

  • For transient state, $P(\tau_{xx} = \infty) > 0$ or in other words, $P(\tau_{xx} < \infty) = \sum_{n=1}^{\infty} P(\tau_{xx} = n) < 1$.

  • For recurrent state, $P(\tau_{xx} = \infty) = 0$ or in other words, $P(\tau_{xx} < \infty) = \sum_{n=1}^{\infty} P(\tau_{xx} = n) = 1$.

    • Note that (for some MCs) even for recurrent state, $\tau_{xx} = \infty$ is possible, i.e. it is a non-empty event. We're simply saying its prob is $0$. (This is akin to "flipping all heads" in an infinite sequence of fair independent coin flips. It is a non-empty event, i.e. possible, but with prob $0$.)

So a recurrent state simply means $\sum_{n=1}^{\infty} P(\tau_{xx} = n) = 1.$ This of course places very little restriction on the expected value $E[\tau_{xx}] = \sum_{n=1}^{\infty} \color{red}{n \times} P(\tau_{xx} = n)$, and it should be no surprise the latter summation may diverge even if the former summation sums to $1$.


I think this surprises you (and many others, especially in the form of the St Petersburg Paradox) because people expect (ha!) the "expected" value to be some kind of "typical" value, when in fact it is just a certain summation and can be completely overwhelmed by the tail.

The St Petersburg Paradox has infinity in it, and may seem like a math curiosity, but it is not. E.g. imagine you modify it a bit (e.g. with a tiny bit of depreciation, or a huge but limited bankroll), so the infinite gets shrunk to some merely huge-but-finite number, say expected payoff = \$1 billion. Now it is no longer a "math paradox", but frankly it is no less of a surprise! I mean, who would pay \$1 billion to play that game?!? The "expected value" of \$1 billion matches nobody's intuitive idea of what the word "expected" should mean.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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