1

Let $X_1,X_2,\ldots,X_n$ be a time-homogeneous discrete-time ergodic Markov chain on a finite state space $\mathcal{S}.$ You can assume stationarity and time-reversibility as well, if you like.

Fix $s_0\in\mathcal{S}.$

Let $A=\{1\leq i\leq n-1: X_i = s_0\}.$

Conditioned on the event that $|A| = m,$ is it true that the random variables $\{X_{i+1}: i\in A\}$ are i.i.d. according to $P(X_2\in \cdot|X_1=i)$?

The answer is NO because, for instance if $m = n-1,$ then we know that $X_{i+1}$ for $i\in A$ is mostly equal to $s_0,$ except perhaps for when $i=n-1.$ $\{m = n-1\}$ may be a rare event, but under its occurrence, the statement is false.

Yet it appears that something like this must be morally true, intuitively speaking. Is there a quantitative version of this intuition? For instance, if $m$ is much smaller than $n-1,$ can we say that $\{X_{i+1}: i\in A\}$ are in some sense close to i.i.d. according to $P(X_2\in \cdot|X_1=i)$ or at least that their relative proportions are close to the multinomial distribution with probabilities $P(X_2\in \cdot|X_1=i)$?

Hedonist
  • 1,401
  • 2
    what does this $P(X_2\in \cdot|X_1=i)$ mean? – Nikos M. Sep 09 '15 at 00:53
  • 1
    It's the Markov transition probability, the conditional law of $X_2$ given $X_1=i.$ As the chain is time-homogeneous, the conditional law of $X_{j+1}$ given $X_j$ is the same for all $j.$ Actually, I figured out an answer to my question (though not THE answer). I will post it later today, if no one else does. Thanks. – Hedonist Sep 09 '15 at 10:42
  • Sorry, I got lazy, and was not sure if anyone was interested. Just wrote up an answer. I am sure there is more to say that I don't know. I would love to hear any additional thoughts on this. – Hedonist Sep 24 '15 at 18:34

1 Answers1

0

Let $X_1,X_2,\ldots,X_n,X_{n+1}$ be a sample path of length $n+1$ drawn from the Markov chain with transition matrix $P = [P(i,j)].$ Define \begin{align*} N_{i,j} & :=|\{1\leq t\leq n: (X_t,X_{t+1}) = (i,j)\}|~, \\ N_i & :=|\{1\leq t\leq n: X_t = i\}|~. \end{align*}

Let $\mathcal{F}_t = \sigma(X_1,X_2,\ldots,X_t).$

Let $Z_{t} = 1_{X_{t-1} = i}(1_{X_{t}=j} - P(i,j))$ for $t=2,\ldots,n+1$ with $Z_1 = 0.$

Let $Y_t = \sum_{j=1}^t Z_j.$ Then, $(Y_t)$ is a martingale adapted to $\mathcal{F}_t$ with $(Z_t)$ being its martingale difference sequence. Then, the standard observation that martingale differences are uncorrelated leads to

$$\mathbb{E}Y_{n+1}^2 = \sum_{t=1}^{n+1}\mathbb{E}Z_t^2,$$

in other words

$$\mathbb{E}(N_{i,j} - N_i P(i,j))^2= \left(\mathbb{E}N_i\right) P(i,j) (1-P(i,j))~.$$

Compare this to: If $X\sim\mathrm{Bin}(n,p),$ then $\mathbb{E}(X-np)^2 = np(1-p).$

We may use Chebyshev's inequality to bound the deviation of $N_{i,j}$ from $N_i P(i,j).$

Furthermore, we can apply Freedman's inequality for martingales to get exponential tails as well. (https://projecteuclid.org/euclid.aop/1176996452)

(This is just some preliminary understanding I gathered from thinking about martingale methods. If anyone can say more about how $N_{i,j}\sim\mathrm{Bin}(N_i,P(i,j))$ is true morally in the sense of its deviation from the binomial distribution being small, I would love to know about it. Please write an additional answer.)

Hedonist
  • 1,401