# Markov and independent random variables

This is a part of an exercise in Durrett's probability book.

Consider the Markov chain on $\{1,2,\cdots,N\}$ with $p_{ij}=1/(i-1)$ when $j<i, p_{11}=1$ and $p_{ij}=0$ otherwise. Suppose that we start at point $k$. We let $I_j=1$ if $X_n$ visits $j$. Then $I_1,I_2,\cdots,I_{k-1}$ are independent.

I don't find it obvious that $I_1,\cdots,I_{k-1}$ are independent. It is possible to prove the independence if we calculate all $P(\cap_{j\in J\subset\{1,\cdots,k-1\}}I_j)$, but this work is long and tedious. Since the independence was written as an obvious thing in this exercise, I assume that there is an easier way.

-

Let $A_k$ denote the set of $\mathfrak a=(a_i)_{1\leqslant i\leqslant k}$ such that $a_1=a_k=1$ and $a_i$ is in $\{0,1\}$ for every $2\leqslant i\leqslant k-1$. For every $\mathfrak a$ in $A_k$, let $U(\mathfrak a)=\{2\leqslant i\leqslant k\mid a_i=1\}$. Then $$\mathrm P((I_i)_{1\leqslant i\leqslant k}=\mathfrak a)=\prod_{u\in U(\mathfrak a)}\frac1{u-1}=\prod_{i=2}^k\frac1{(i-1)^{a_i}}.$$ The product form of the RHS ensures that $(I_i)_{1\leqslant i\leqslant k}$ is independent.

Furthermore, for every $1\leqslant i\leqslant k-1$, summing the RHS over every $\mathfrak a=(a_i)_{1\leqslant i\leqslant k}$ in $A_k$ such that $a_i=\alpha$ with $\alpha$ in $\{0,1\}$ shows that $$\mathrm P(I_i=\alpha)=\frac1{k-1}\frac1{(i-1)^{\alpha}}\prod_{2\leqslant j\leqslant k-1}^{j\ne i}\left(1+\frac1{j-1}\right)=\frac1{(i-1)^{\alpha}}\frac{i-1}i,$$ hence $\mathrm P(I_i=1)=\dfrac1i$ and $\mathrm P(I_i=0)=\dfrac{i-1}i$.

-

For any $j$, observe that $X_{3}|X_{2}=j-1,X_{1}=j$ has the same distribution as $X_{2}|X_{2} \neq j-1, X_{1}=j$. Since $X_{2}=j-1$ iif $I_{j-1}=1$, by Markovianity conclude that $I_{j-1}$ is independent of $(I_{j-2},\ldots,I_{1})$ given that $X_{1}=j$.

Let's prove by induction that $I_{j-1}$ independent of $(I_{j-2},\ldots,I_{1})$ given that $X_{1}=k$.

I) $j=k$ follows straight from the first paragraph.

II) Now assume $I_{a-1}$ independent of $(I_{a-2},\ldots,I_{1})$ for all $a \geq j+1$. Thus, $(I_{k-1},\ldots,I_{j})$ is independent of $(I_{j-1},\ldots,I_{1})$. Hence, in order to prove that $I_{j-1}$ is independent of $(I_{j-2},\ldots,I_{1})$ we can condition on $(I_{k-1}=1,\ldots,I_{j}=1)$. This is the same as conditioning on $(X_{2}=k-1,\ldots,X_{k-j+1}=j)$. By markovianity and temporal homogeneity, $(X_{k-j+2}^{\infty}|X_{k-j+1}=j,\ldots,X_{1}=k)$ is identically distributed to $(X_{2}^{\infty}|X_{1}=j)$. Using the first paragraph, we know that $I_{j-1}$ is independent of $(I_{j-1},\ldots,I_{1})$ given that $X_{1}=j$. Hence, by the equality of distributions, $I_{j-1}$ is independent of $(I_{j-2},\ldots,I_{1})$ given that $X_{1}=k$.

-
I understand now. I think you mean "Hence $I_{k-1}$ is independent of $(I_{k−2},\cdots,I_1)$". This is a very good answer! thanks. – Wei Jun 29 '12 at 17:08
Which induction? – Did Jun 29 '12 at 21:26
@did I'll try to fix this (it is very sloppy, indeed). – madprob Jun 29 '12 at 21:39
Your induction hypothesis is not clear. (By the way, I am curious to know which parts of your argument the OP got, really.) – Did Jun 30 '12 at 6:13
@did the induction hypothesis is that $I_{j-1}$ is independent of $(I_{j-2},\ldots,I_{1})$ for all $k-n \leq j < k$ – madprob Jun 30 '12 at 6:39