1
$\begingroup$

Let $\alpha, \beta$ be independent d-states (d > 2) Markov chains with the same transition probability matrix $\pi$, and let $P(\alpha_0 =1)=P(\alpha_0 =d)= \frac{1}{2}$, $P(\beta_0 =2)=P(\beta_0 =d−1)= \frac{1}{2}$. Find ALL transition matrices $\pi$ such that $\alpha$, $\beta$ may be successfully coupled.

My attempt

I understand that successful coupling means that, starting at some point $\tau$, the processes are glued ($P(\alpha \neq \beta) = 0, t \geq \tau$). Am I right that here this means chains just have to ever intersect? Then it suffices that there exists N such that the probability of getting into one state is positive after N steps, which can be described as follows: $a_0T (\pi^T)N \pi^N b_0 > 0$. But I can't figure out answer directly in terms of matrix elements, which is required. I understand that $\pi^N > 0$ is enough, but this is too strong condition.

$\endgroup$
3
  • $\begingroup$ You don't need to have $P(\alpha \neq \beta) = 0, t \geq \tau$ but instead, there is an alternative joint process $\alpha^\prime,\beta^\prime$ for which we have $(\alpha^\prime \neq \beta^\prime) = 0, t \geq \tau$ and the marginal distributions of the joint distribution $\alpha^\prime,\beta^\prime$ equals the distributions of $\alpha$ and $\beta$. Also, often one considers $\lim_{t\to \infty}P(\alpha \neq \beta) = 0$ $\endgroup$ May 18, 2023 at 21:46
  • $\begingroup$ An example is the matrix $$\begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\\end{bmatrix}$$ for which the chains can be coupled but we have $P(\alpha \neq \beta) = 2/3 \quad \forall t>0$ $\endgroup$ May 18, 2023 at 21:50
  • $\begingroup$ Where does this problem occur? Why do you need to find all these matrices? $\endgroup$ May 18, 2023 at 21:57

1 Answer 1

0
$\begingroup$

We can describe the probabilities for the begin state as the vectors $$\mathbf{x}_0 = [0.5,0,\dots,0,0.5]$$ and $$\mathbf{y}_0 = [0,0.5,\dots,0.5,0]$$

If the proces can be coupled then these probabilities must approach each other.

Case $\exists t : \mathbf{x}_t = \mathbf{y}_t$

The probabilities for the states after some time $t$ are must be equal $\mathbf{x}_t = \mathbf{y}_t$ such that

$$ \mathbf{P}^t \mathbf{x}_0 =\mathbf{P}^t \mathbf{y}_0 $$

And also

$$\mathbf{P}\cdot \left(\mathbf{P}^{t-1} (\mathbf{x}_0-\mathbf{y}_0)\right) =\mathbf{0}$$

So a neccesary condition is that the transition matrix has a zero eigenvalue.

Case $\lim_{t\to \infty} |\mathbf{x}_t - \mathbf{y}_t| = 0$

The 'successful coupling' can mean that the distance between the two chains approaches one (if you wait long enough then the coupling occurs almost surely).

Example for a transition matrix

$$\mathbf{P} = \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\\end{bmatrix}$$

We can have the joint process $\mathbf{u}_t,\mathbf{v}_t$ that transitions according to

$$\begin{array}{c|ccccccccc} &1,1 & 2,2 & 3,3 & 1,2 & 1, 3& 2,1& 2,3 & 3,1 &3,2\\ \hline 1,1 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} &\frac{1}{3} & \frac{1}{3} &0&0&0&0\\ 2,2& \frac{1}{3} & \frac{1}{3} & \frac{1}{3}&0&0&\frac{1}{3}&\frac{1}{3}&0&0\\ 3,3& \frac{1}{3} & \frac{1}{3} & \frac{1}{3}&0&0&0&0&\frac{1}{3}&\frac{1}{3}\\ 1,2&0&0&0&\frac{1}{3}& \frac{1}{3}&0&0&0&0\\ 1,3&0&0&0&\frac{1}{3}& \frac{1}{3}&0&0&0&0\\ 2,1&0&0&0&0&0&\frac{1}{3}&\frac{1}{3}&0&0\\ 2,3&0&0&0&0&0&\frac{1}{3}&\frac{1}{3} &0&0\\ 3,1&0&0&0&0&0&0&0&\frac{1}{3}&\frac{1}{3}\\ 3,2&0&0&0&0&0&0&0&\frac{1}{3}&\frac{1}{3}\\ \end{array}$$

This will eventually end up in the states (1,1), (2,2) and (3,3) where $U_t=V_t$ while the marginal distributions of process are the same as $X_t$ and $Y_t$ if we start with $U_0 = X_0$ and $V_0 = Y_0$.

However this is not the same as $$P[U_t \neq V_t] = 0$$ instead we have $$P[U_t \neq V_t] = 0.75 \left(\frac{2}{3}\right)^t$$ we have $P[U_0 \neq V_0] = 0.75$ and every step there is a $2/3$ probability that they remain different.

So, with this interpretation of successful coupling, it occurs when either both $\alpha$ and $\beta$ have the same stationary state, or have different stationary states with equal probability, or end up in similar cyclic states at the same time.

It is not easy to express in a simple way all the matrices that fullfill such condition.

$\endgroup$
1
  • $\begingroup$ I think that first equation is not true. Because values of $\alpha$ and $\beta$ is {0, ..., n}, (not state vectors). Since $\pi^t \alpha_0$ and $\pi^t \beta_0$ have to be with positive product, not the same. $\endgroup$ May 18, 2023 at 17:07

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.