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 ?
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}