# Constructing a discrete Markov chain

Klenke gives a construction for a discrete Markov chain (Section 17.2 "Discrete Markov Chains: Examples", pp. 353-354). I don't understand several points in this construction, as indicated below.

The construction

Let $\left(R_n\right)_{n\in\mathbb{N}_0}$ be an independent family of random variables, all defined on the common probability space $\left(\Omega,\mathcal{A},\mathrm{P}\right)$ and each with values in $E^E$ (where $E$ is countable) and with the property $$\left(*\right)\space\space\mathrm{P}\left[R_n\left(x\right)=y\right]=p\left(x,y\right)\space\space\mathrm{for}\space\mathrm{all}\space x,y\in E$$ where $p\in E\times E\rightarrow\left[0,1\right]$ is a stochastic matrix.

For example, choose $\left(R_{n,x}\right)_{x\in E,n\in\mathbb{N}}$ as an independent family of random variables with values in $E$ and distributions $$\left(**\right)\space\space\mathrm{P}\left[R_{n,x}=y\right]=p\left(x,y\right)\space\mathrm{for}\space\mathrm{all}\space x,y\in E\space\mathrm{and}\space n\in\mathbb{N}_0$$

Note, however, that in $\left(*\right)$ we have required neither independence of the random variables $\left(R_{n,x}\right)_{x\in E}$ nor that all $\left(R_{n,x}\right)_{n\in\mathbb{N}_0}$ have the same distribution.

For $x\in E$ define $$X_0^x=x\space\space\mathrm{and}\space\space X_n^x=R_{n,X_{n-1}^x}\space\space\mathrm{for}\space n\in\mathbb{N}$$

Finally, let $\mathrm{P}_x:=\mathcal{L}\left[X^x\right]$ be the distribution of $X^x$. Recall that this is a probability measure on the space of sequences $\left(E^{\mathbb{N}_0},\mathcal{B}\left(E\right)^{\otimes\mathbb{N}_0}\right)$.

Theorem With respect to the distribution $\left(\mathrm{P}_x\right)_{x\in E}$, the canonical process on $\left(E^{\mathbb{N}_0}, \mathcal{B}\left(E\right)^{\otimes\mathbb{N}_0}\right)$ is a Markov chain with transition matrix $p$. In particular, to any stochastic matrix $p$, there corresponds a unique discrete Markov chain (namely, the canonical process) with transition probabilities $p$.

My questions

1. Previously in the book (at the beginning of section 17.1 "Markov Chains: Definitions and Construction", p. 345), a Markov process's range set $E$ is required by definition to be a Polish space. In the construction above all that is assumed on $E$ is that it is countable. Is countability a sufficient condition for "Polishness"?
2. How does $\left(**\right)$ (which is $\mathcal{A}-\mathcal{B}\left(E\right)^{\otimes\left(E\times\mathbb{N}_0\right)}$ measurable) define a process $\left(*\right)$ (which is $\mathcal{A}-\left(\mathcal{B}\left(E\right)^{\otimes E}\right)^{\otimes\mathbb{N}_0}$ measurable)?
3. Why is $X_n^x$ a $\mathcal{A}-\mathcal{B}\left(E\right)$ measurable random object (for each $x\in E$, $n\in\mathbb{N}_0$)?
-
1) It's almost obvious that a countable discrete topological space is Polish. 2) What do you mean by $\mathcal{B}(E)^{E \times \mathbb{N}_0}$ ? Anyway, what do you have to prove in order to show that this is a random variable with values in $E^E$ ? Remember the fundamental property of the product $\sigma$-algebra : how do you prove that a function with values in a product space is measurable ? –  Ahriman Sep 3 '12 at 19:55
@Ahriman: Thank you! Your hint for my 2nd question has helped me a lot. Regarding my 1st question: as Byron mentions below, not all countable topologies are Polish. This leaves my 1st and 3rd questions open for the time being. –  Evan Aad Sep 3 '12 at 22:32
@Even Aad: I said that every countable DISCRETE topological space is Polish. Discrete means that every set is open. When one considers stochastic processes with values in a countable set, if nothing is said about its $\sigma$-algebra, then it is endowed with the discrete $\sigma$-algebra, which is the Borel $\sigma$-algebra corresponding to the discrete topology. –  Ahriman Sep 4 '12 at 7:56
@Ahriman: I see. Thanks, now it makes sense –  Evan Aad Sep 4 '12 at 8:12

1. Not every topology on a countable set is Polish. Take for instance $\mathbb{Q}$ with the Euclidean topology. This system does not admit a complete metric (cf. Dugunji, Chapter XIV, Section 4, Example 2). Hence, it is not Polish. The discrete topology (i.e the power-set) is always Polish, and it is this topology that should be stipulated here to guarantee that the stochastic matrix $p$ be a $\mathcal{B}\left(E\right)-\mathcal{B}\left(E\right)$ kernel. With this topology the Borel algebra $\mathcal{B}\left(E\right)$ is simply $\mathbb{P}E$.
2. Let $\left(\hat{R}_{n,x}\right)_{x\in E,n\in\mathbb{N}_0}$ be an independent family of random variables on $\left(\Omega, \mathcal{A}, \mathrm{P}\right)$ with values in $E$ (equipped with the Borel algebra $\mathcal{B}\left(E\right)$) and distributions $$\mathrm{P}\left[\hat{R}_{n,x}=y\right]=p\left(x,y\right)\space\mathrm{for}\space\mathrm{all}\space x,y\in E\space\mathrm{and}\space n\in\mathbb{N}_0$$ For every $n\in\mathbb{N}_0$ define $$R_n:\Omega\rightarrow E^E,\space R_n\left(\omega\right):=\left[x\in E\mapsto\hat{R}_{n,x}\left(\omega\right)\right]$$ It is by a fundamental property of product spaces that $R_n$ is $\mathcal{A}-\mathcal{B}\left(E\right)^{\otimes E}$ measurable iff for all $x\in E$, $\hat{R}_{n,x}$ is $\mathcal{A}-\mathcal{B}\left(E\right)$ measurable, which it is by assumption.
3. To prove this part it must be stipulated that $R_n$ be $\mathcal{A}-\mathcal{B}\left(E\right)^{\otimes E}$ measurable for all $n\in\mathbb{N}_0$, which is the same as stipulating that $R_{n,x}$ be $\mathcal{A}-\mathcal{B}\left(E\right)$ measurable for all $\left(n,x\right)\in\mathbb{N}_0\times E$. Now this part follows by induction on $n$ by observing that for all $B\in\mathcal{B}\left(E\right)$, $$\left\{X_{n+1}^x\in B\right\}\cap \left\{X_n^x=e\right\}=\underset{\in\mathcal{A}\space\mathrm{by}\space\mathrm{stipulation}}{\underbrace{\left\{R_{n+1, e}\in B\right\}}}\cap \underset{\in\mathcal{A}\space\mathrm{by}\space\mathrm{induction}}{\underbrace{\left\{X_n^x=e\right\}}}$$ and taking the union across $e\in E$. As an added value, the same proof can be used to show that $X_n^x\in\sigma\left(R_{0,x}, R_{1,x}, \dots, R_{n,x}\right)$. While we're at it, despite it not being immediately relevant to that which was asked above, it will prove useful for Klenke's reader to convince themselves at this point that $\sigma\left(R_n\right)=\sigma\left(R_{n,x}\space:\space x\in E\right)$.
In conclusion, to make sense of Klenke's construction we should stipulate further that $E$ be provided with the discrete topology (in which case $\mathcal{B}\left(E\right)=\mathbb{P}E$) and that $R_n$ be $\mathcal{A}-\mathcal{B}\left(E\right)^{\otimes E}$ measurable for all $n\in\mathbb{N}_0$, which is the same as stipulating that $R_{n,x}$ be $\mathcal{A}-\mathcal{B}\left(E\right)$ measurable for all $\left(n,x\right)\in\mathbb{N}_0\times E$.
Note that 1. depends on the topology. $\mathbb{Q}$ is a countable metric space that is not Polish. –  Byron Schmuland Sep 3 '12 at 22:12