Let $X_0$ be a random variable with values in a countable set $I$. Let $Y_1,Y_2,\ldots$ be a sequence of independent random variables, uniformly distributed on $[0,1]$. Suppose we are given a function

$$G\colon I\times [0,1]\rightarrow I$$

and define inductively $$X_{n+1}=G(X_n,Y_{n+1})$$.

I want to show that $(X_n)_{n\ge 0}$ is a Markov Chain. In other words I want to show that $\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)=\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_n=i_n)$ and that $\mathbb{P}(X_0=i_0)=\lambda_i$ for some $\lambda_i\in \lambda$ (distribution).

we see that

\begin{align} \mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)&=\mathbb{P}(G(X_n,Y_{n+1})=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)\\ &=\mathbb{P}(G(X_n,Y_{n+1})=i_{n+1}\,|\,X_n=i_n)\\ &=\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_n=i_n). \qquad\qquad\qquad\text{(1)} \end{align} I think that the equality above is true because $X_n$ is given and $Y_j$ for all $j$ is independent. And because $X_0(\omega)\in I$ we can say that $\mathbb{P}(X_0=i_0)=\lambda_i$ with $\lambda_i\in\lambda$ (distribution i.e. $\sum_{\lambda_i\in\lambda,i\in I}{\lambda_i=1}$). So we can conclude that $(X_n)$ is Markov.

Since $(X_n)_{n\ge 0}$ is a Markov chain we can express its transition matrix in terms of $G$.

The transition matrix $P$ is defined as $P:=(p_{i,j}\colon i,j\in I)$ where $p_{i,j}=\mathbb{P}(X_{n+1}=i\,|\,X_n=j)=\mathbb{P}(G(X_n,Y_{n+1})=i\,|\,X_n=i_n)$. Therefore $P=(\mathbb{P}(G(X_n,Y_{n+1})=i\,|\,X_n=j)\colon i,j\in I).\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \text{(2)}$

So my questions are as follows:

  • Is the equality at (1) true?

  • Is (2) the only method to express the transition matrix of $(X_n)_{n\ge 0}$ in terms of $G$?

  • Can all Markov chains be realized in this way?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.