MHB Regarding mixing time of a Markov chain

AI Thread Summary
The discussion focuses on the mixing time of a Markov chain and the relationship between two independent copies of the chain. It examines the probability that the states of these copies differ after one transition, given their initial states. The participants note that this probability can be bounded by the total variation distance, which is influenced by the transition matrix and the initial distributions. There is a mention of the importance of coupling in understanding these probabilities, particularly in the context of maximal coupling. The conclusion indicates that the initial statement about bounding the probability does not hold in certain cases, such as a random walk on a complete graph.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
Let $X=X_0, X_1, X_2, \ldots$ be a Markov chain on a finite state space $S$, and let $P$ denote the transition matrix.
Assume that there is an $\varepsilon>0$ such that whenever $\mu_0$ and $\nu_o$ are point distributions on $S$ (in other words, $\mu_0$ and $\nu_0$ are Direac masses) we have
$$\|\mu_0P-\nu_0P\|_{TV}\leq \varepsilon$$

Now let $Y=Y_0, Y_1, Y_2, \ldots$ be an independent copy of $X$.

Question. What can we say about the magnitude of $P[X_1\neq Y_1|X_0=x_0, Y_0=y_0]$, where $x_0$ and $y_0$ are two different states in $S$.

I intuitively think that we should be above to bound the above quantity by $\varepsilon$ up to multiplication by an absolute constant. But I am unable to prove it.

We have that
$$P[X_1\neq Y_1|X_0=x_0, Y_0=y_0] = \sum_{x\in S}\sum_{y\in S, y\neq x}P[X_1=x, Y_1=y|X_0=x_0, Y_0=y_0]$$
which is equal to
$$\sum_{x\in S} p(x_0, x)(1-p(y_0, x))$$
but I am unable to make progress.
 
Physics news on Phys.org
Really a standard exercise/result for countable state random variables (with emphasis on markov chains) is to show, where, for notational reasons it is understood in your particular case that $X_0 = 0 $ and $Y_0 = 0$

$P[X_1\neq Y_1|X_0=x_0, Y_0=y_0] = P[X_1\neq Y_1] \geq d_{TV}(X_1,Y_1)= \|\mu_0P-\nu_0P\|_{TV}$
with $\mu := \mathbf e_0$ $\nu := \mathbf e_0$

and the inequality is reached with equality in the case of a maximal coupling. This is somewhat trivial here but useful for other couplings e.g. if $\nu_0$ was the steady state vector.

(nit: there are couple different formulations of total variation distance I am using the 1/2 L1 norm of difference between probability vectors interpretation for countable state r.v.v)

the inequality you're trying to prove 'points in the wrong way' so to speak. More context / background information is needed to make sense of what you're trying to do. E.g. if you don't know what coupling, that is a big deal and my post won't make any sense.
 
steep said:
Really a standard exercise/result for countable state random variables (with emphasis on markov chains) is to show, where, for notational reasons it is understood in your particular case that $X_0 = 0 $ and $Y_0 = 0$

$P[X_1\neq Y_1|X_0=x_0, Y_0=y_0] = P[X_1\neq Y_1] \geq d_{TV}(X_1,Y_1)= \|\mu_0P-\nu_0P\|_{TV}$
with $\mu := \mathbf e_0$ $\nu := \mathbf e_0$

and the inequality is reached with equality in the case of a maximal coupling. This is somewhat trivial here but useful for other couplings e.g. if $\nu_0$ was the steady state vector.

(nit: there are couple different formulations of total variation distance I am using the 1/2 L1 norm of difference between probability vectors interpretation for countable state r.v.v)

the inequality you're trying to prove 'points in the wrong way' so to speak. More context / background information is needed to make sense of what you're trying to do. E.g. if you don't know what coupling, that is a big deal and my post won't make any sense.

I realize now that the statement I want to prove does not hold for the random walk on a big complete graph.
 
Back
Top