MHB Regarding mixing time of a Markov chain

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.
 
Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Back
Top