A tricky conditional probability question on Markov chains

252 Views Asked by At

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)$?

1

There are 1 best solutions below

0
On BEST ANSWER

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.)