数理解析研究所講究録
1011 巻 1997 年 16-24

16Constructions of Piecewise Linear Maps Generating
Markov Sources
Yasutada OOHAMA and Tohru KOHDA
Graduate School of Information Science and Electrical Engineering, Kyushu University

6-10-1 Hakozaki, Higashi-ku, Fukouka 812, Japan
Tel: 092-632-4044, Fax: 092-632-5204$\mathrm{E}$1-mail:, kohda@csce.kyushu-u.ac.jp$\mathrm{o}\mathrm{o}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{a}\emptyset \mathrm{c}\mathrm{s}\mathrm{c}\mathrm{e}.\mathrm{k}\mathrm{y}\mathrm{u}\mathrm{S}\mathrm{h}\mathrm{u}-\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{j}\mathrm{P}$Introduction

Nonlinear one-dimensional maps may be the simplest object that can produce chaos. There
are several attempts to produce pseudo-random numbers by using one-dimensional maps displaying chaos. $[1]-13]$
Pseudo-random sequences generated by dynamical systems can possess statistical propertiesof Markov or hidden Markov information sources.[4] On the other hand, we can consider theinverse problem of constructing a dynamical system which has a stochastic structure of anarbitrary prescribed Markov source. In this paper we give two solutions for this problem.
Using piecewise-linear maps, we construct a dynamical system which has a structure of anarbitrary prescribed finite state Markov chain. A construction of a dynamical system having astatistical structure of an arbitrary prescribed reverse Markov source is also given.
A construction of piecewise-linear maps that realize discrete memoryless information sources
was given by
for uniform distributions andfor non-uniform distributions, respectively. It is interesting to note that the proposed constructions of Markov and Reverse
Markovcontain the results of.Kac and Kanaya, as special cases, respectively.
$\mathrm{K}\mathrm{a}\mathrm{c}^{[5]}$$\mathrm{K}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{y}\mathrm{a}^{[6]}$sourc.es2

Dynamical Systems Realizing Markov Sources

We consider a Markov chain with a state $s–\{1,2, \cdots, n\}$ . Let
be$i,j=1,2,$transition probabilities from the state $i\in S$ to the state $j\in S$ . Let] denote by thestochastic matrix that has transition probabilities
as the $(i,j)$ -element for $i,j=1,2,$.
We write anprobability distribution as
Markov source is definedby the stochastic process
produced by the triple of state space , stochastic matrix
and initial probability vector . We denote it by $\mathcal{M}(S, P,p)$ . The generic probability of astring $a_{0}a_{1N-1}\ldots a\in S^{N}$ is given by$\cdots,$ $n$$p_{ij},$$P=\lceil p_{ij}$$\cdots,$ $n$$p_{ij}$$p=[p_{1},p_{2}, \cdots , p_{n}].\mathrm{t}$$\mathrm{i},\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}$$\{X_{N}\}_{N=}\infty 0$

$P$

$p$

Prob $\{X_{0}=a_{0}, X_{1}=a_{1}, \cdots , X_{N-1}=a_{N-1}\}$$S$17(1)$\vee=p_{a0}p_{a}\mathrm{o}a1\ldots p_{a_{N2}a}-N-1^{\cdot}$

Our aim is to construct a dynamical system which is equivalent to an arbitrary prescribedMarkov source. We first define a dynamical system equivalent to a given Markov source. Let
denote the closed interval $[0,1]$ and : $Iarrow I$ be a nonlinear map. Consider the following
decomposition of :$I$$\tau$$I$$0=\triangle 0\leq\triangle_{1}\leq\triangle_{2}\leq\cdots\leq\triangle_{n}=1$.

and set$I_{k}$$=$$[\triangle_{k-1}, \triangle_{k})$$I_{n}$$=$$[\triangle_{n-1}, \triangle_{n}]$for $k=1,2,$$\cdots,$$n-1$.

Define the quantizer a by$\sigma(x)=k$for$x\in I_{k}$.

For any positive integer $N$ and any string $a_{0}a_{1N-1}\ldots a\in S^{N}$ , let $A(a_{0}a_{1}\cdots aN-1)$ denote the set
each element of which producesby the random number generator
and $\mu[a_{0}a_{1}\cdots aN-1]$ denote the measure of the set $A(a0a1\ldots aN-1)$ , that is,$x$$\{\sigma(\tau^{k}(X))\}k=0N-1$$a_{0}a_{1}\cdots a_{N-1}$$A(a0a_{1}\cdots aN-1)$$=$$\{x:\sigma(X)=a_{0},$ $\sigma(\mathcal{T}(x))--a_{1},$ $\cdots,$ $\sigma(\tau^{N-1}(X))=a_{N-1}\}$(2)$\mu[a_{0}a1\ldots aN-1]$$=$$\mu(A(a0a1^{\cdot}\cdot\iota aN-1))$.

(3)

Let
denote the dynamical system that consists of the triple of quantizer a, oneis equivalent toifdimensional map and measure . We call
$F(\sigma, \tau, \mu)$$\tau$$\mathcal{M}(S, P,p)$$\mathcal{F}(\sigma, \tau, \mu)$

$\mu$

(4)

$\mu[a_{0}a_{1}\cdots aN-1]$$=p_{a0}p_{aa}\mathrm{o}1\ldots p_{a_{N2}}-aN-1$

for any $N$ and any string3(5)$a_{0}a_{1}\cdots a_{N-1}\in’ S^{N}$

The Construction of Markov Sources by PiecewiseLinear Maps

In this section we construct a dynamical system that is equivalent to an arbitrarily prescribedMarkov source $\mathcal{M}(S, P,p)$ .
Let the decomposition of the interval $I=[0,1]$ be$\triangle_{k}=\frac{k}{n}$for $k=1,2,$$\cdots,$ $n$

18

and$\tau_{k}(x),$$k=1,2,$$\cdots,$ $n$

be the restriction of the map$\tau(x)$to subinterval$I_{k}$. Define$\tau_{k}(x),$

$k=$

by

$1,2,$ $\cdots,$ $n$$\tau_{k}(x)=p_{kl}-1(_{X}-ckl-1)+\frac{l-1}{n}$

(6)

$\}$

for

where

$c_{kl}$$c_{kl-1}\leq x\leq c_{kl}$and $l=1,2,$$\cdots$, $n,$

is defined by$c_{k0}=\underline{k-1}$,$n$$c_{kl}= \frac{1}{n}\cdot\sum_{j=1}^{l}p_{kj}+\frac{k-1}{n}$

for

$k,$

$l=1,2,$$\cdots,$ $n$

(7)

.
,7

Furthermore define

$\mu$

by
$\mu(x)d_{X}=np_{k}dx$

For the dynamical system$x\in I_{k}$(8).

constructed as above, the following theorem holds.

$F(\sigma, \tau, \mu)$Theorem 1 The dynamical systemfor$\mathcal{F}(\sigma, \tau, \mu)$is equivalent to $\mathcal{M}(S, P,p)$ .

To compute $\mu[a_{0}a1\ldots aN-1]$ , let $BV$ the set of bounded variation, and for any$f\in BV$ , define the linear operator: $BVarrow BV$ called Perron-Frobenius operator (PFoperator) by$Proof.\cdot$$\dot{P}_{\tau}$(9)$P_{\tau}(f(x))= \sum_{(y\in \mathcal{T}^{-}x)1}\frac{f(y)}{|\tau(y)|},\cdot$

By the definition of the PF-operator(10)$\int_{0}^{1}f(x)g(\tau(x))d_{X}=\int_{0}^{1}P_{\mathcal{T}}(f(x))g(x)dX$

can easily be verified. Next, let:be inverse branches ofand$k=1,2,$be indicator functions that take 1 on
and otherwise . By thedefinition (9) of -operator we have$\eta_{k}(X),$$y_{k}(x)$$I_{k}arrow I,$$k=1,2,$$\tau(x)$$\cdots,$ $n$$\cdots,$ $n$$I_{k}$$0$$\mathrm{P}\mathrm{F}$$P_{\tau}(\eta_{k}(x)\mu(x))$$= \sum_{j=1}^{n}\frac{\eta_{k}(y_{j}(x))\mu(yj(_{X}))}{|\tau’(y_{j}(_{X))}|}$$=$$\frac{np_{k}}{|\tau’(yk(X))|}$$= \sum_{j=1}^{n}npkpkj\eta j(x)$(11)

for $k=1,2\cdots,$ . Furthermore, it follows from similar calculations that$n$$P_{\mathcal{T}}( \eta_{k}(x))=\sum_{j=1}pnkj\eta j(x)$(12)19

for $k=1,2\cdots$ , . The calculation of $\mu[a_{012}aa\cdots a_{N}-1]$ by using (10), (11) and (12) yields thefollowing chain of equalities:$n$$\mu[a_{012}aa\cdots a_{N}-1]$$=$$\int_{0}^{1}\eta_{a_{0}}(x)\eta_{a_{1}}(\mathcal{T}(x))\eta_{a}2(_{\mathcal{T}^{2}}(X))$

.. .
$=$

$\int_{0}^{1}P_{\mathcal{T}}(\eta a0(x)\mu(x))\eta a_{1}(_{X)(_{\mathcal{T}}}\eta_{a}2(X))$

.. .
$=$

$\eta_{a_{N-1}}(_{T^{N2}}-(x))dX$$\int_{0}^{1}\sum_{j=0}^{l}np_{a}\mathrm{o}pa\mathrm{o}j\eta j(_{X)\eta()\eta}a_{1}Xa_{2}(\mathcal{T}(X))$

...
$=$

$\eta_{a_{N-1}}(\tau-1(_{X}N))\mu(x)d_{X}$$\eta_{a_{N-1}}(\tau^{N-2}(x))dX$$np_{a_{0}}p_{aa_{1}}0 \int_{0}^{1}\eta_{a_{1}}(X)\eta a_{2}(T(X))$

.. .
$=$

$np_{a}0p_{a0a}1 \int_{0}^{1}P_{\mathcal{T}}(\eta_{a}1(X))\eta a2(x)$

...
$=$

$\eta_{a_{N-1}}(\tau^{N-2}(x))dX$$\eta_{a_{N-1}}(\tau^{N3}-(x))dX$$np_{a_{0}}pa_{0}a_{1} \int 0x1\sum_{j=0}^{l}p_{a_{1}j}\eta j()\eta_{a}2(X)$...

$\eta_{a_{N-1}}(\tau^{N-3}(x))dX$$=$$np_{a_{0}}p_{a01}ap_{a}0a_{2} \int_{0}^{1}\eta_{a_{2}}(_{X})\cdots\eta a_{N-1}(\tau^{N3}-(x))d_{X}$$=$$np_{a0}pa \mathrm{o}a1p_{a}1a_{2}\ldots p_{a}N-2aN-1\int_{0}^{1}\eta_{a_{N-}}1(_{X)}dx$$=$$p_{a0}p_{aa}\mathrm{o}1pa1a_{2}\ldots p_{a_{N}a}-2N-1$

(13)

,

which coincides with (1).
In general any hidden Markov chain can be considered as a functional process over a certain
Markov chain. Accordingly, a dynamical system that realizes an arbitrary prescribed hidden
Markov chain can easily obtained from a dynamical system equivalent to a suitable Markovchain a certain functional process over which coincides the given hidden Markov chain.
proved that for integer $g\geq 3$ the map $\tau(x)=gx$ (mod 1) generates independently
uniformly distributed random sequence over the set of -alphabets, $\{0,1, \cdots, g-1\}$ . Our way$k=1,2,$of construction contains the result of Kac as a special case when we choice
as straight lines and $\mu(x)=1$ .
The state diagram for the Markov chain with state $S=\{1,2,3\}$ and stochastic matrix$\mathrm{K}\mathrm{a}\mathrm{c}^{[51}$$g$$\tau_{k}(x),$$P=[ \frac{1}{\frac{\not\in}{\frac{g}{4}}}$$\frac{\frac{1}{3}}{\frac,4\S}$$\frac{\frac{}{\not\in}\frac{1}{\mathrm{f}}}{2}$$\cdots,$ $n$(14)20

is shown in Fig. 1. An example of realization of this Markov chain with a piece-wise linear
map is shown in Fig. 2.

Fig. 1. The state diagram for the Markov source.

$\mathit{1}_{l}$$\mathit{1}_{2}$$\mathit{1}_{\mathit{3}}$Fig. 2. A realization of the Markov chain with a piece-wise linear map.

4

The Construction of Reverse Markov Chains by Piecewise Linear MapsConsider the state and stochastic matrix on . If the stochastic matrix is irreducible,
suchthen there exists an unique provability vector $u=[u_{1}, u_{2}, \cdots, u_{n}],$ $u_{k}>0,$ $k=1,2,$
that
(15)
$u=uP$ .
$S$

$P$

$S$

$P$

$\cdots,$ $n$

21

If the generi.C probability of any string
stochastic process
is given by$a_{0}a_{1}\cdots a_{N-1}\backslash \in S^{N}$..

$\mathrm{r}$$\{X_{N}\}_{N=}^{\infty}0$

from the source defined by theProb $\{X_{0}=a_{0}, X_{1}=a_{1}, \cdots, X_{N-1}=a_{N-1}\}$$=u_{a_{N-1}}paN-1aN-2\ldots$ pal $a0$

then we call the source$\{X_{N}\}_{N=}^{\infty}0$

,

(16)

the reverse Markov source with $(S, P)$ and denote it by.
Consider a dynamical systemwith uniform measureon the interval . In
particular, letdenote a dynamical system with uniform measure on the interval .
In this section we show that for an arbitrary prescribed reverse Markov source, wecan construct a pair of quantizer and nonlinear map so that the dynamical system
is equivalent to.
We first consider cumulative probabilities$\mathcal{M}^{*}(S, P)$$\mathcal{F}(\sigma, \tau, \mu)$

$I$

$\mu$

$F^{*}(\sigma, \tau)$

$I$

$\mu$

$\mathcal{M}^{*}(S, P)$$\sigma$$F^{*}(\sigma, \tau)$$\tau$$\mathcal{M}^{*}(S, P)$$c_{0}.=0,$

for $k=1,2,$$c_{k}.= \sum_{j=1}^{k}u_{j}$and define the decomposition of the interval $I=[0,1]$ by$k=1,2,$, define the mapby:$\tau_{k}(x)$$\cdots,$ $n$(17)$\cdots,$ $n$$k=1,2,$$\triangle_{k}=c_{k},$$\cdots,$ $n$. Next, for$I_{k}arrow I$$\tau_{k}(x)=p_{lk}^{-}1(x-c_{\iota_{-1k}}^{*)}+c_{l-1}$

(18)

$\}$

for
where

$c_{lk}^{*}$$c_{l-1k}^{*}\leq x\leq c_{lk}^{*}$For the dynamical system$\mathcal{F}^{*}(\sigma, \tau)$

Theorem 2 The dynamical systemof$\mathrm{P}\mathrm{F}$for$F^{*}(\sigma, \mathcal{T})$$l=1,2,$$\cdots,$ $n$.

(19)

$\}$

is equivalent to the reverse Markov model$\cdots,$ $n$$\mathcal{M}^{*}(S, P)$.

consider the indicator function
on otherwise. From the definition$\mu[a_{0}a_{1}\cdots aN-1]$

that take 1 on the interval-operator (9), we have, for $k=1.’ 2\cdots,$ ,, $k=1,2,$$k,$constructed as above, the following theorem holds.

Proof: To calculate the probability measure$\eta_{k}(x)$$\cdots n,$is$c_{lk}^{*}c_{0k}^{*}= \sum_{=}^{1}=j1c_{k-}lu_{j}’ pjk+c_{k-1}$.

and $l=1,2,$$I_{k}1$

and$0$$n$$P_{\tau}( \eta k(X))=\sum_{j=1}^{n}pjk\eta j(x)$.

(20)

Using the above formula and (10) we can calcuIate $\mu[a0, a_{1}\cdots aN-1]$ to verify that it coincides
with (16). Since the argument is quite similar to that of the previous section, we omit thedetail.
1
provided a construction of a dynamical system which is equivalent to an arbitrary
prescribed discrete memoryless source. Our way of construction contains that of Kanaya as a$k=1,2,$
be straight lines.
special case by letting$\mathrm{K}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{y}\mathrm{a}^{[6]}$$\tau_{k}(x),$$\cdots,$ $n$

22We consider an example that $S=\{1,2,3\}$ and stochastic matrix is the same as specified]. An(14) in the previous section. For this case the stationary probability is
example of construction of the reverse Markov source with a piecewise linear map is shown in
Fig. 3.
$P$$u=1 \frac{3}{10},$$\frac{3}{10},$$\frac{2}{5}$Fig. 3. A realization of the reverse Markov source with a piecewise linear map.

The next example is that $S=\{1,2\}$ and stochastic matrix

$P$

is

$P=$
. The state diagram for this reverse MarkovThe stationary probability for this case ismodel is shown in Fig. 4. An example of construction of the reverse Markov source with apiecewise linear map is shown in Fig. 5. It can be seen from the form of the map that thissource has the structure of hidden Markov source as shown in Fig. 6.
$u=[ \frac{2}{3}, \frac{1}{3}]$Fig. 4. The state diagram for the reverse Markov source.

23Fig. 5. A realization of the reverse Markov source with a piecewise linear map.

Fig. 6. A hidden Markov source equivalent to the reverse Markov source.

5Conclusions

We have considered the construction problem of dynamical systems that realize arbitrary
prescribed Markov (or reverse Markov) sources and provided solutions for this problem bygiving two ways of construction with piecewise linear maps. The established representations ofinformation sources by dynamical systems are useful not only for the design of pseudo-random
number generator that has prescribed statistical properties but also the design of white chaos,[7]source coding problems, model estimations for sources.
One of further researches is the construction of dynamical systems that realize a certain
wider family of information sources containing hidden Markov sources as a special case. The
linearly dependent process is one of such families of information sources. In general the genericprobability of any string emitted from the hidden Markov source can be expressed by the product of several sub-matrices of stochastic matrix.[8] On the other hand, the generic probabilityof any string emitted from the linearly dependent process can be expressed by the product ofseveral sub-matrices of the matrix whose elements are not always non-negative.[8]24

In our constructions, elements of the stochastic matrix correspond to absolute inverse valuesof the gradient of piecewise linear functions. On the other hand, in order to solve the construction problem of an arbitrary prescribed linearly dependent process, we should characterize, asparameters of a suitable dynamical system, not necessary non-negative elements appearing in
the matrix that defines the linearly dependent process.
However, this problem is very hard and no key for resolutions has not been found so far.

References[1] K. Kohda, A. Kakimoto, “Chaos and pseudo-random numbers,” Japan Journal of Information Processing, vol.27, no.3, pp.289-296, 1986.

[2] T. Kohda and A. Tsuneda, “Pseudonoise sequences by chaotic nonlinear maps and theircorrelation properties,” IEICE Trans.,E76-B,no.8,pp.855-862,l993.
[3] T. Kohda and A. Tsuneda, “Explicit evaluations of correlation functions of Chebyshev
binary and bit sequences based on Perron-Frobenius operator,” IEICE Trans., E77-B,no.11, pp.1794-1800, 1994.
[4] Y. Oohama and T. Kohda, “Statistical properties of pseudo-random numbers generated
by one-dimensional maps,” Proceedings of 17th Symposium on Information Theory and itsApplications, pp.193-196, Dec. 1994.

[5] M. Kac, Statistical Independence in Probability Analysis and Number Theory, The Mathematical Association of America, 1959.
[6] F. Kanaya, “Chaos model for stationary discrete memoryless sources and arithmetic codes,”Proceedings of 18th Symposium on Information Theory and its Applications, pp.361-364,

Oct. 1995.

[7] T. Kohda, “Indirect time series analysis of 1-D chaos and its applications to designs ofnoise generators and to evaluations of randomness of pseudorandom nunlber generator,”
Towards the Harnessing of Chaos, M. Yamaguchi (Editor), Elesevier Science, pp. 241-256,

1993.

[8] H. Ito, An Algebraic Study on Discrete Stochastic Systems, Dr. thesis, The University ofTokyo, Tokyo, 1992.