Let $A$ be a finite set, $\Omega = A^N$, with $N \in \mathbb{N}$ or $N = \infty$ and let $\mathcal{B}(\Omega)$ be a $\sigma$-algebra of $\Omega$. Consider $\omega \in \Omega$ such that $\omega = (x_1, x_2, \ldots ,x_N)$ and a sequence of random variables $(X_t)_{t=1,\ldots, N}$ such that $X_t(\omega) = x_t$. Assume that $(X_t)_{t=1,\ldots, N}$ is a homogeneous Markov chain with transition probability $P$ and initial probability $\mu$ such that $\mathbb{P}(X_1 = x_1, \ldots, X_k = x_k) = \mu(x_1)P(x_2|x_1)\ldots P(x_k|x_{k-1})$.

In the context of Markov decision processes, I found the following claim while reading [1]: let $R: \Omega \to \mathbb{R}$ and consider the following quantity:

$$ \mathbb{E}[R] = \sum_{\omega = (x_1, \ldots, x_N) \in \Omega} R(\omega) \mathbb{P}(X_1 = x_1, \ldots, X_N = x_N) $$ when $N$ is finite. When $N$ is infinite, the author claims that we can replace the sum above by an integral.

My question is: with respect to which measure would this integral be defined? And how is this measure related to the transition probability? I would like to understand precisely the meaning of

$$ \int_{\Omega} R(\omega) \mathbb{P}(\mathrm{d}\omega) $$ in this setting.

The probability of any trajectory is zero when $N = \infty$, so I thought about using a mapping $f: \Omega \to [0,1]$ such that $f(\omega) = \sum_{k \geq 1} x_k |A|^{-k}$, where $|A|$ is the number of elements in $A$ (that is, consider $\omega$ to be the representation in base $|A|$ of a real number between 0 and 1) and identifying a measure in $([0,1],\mathcal{B}([0,1))$ to a measure in $(\Omega,\mathcal{B}(\Omega))$. However, I do not know how to link this measure in $[0,1]$ to the transition probability of the Markov chain and whether this is a good approach.

I would also like to know how this generalizes when $A = \mathbb{R}$ instead of being finite.

Thank you for your help!

[1] Markov Decision Processes: Discrete Stochastic Dynamic Programming, by Martin L. Puterman, (section 2.1.6).

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.