1
$\begingroup$

According to Wiki: by the Ornstein isomorphism theorem, that every aperiodic and irreducible Markov chain is isomorphic to a Bernoulli scheme; The isomorphism generally requires a complicated recoding.

The question is, for a given simple Markov chain, how to find the Bernoulli scheme which is isomorphic to this Markov chain ?

For example, the Markov chain is an one dimensional binomial random walk whose next step size $S_i$ is the current distance away from origin:

$S_i = \begin{cases} &+L, &\text{probability} &=1/2, \\ &-L, &\text{probability} &=1/2 \end{cases}$

where $L$ is the current distance away from origin.

For this Markov chain, what is the the Bernoulli scheme which is isomorphic to it ? How to construct it ?

$\endgroup$
8
  • $\begingroup$ I believe the statement on the supposed consequences of the Ornstein isomorphism theorem given in the Wikipedia article on Markov chains is inaccurate. The theorem only applies to stationary processes. Your Markov chain is null recurrent, so there is no distribution on its states with respect to which it can be stationary. $\endgroup$ Aug 31, 2021 at 22:55
  • $\begingroup$ Thank you for your comment. Ornstein isomorphism theorem given in the Wikipedia article on Markov chains did NOT mention the stationary conditions, and you are right, my Markov chain is not stationary. In this case, will it still be possible to find a Bernoulli scheme which is isomorphic to this Markov chain ? $\endgroup$
    – david
    Sep 1, 2021 at 2:09
  • $\begingroup$ Yes, the fact that the statement in the Wikipedia article fails to mention stationarity is the reason why I believe it's inaccurate. I can't claim much more than a nodding acquaintance with ergodic theory, but I'm certain that the isomorphism theorem you're referring to (at least, as originally proved by Friedman and Ornstein—in the paper which you can download from here) was only given for finite-state, stationary, irreducible and aperiodic Markov chains. $\endgroup$ Sep 1, 2021 at 16:10
  • $\begingroup$ It's a corollary of the more general result, given on p.369 of the paper, that two weak Bernoulli shifts with the same entropy are isomorphic. The corollary follows from the result, given on p.393-94, that a mixing Markov shift is a weak Bernoulli shift. As defined by Friedman and Ornstein, a Markov shift is the right shift operator on the sequences in the sample space of a finite-state, stationary Markov chain, and it is known that such an operator is mixing if and only if the chain is irreducible and aperiodic. $\endgroup$ Sep 1, 2021 at 16:10
  • $\begingroup$ @ lonza leggiera, thank you again for your comment. Put my specific example of Markov chain aside, in general, can you point out some articles which have examples of constructing Bernoulli scheme which is isomorphic to a given Stationary Markov chain ? I like to learn the methods of constructing such Bernoulli scheme. $\endgroup$
    – david
    Sep 1, 2021 at 18:39

1 Answer 1

1
+50
$\begingroup$

Some general remarks

The isomorphism appearing in Ornstein's isomorphism theorem is an isomorphism between transformations on probability spaces. Two such transformations $\ T_1:\Omega_1\rightarrow\Omega_1\ $ and $\ T_2:\Omega_2\rightarrow\Omega_2\ $ are isomorphic if there are subsets $\ \tilde{\Omega}_1\ $ of $\ \Omega_1\ $ and $\ \tilde{\Omega}_2\ $ of $\ \Omega_2\ $ with $\ P_1\big(\tilde{\Omega}_1\big)=$$P_2\big(\tilde{\Omega}_2\big)=$$1\ $, $\ T_1\big(\tilde{\Omega}_1\big)\subseteq\tilde{\Omega}_1\ $,$\ T_2\big(\tilde{\Omega}_2\big)\subseteq\tilde{\Omega}_2\ $, and there is a bijective measurable mapping $\ \phi:\tilde{\Omega}_1\rightarrow\tilde{\Omega}_2\ $ such that $\ \phi(A)\ $ is measurable and $\ P_2\big(\phi(A)\big)=P_1(A)\ $ for all measurable $\ A\subseteq\tilde{\Omega}_1\ $, and $\ T_2(\phi(\omega))=$$\phi(T_1(\omega))\ $ for all $\ \omega\in\tilde{\Omega}_1\ $. This means that $\ \phi\ $ is an isomorphism of the probability spaces $\ \tilde{\Omega}_1\ $ and $\ \tilde{\Omega}_2\ $, and $\ T_1\ $ maps $\ \omega\ $ to $\ \omega_t\ $ if and only if $\ T_2\ $ maps $\ \phi\big(\omega\big)\ $ to $\ \phi\big(\omega_t\big)\ $, so the transformation $\ T_2\ $ is then a perfectly faithful "image" of the transformation $\ T_1\ $ under the isomorphism.

A Bernoulli shift is a left shift, $\ L\ $, or a right shift, $\ R\ $, on the elementary outcomes $\ \omega=\big(\dots \omega_{-n},\dots,$$\,\omega_{-1},$$\,\omega_0,$$\,\omega_1,$$\,\dots,$$\,\omega_n,\dots\big)\, $of a Bernoulli scheme, defined by \begin{align} L(\omega)_t&=\omega_{t+1}\ \text{, and}\\ R(\omega)_t&=\omega_{t-1}\ , \end{align} and a Markov shift is likewise a left or right shift on the elementary outcomes of a Markov chain. Bernoulli shifts are always measure-preserving and ergodic, and both these properties are preserved under isomorphism, as is the entropy of any measure-preserving transformation. A Markov shift can therefore only be isomorphic to a Bernoulli shift if it's measure preserving, ergodic, and has the same entropy.

Friedman and Ornstein's theorem tells us that if the underlying Markov chain is finite, then these conditions are also sufficient. A Markov shift is measure preserving if and only if the underlying Markov chain is stationary, and it's ergodic if and only if the underlying chain is aperiodic and irreducible—that is, if and only if it's mixing—, and Friedmann-Ornstein says that if a mixing Markov shift on a finite-state Markov chain and a Bernoulli shift have the same entropy, then they're isomorphic. To find a Bernoulli shift isomorphic to such a given Markov chain, therefore, all you need to do is find one with the same entropy.

Construction of an isomorphic Bernouilli shift

The entropy, in bits per unit time, of a Bernoulli shift on a scheme with $\ n\ $ symbols of probabilities $\ p_1, p_2,\dots, p_n\ $ is $\ {-}\sum_\limits{i=1}^np_i\lg p_i\ $.

If $\ P\ $ is the transition matrix of a $k$-state, aperiodic and irreducible Markov chain, and $\ \pi\ $ is its stationary-state probability mass vector $\big($satisfying $\ \pi^\top P=\pi^\top\ \big)$ then the entropy, in bits per unit time, of the Markov shift on that chain is $\ {-}\sum_\limits{i=1}^k\pi_i\sum_\limits{j=1}^kP_{ij}\lg P_{ij}\ $. The aforementioned Bernoulli shift will be isomorphic to this Markov shift, therefore, if and only if $$ \sum_\limits{i=1}^np_i\lg p_i=\sum_\limits{i=1}^k\pi_i\sum_\limits{j=1}^kP_{ij}\lg P_{ij}\ . $$

If, for example, $$ P=\pmatrix{\frac{1}{3}&\frac{2}{3}\\\frac{2}{3}&\frac{1}{3}}\ , $$ then \begin{align} \pi&=\pmatrix{\frac{1}{2}\\\frac{1}{2}}\ \text{, and}\\ \sum_\limits{i=1}^k\pi_i\sum_\limits{j=1}^kP_{ij}\lg P_{ij}&=\pmatrix{\frac{1}{2}&\frac{1}{2}}\pmatrix{\frac{1}{3}\lg\frac{1}{3}&\frac{2}{3}\lg\frac{2}{3}\\\frac{2}{3}\lg\frac{2}{3}&\frac{1}{3}\lg\frac{1}{3}}\pmatrix{1\\1}\\ &=\frac{1}{3}\lg\frac{1}{3}+\frac{2}{3}\lg\frac{2}{3}\ . \end{align} Therefore, the Bernoulli shift on a scheme with two symbols of probabilites $\ \frac{1}{3},\frac{2}{3}\ $ has the same entropy, $\ \frac{1}{3}\lg3+\frac{2}{3}\lg\frac{3}{2}\ $, as the Markov shift on the above Markov chain, and is therefore isomorphic to it.

More generally, if the rows of $\ P\ $ are all permutations of the same probability vector $\ \big(q_1,q_2,\dots,q_k\big)\ $—that is, $\ P_{ij}=q_{\sigma_i(j)}\ $ for some set of permutions $\ \sigma_1,\sigma_2,\dots,\sigma_k\ $ on the integers $\ 1,2,\dots,k\ $, then \begin{align} \pi&=\pmatrix{\frac{1}{k}\\\frac{1}{k}\\\vdots\\\frac{1}{k}}\ \text{, and}\\ \sum_\limits{i=1}^k\pi_i\sum_\limits{j=1}^kP_{ij}\lg P_{ij}&=\sum_\limits{i=1}^k\frac{1}{k}\sum_\limits{j=1}^kq_{\sigma_i(j)}\lg q_{\sigma_i(j)}\\ &=\sum_\limits{j=1}^kq_j\lg q_j\ . \end{align} In this case, therefore, the Markov shift on this Markov chain is isomorphic to the Bernoulli shift on the scheme with $\ k\ $ symbols of probabilities $\ q_1, q_2,\dots, q_k\ $.

In the general case, if $\ h={-}\sum_\limits{i=1}^k\pi_i\sum_\limits{j=1}^kP_{ij}\lg P_{ij}\ $ is the entropy of the Markov shift, then to find an isomorphic Bernoulli shift we have to find probabilites $\ p_1,p_2,\dots,p_n\ $ such that \begin{align} \sum_{i=1}^np_i&=1\ \text{, and}\\ {-}\sum_{i=1}^np_i\lg p_i&=h\ . \end{align} Now the maximum possible value of $\ {-}\sum_\limits{i=1}^np_i\lg p_i\ $ subject to the constraints $\ p_i\ge0\ $ and $\ \sum_\limits{i=1}^np_i=1\ $ is $\ \lg n\ \big($ when $\ p_i=\frac{1}{n}\ $ for all $\ i\big)$. The above equations cannot have a solution, therefore, unless $\ n\ge2^h\ $.

If $\ n=\big\lceil2^h\big\rceil\ $, however, $\ \mathcal{P}(\lambda)=\big(1-\lambda+\frac{\lambda}{n},\frac{\lambda}{n},\frac{\lambda}{n},\dots,\frac{\lambda}{n}\big)\ $, and \begin{align} \mathcal{H}(\lambda)&={-}\sum_{i=1}^n\mathcal{P}(\lambda)_i\lg\mathcal{P}(\lambda)_i\ , \end{align} then $\ \mathcal{H}\ $ is a strictly increasing function on the interval $\ [0,1]\ $, with $\ \mathcal{H}(0)=0\ $ and $\ \mathcal{H}(1)=\lg n\ge h\ $. Therefore, there is a unique $\ \lambda^*\in(0,1]\ $ such that $\ \mathcal{H}(\lambda^*)=h\ $ and the Bernoulli shift on a scheme with $\ n\ $ symbols of probabilities $\ 1-\frac{(n-1)\lambda^*}{n}, \frac{\lambda^*}{n},\frac{\lambda^*}{n},\dots,\frac{\lambda^*}{n}\ $ will be isomorphic to the Markov shift on the stationary Markov chain with transition matrix $\ P\ $.

The Markov chain with transition matrix $$ \pmatrix{\frac{1}{3}&\frac{1}{3}&\frac{1}{3}\\ 0&\frac{1}{2}&\frac{1}{2}\\ 1&0&0}\ , $$ for example, is aperiodic and irreducible with stationary state probabilites $\ \frac{3}{7},\frac{2}{7},\frac{2}{7}\ $. The entropy of the Markov shift on this chain is therefore \begin{align} h&={-}\pmatrix{\frac{3}{7}&\frac{2}{7}&\frac{2}{7}}\pmatrix{\frac{1}{3}\lg\frac{1}{3}&\frac{1}{3}\lg\frac{1}{3}&\frac{1}{3}\lg\frac{1}{3}\\ 0&\frac{1}{2}\lg\frac{1}{2}&\frac{1}{2}\lg\frac{1}{2}\\ 0&0&0}\pmatrix{1\\1\\1}\\ &=\pmatrix{\frac{3}{7}&\frac{2}{7}&\frac{2}{7}}\pmatrix{\lg3\\\lg2\\0}\\ &=\frac{3}{7}\lg3+\frac{2}{7}\lg2=\lg108^\frac{1}{7}\ . \end{align} Since $\ 2^h=108^\frac{1}{7}\approx1.95\ $, there is a Bernoulli scheme with just two symbols whose Bernoulli shift will be isomorphic to the Markov shift on the above Markov chain. If the probabilities of the symbols are taken to be $\ 1-\frac{\lambda^*}{2}, \frac{\lambda^*}{2}\ $, where $\ \lambda^*\ $ is the unique solution in the interval $\ [0,1]\ $ of the equation $$ \Big(1-\frac{\lambda}{2}\Big)\lg\Big(1-\frac{\lambda}{2}\Big)+\frac{\lambda}{2}\lg\frac{\lambda}{2}={-}\frac{\lg108}{7}\ , $$ then the resulting Bernoulli shift will be isomorphic to the Markov shift on the above Markov chain. Numerical solution of the above equation gives $$ \lambda^*\approx0.78057\ , $$ and the probabilities of the symbols for the isomorphic Bernoulli shift are therefore \begin{align} 1-\frac{\lambda^*}{2}&\approx0.6097\\ \frac{\lambda^*}{2}&\approx0.3903\ . \end{align}

$\endgroup$
12
  • $\begingroup$ @ lonza leggiera. Wow, that is a great post ! Thank you. $\endgroup$
    – david
    Sep 5, 2021 at 14:56
  • $\begingroup$ @ lonza leggiera, can you provide a link to a text book or some articles on the subject ? $\endgroup$
    – david
    Sep 6, 2021 at 22:19
  • $\begingroup$ @ lonza leggier, in the last example, should $$ h = \frac{3}{7}\lg3+\frac{4}{7}\lg2\ ? $$ $\endgroup$
    – david
    Sep 6, 2021 at 22:46
  • $\begingroup$ @ lonza leggier, in the last example, the Markov Chain has three possible states. Bernoulli scheme with just two symbols whose Bernoulli shift is isomorphic to the Markov shift on the Markov Chain. How many possible states will the Benoulli scheme have ? (I am a bit confused here). $\endgroup$
    – david
    Sep 6, 2021 at 22:55
  • $\begingroup$ As one of my previous comments indicates, I'm not very familiar with the literature on this subject. Most of what little I know about it was obtained from Patrick Billingsley's Ergodic Theory and Information. It's a very good book, and contains proofs of the ergodicity of, and the formulas for the entropies of, Bernoulli shifts and Markov shifts on finite-state, aperiodic and irreducible Markov chains. $\endgroup$ Sep 7, 2021 at 4:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .