数理解析研究所講究録 1240 巻 2001 年 204-215

204
Random Number Generation and Dvnamical System-

Stat.istical Prop erties of Binary Sequences Generated by Oue-dimensional Maps-

Yaesutada Oohama and Tohru Kohda(大濱靖匡, 香田徹)
Faculty of Information Science and Electrical Engineering, Kyushu University(九州大学大学院システム情報科学研究院)

oohama kohda}@csce.kyushu-u.ac.jp
Thereare several attempts to generate chaotic binary Sequences by using oneapph.catiollS-, itevaluate. this papcr
statistics of
The large deviation theory for dynamical
is useful for investigating this problem.
E-mail:Abstract-.

$\mathrm{d}.\mathrm{i}_{1\mathrm{I}1\mathrm{C}11\mathrm{S}}.\cdot..\mathrm{i}_{011\mathrm{A}}1*\mathrm{I}\mathrm{l}\mathrm{l}\dot{\epsilon}\iota \mathrm{p}.\mathrm{s}..\cdot \mathrm{F}\mathrm{r}_{\wedge}\mathrm{o}\mathrm{m}$of-$\mathrm{t}110-\mathrm{s}\mathrm{t}_{\dot{\mathrm{e}}1\mathrm{I}1(}1\mathrm{p}\mathrm{o}\mathrm{i}_{11}\mathrm{t}$$\mathrm{i}_{\mathrm{S}\mathrm{u}\mathrm{c}\iota\cdot \mathrm{c}\mathrm{s}\mathrm{s}\mathrm{A}1}.\check{\gamma}\mathrm{t}0-$$\mathrm{c}11\mathrm{g}\mathrm{i}11\mathrm{c}\cdot \mathrm{c}\mathrm{r}\mathrm{i}_{1\mathrm{l}}\mathrm{g}$$\mathrm{s}\mathrm{t}\mathrm{a}\mathfrak{c}\mathrm{i}_{\mathrm{S}}\mathrm{t}\mathrm{i}\mathrm{c}\cdot \mathrm{a}1\mathrm{p}\mathrm{r}\mathrm{o}_{\mathrm{P}^{(^{\backslash }\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{s}\mathrm{a}1\mathrm{n}\mathrm{p}1\mathrm{c}\mathrm{s}\mathrm{c}^{\backslash }(1^{\mathrm{u}\mathrm{c}\mathrm{u}\iota\cdot \mathrm{c}\mathrm{s}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{u}\mathrm{i}\mathrm{t}\mathrm{e}1_{\mathrm{C}11}\mathrm{g}\mathrm{t}\mathrm{h}}}}$$\mathrm{I}_{11}$$\tau\backslash ^{r}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{m}_{1}\mathrm{J}\mathrm{t}\iota_{0}^{\mathrm{w}}\mathrm{c}\mathrm{v}\mathrm{a}1_{11}\mathrm{a}\mathrm{t}\mathrm{c}$$\mathrm{t}\mathrm{h}(^{1}$$\mathrm{C}\mathrm{h}\mathrm{a}0\mathrm{t}\mathrm{i}_{\mathrm{C}}[_{)}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}\mathrm{s}\mathrm{e}q\cdot$$.\mathrm{S}.\backslash ^{-\mathrm{s}\mathrm{t}\mathrm{e}1\mathrm{u}\mathrm{s}}$1IntroductionLet

be a closed$A$$\mathrm{i}_{11}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{v}\cdot \mathrm{a}1$$\{xt\}t=0,1.2,\cdots \mathrm{g}\mathrm{e},\mathrm{n}\mathrm{e},\mathrm{r}\mathrm{a}\mathrm{t}_{l}\mathrm{e},\mathrm{d}$

by

a1ld

$\tau$: $Aarrow A$ be a ll0lllillear lllap. A real valued sequence$\mathrm{t}_{1}\mathrm{h}\mathrm{c}\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{e},\mathrm{r}\mathrm{e}^{\tau},\mathrm{n}\mathrm{c}\mathrm{e}$equation(1)$x_{t+1}=\tau(x_{t})$

is

the

$\mathrm{p}\mathrm{e}\mathrm{r}1_{1}\mathrm{a}\mathrm{p}\mathrm{s}$object which
clisplay chaos. Thereby llsinga chaotic real$\mathrm{s}\mathrm{i}_{1\mathfrak{U}}\mathrm{p}1\mathrm{e}\mathrm{s}\mathrm{t}$$\mathrm{c}:\mathrm{a}\mathrm{n}$$\mathrm{d}\mathrm{i}\mathrm{g}\mathrm{i}\mathrm{t}_{l}\mathrm{a}1\mathrm{s}\mathrm{e},\mathrm{q}_{11}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{c}\mathrm{s}$$\mathrm{S}11\mathrm{C},\mathrm{h}$$.$$\alpha \mathrm{e}$$\mathrm{v}\mathrm{a}1_{11(^{\backslash }},\mathrm{d}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{u}\mathrm{n}\iota 1\mathrm{n}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}_{1}\mathrm{i}\mathrm{o}\mathrm{n}$systems $[1],[2]$several attenlpts to generate
apply it todigital$\mathrm{m}\mathrm{d}$$\mathrm{s}\mathrm{e},\mathrm{q}\mathrm{l}\mathrm{l}\mathrm{c}\mathrm{n}\mathrm{c}\mathrm{e}$.

$\mathrm{s}\mathrm{e},\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}$enables us to know statistic properties of sucll digitalensemble averageoflength when the system is ergodic $[3].[4]$ . On thehalld. from thcofapplications. it is llecessary tostatistical properties ofsaull)leof.
In
todeviation fromstatistics of chaotic
fillitelless of their length. The
foramicalplays anrole in discussing such problems.
$\mathrm{T}1_{1}\mathrm{e}$$\mathrm{t}\mathrm{e}\mathrm{c}\cdot \mathrm{h}_{\mathrm{I}}\dot{\mathrm{u}}\mathrm{q}\mathrm{u}\mathrm{e}$$\mathrm{a}1$$\mathrm{g}\mathrm{e}$,$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}_{1}\mathrm{e}$$\mathrm{S}\mathrm{C},q$$\mathrm{s}\mathrm{t}_{\mathrm{d}11}.\mathrm{d}\mathrm{p}\mathrm{o}\mathrm{i}_{11}\mathrm{t}$$\mathrm{o}\mathrm{t},\mathrm{h}\mathrm{e}^{\mathrm{Y}},\mathrm{r}$$\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{i}_{11}\mathrm{e}\mathrm{e}\mathrm{r}\mathrm{i}_{1\mathrm{l}}\mathrm{g}$$\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}\iota \mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}$$\mathrm{f}\mathrm{i}_{11}\mathrm{i}\mathrm{t}\mathrm{e}1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}1_{1}$$\mathrm{s}\mathrm{e}\mathrm{q}\iota \mathrm{l}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{c}\mathrm{e}\mathrm{s}$$\mathrm{t}_{l}\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{p}_{\mathrm{C}^{\backslash }},\mathrm{r}$$\mathrm{w}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{t}_{1}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{t}_{1}$$\mathrm{e},\mathrm{v}\mathrm{a}1_{11}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{t}\mathrm{h}\mathrm{c}$$\mathrm{t}_{1}\mathrm{h}\mathrm{e}$$\mathrm{S}\mathrm{C}q$$\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{i}_{11}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{c}1$$\mathrm{f}_{\Gamma \mathrm{O}\mathrm{l}}\mathrm{n}\mathrm{t}1_{1}\mathrm{e}$$\mathrm{l}\mathrm{a}\mathrm{l}\cdot \mathrm{g}\mathrm{e}$$\mathrm{s}\mathrm{y}\mathrm{s}\mathrm{t}_{1}\mathrm{e}\mathrm{m}\mathrm{s}[5]-[7]$2$\mathrm{d}\mathrm{e}\mathrm{v}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{i}_{011}\mathrm{t}1_{1}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{y}$$\mathrm{d}\mathrm{y}\mathrm{n}$$\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}_{1}\mathrm{e}\mathfrak{U}1\mathrm{t}_{1}$Chaotic Binary Sequences Generated by One-DimensionalMaps

we shalltheensional
dealt withpaper ancl themct.hod ofbinal.yllsing-dimcnsional maps. Furthermore,
we shall present a fral1lework of evaluating statistical Properties ofobtained binary seof(llengths.
notations used throughout this paper. Let $=\{0.1\}$ , a1ld let.
the set of alllellgth allddell0te the set of all finitebinstrings. Webythe string. For
the stringis empty,
by A.
It is wellthat tellt
logistic nlaps a1ld
lnaps
examples of one)
dimensional
whose. In this papcr. wc
with aCdse whell
, and
is a
defined by$\mathrm{h}_{1}$this$\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}_{011}$$\mathrm{e}\mathrm{x}\mathrm{p}1\mathrm{a}\mathrm{i}_{11}$$\mathrm{O}\mathrm{n}\mathrm{e}-\dim$$\mathrm{i}_{11}\mathrm{t}1_{1}\mathrm{i}\mathrm{s}$$\mathrm{m}\mathrm{a}\mathrm{p}$$\mathrm{g}\mathrm{c}^{\backslash },\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{a}\mathrm{t}.\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{t}_{1}\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{b}\mathrm{o}\mathrm{v}\mathrm{e}^{\iota}$$\mathrm{S}\mathbb{C}q,,$,$o\mathrm{n}\mathrm{c}$$\mathrm{t}1_{1}\mathrm{e}$$\mathrm{f}\mathrm{i}_{11}\mathrm{i}\mathrm{t}\mathrm{e}$$\mathrm{w}_{\mathrm{e}\mathrm{f}\mathrm{f}\mathrm{i}_{1\mathrm{S}\mathrm{t}_{11})\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{t}^{\mathrm{Y}}1\mathrm{a}1}},\cdot,.,\cdot$$B$$B^{n}$$\subset \mathrm{l}\mathrm{e}\mathrm{l}\mathrm{l}0\mathrm{t}\mathrm{e}$$\mathrm{b}\mathrm{i}_{11}\mathrm{a}\mathrm{r}\mathrm{y}$$\mathrm{s}\mathrm{t}_{1}\cdot \mathrm{i}_{11}\mathrm{g}\mathrm{s}\mathrm{w}\mathrm{h}\mathrm{i}\mathrm{c}\cdot \mathrm{h}$$\mathrm{h}.\mathrm{a}$$\mathrm{d}\mathrm{o}\mathrm{n}o\mathrm{t}_{\mathrm{C}^{\backslash }}$,$‘\backslash 1^{\cdot}\mathrm{y}$$\mathrm{v}\mathrm{e}$$?\iota$$b_{n\iota}b_{m+1}\cdots$$b_{n\iota}^{n}$$b_{l},$$B^{*}$$?n$ $>’\iota$$b_{m}^{n}$$\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}_{1}\mathrm{e},\mathrm{d}$$\mathrm{k}_{11\mathrm{O}\mathrm{W}11}$$\mathrm{C}\mathrm{h}\mathrm{e}\mathrm{b}\mathrm{y}\mathrm{s}1_{1}\mathrm{e}\mathrm{v}$$111\mathrm{a}\mathrm{p}\mathrm{s}_{\backslash }$$\mathrm{s}$$\mathrm{m}\mathrm{a}\mathrm{l}$$A=[\mathrm{t}1, 1]$$\mathrm{p}\iota\cdot \mathrm{o}\mathrm{p}_{\mathrm{C}1}\cdot \mathrm{t}_{1}\mathrm{i}\mathrm{c}\mathrm{s}$$\tau$$.$$\mathrm{a}\mathrm{r}\mathrm{e}$,$\mathrm{a}1^{\cdot}\mathrm{C}$$\mathrm{e}\mathrm{x}\mathrm{t},\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{y}$$\mathrm{s}\mathrm{t}_{11},\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{d}$$\mathrm{d}\mathrm{e},\mathrm{a}\mathrm{l}$$\mathrm{d}\mathrm{y}\mathrm{a}\mathrm{d}\mathrm{i}_{\mathrm{C}111}.\mathrm{a}\mathrm{p}$$2x$$\tau(x)=\{$

for $0\leq x<1/2$$2x-1$ for $1/2\leq x\leq 1$

(2)

205
Although the above case is an example of one-dimensional
maps displaying chaos, the arguments we shall develop
here will be extended to a more general case that the
map is an -ardic map. Moreover, by using some conformal transformation’ an extension to the case of Chebyshev maps is also possible. Using the following threshold
function$r$$\tau$$\sigma_{c}(x)=\{$

1for $0\leq x<c$0for $c\leq x\leq 1$ ’

(3)from thewe obtain the binary sequence. It is well known that
real-valued sequencegives adyadic expanif
sion of the real number . It is also well known thatcan be regarded as a random process Fig. 1: Generation of binary
sequences using the dyadic map
equivalent to a realization of fair coin tosses.
and the threshold function$\{\sigma_{c}(\tau^{n}(x))\}_{n=0}^{\infty}$$\{\tau^{n}(x)\}_{n=0}^{\infty}$$c=1/2_{\backslash }\{\sigma_{1/2}(\tau^{n}(x))\}_{n=0}^{\infty}$$x$$\{\sigma_{1/2}(\tau^{n}(x))\}_{n=0}^{\infty}$

Prom a theoretical as well as practical engineering point of view, we are interested in thestatistical properties of the above binary sequence for general value of . In this paper wecan be considered as a functional
shall demonstrate that the binary sequences
coin tosses.
fairof
process
process on some transfomation of the random
To examine statistical properties of the above binary sequence we consider the relativei.e.
,frequency of the letter 1 appearing in the sequence$c$$\{\sigma_{c}(\tau^{n}(x))\}_{n=0}^{\infty}$$\sigma_{c}(x)$$S_{n}^{(c)}(x)= \frac{1}{n}\sum_{k=0}^{n-1}\sigma_{c}(\tau^{k}(x))$$\sigma_{c}(\tau(x))’\cdots$$\sigma_{c}(\tau^{n}(x))$

’

’

.

(4)

By Birkhoff’s individual ergodic theorem we have$\lim_{narrow\infty}S_{n}^{(c)}(x)=\int_{A}\sigma_{c}(s)\mu(s)ds=1-c$$\mathrm{a}.\mathrm{e}$

.

$x$

(5)

,

is theis an invariant measure calculated from . When is the dyadic map,
where
$[0,
1]$
the
set
of
of
the
. The above equality means that the measureuniform distribution on
does not converge to as $narrow\infty$ is zero. Our purpose isinitial value for which
to examine the asymptotic behavior of such measure for large . To this end, let $B$ be an
arbitrary subset of $[0, 1]$ and set$\tau$$\tau$

$\mu$

$\mu$

$S_{n}^{(c)}(x)$

$c$

$n$

$D_{n}^{(c)}(B)=\{x$:$x\in A_{\backslash }S_{n}^{(c)}(x)\in B\}$We say that the sequence of the probability measuredeviation property with a rate function $I^{(c)}(y)$ , if.

$\{\mu(D_{n}(B))\}_{n=1}^{\infty}$$\lim_{narrow}\sup_{\infty}\frac{1}{n}\log\mu(D_{n}^{(c)}(B))\leq-\inf_{y\in B}I^{(c)}(y)$$\lim_{narrow}\inf_{\infty}\frac{1}{n}\log\mu(D_{n}^{(c)}(B))\geq-\inf_{y\in B}I^{(c)}(y)$

on

$A$

has the large

for closed $B$ ,for open$B$.

Roughly speaking, this means$\mu(D_{n}^{(c)}(B))\approx\exp[-nI^{(c)}(B)]$

,

(6)

206
where $I^{(c)}(B)= \inf_{y\in B}I^{(c)}(y)$ . It can be seen from (5) that the sequenceis the pseudo-random sequence approximating the binomial distribution $p_{c}=(c, 1-c)$. The
function $I^{(c)}(y)$ indicates how well the random number sequence approximates the distribution for the ffinite period
and therefore, is considered as. one of the criterion to evaluate
the quality of random numbers. It is important to know $I^{(c)}(y)$ in aclosed form.
When
the binary sequence can be regarded as stochasticauy
toarandom pr0equivalentcess of fair coin tossing.
thisis considered as a sample mean of the random
sequence ffom this stochastic process.
it foUows fromtheorem in the large
deviation theory that we obtain$\{\sigma_{c}(\tau^{n}(x))\}_{n=0}^{\infty}$$p_{c}$$n_{\backslash }$$c=1/2_{\backslash }$$\mathrm{h}$$\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{e}_{\backslash }S_{n}^{(1/2)}(\cdot)$$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{n}_{\backslash }$$\mathrm{C}\mathrm{r}\mathrm{a}\mathrm{m}\acute{\mathrm{e}}\mathrm{r}^{\backslash }\mathrm{s}$$I^{(c)}(y)=\log 2-h(y)$ ,(7)

where $h(y)=-y\log y-(1-y)\log(1-y)$ . In this paper we try to derive an explicit form of$I^{(c)}(y)$for some rational numbers .
$c$3Functional Process on Prefix bansformations

In this subsection we examine the structure of the generation of the binary sequence
for some rational number . We show that the generation of the above binary sequences
as a functional process on some transformation of the random process of$\{\sigma_{c}(\tau^{n}(x)$$)\}_{n=0}^{\infty}$$c$$\mathrm{f}\mathrm{a}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{r}.\mathrm{e}\mathrm{d}$We consider the case that the threshold value is a rational number having a finite dyadic$c$expression given by(8)$c=0.a_{1}a_{2}\cdots a_{l\backslash }$where $a_{i}\in B$ ,,and $a_{l}=1$ . Let $l=l(c)$ denote the length of the dyadic expressionof . Based on the above binary expression of , set$i=1_{\backslash }2$$\cdots\backslash l$

$c$

$c$

$s_{1}=\overline{a}_{1}$,$s_{2}=a_{1}\overline{a}_{2}$$u_{1}=a_{1\backslash }$,$u_{2}=a_{1}a_{2\prime}$(9)$u_{l}.\cdot.\cdot.\cdot=a_{1}a_{2}\cdots a_{l}u_{j}=a_{1}a_{2}\cdots a_{j\backslash },|$$\cdot$$s_{l}.\cdot.\cdot.\cdot=a_{1}a_{2}\cdots a_{l-1}\overline{a}_{l}s_{j}=a_{1}a_{2}\cdots a_{j-1}\overline{a}_{j}$,and define the subset ofproperty.

$B^{*}$

by$S=\{s_{1}.s_{2\backslash \backslash }\ldots s_{l\backslash }u_{l}\}$. The set $S$ of$B^{*}$

satisfifies the following

1. No string in $S$ is a prefix of any other string in $S$ .

2. Each string in
In general we$B^{*}$

has a prefix that belongs to $S$ .

a prefix set if it satisfifies the above two conditions. Set. The prefix set makes it possible to define the function which maps stringsinonto theirprefix $s\in S$ . We denote this map by:
andit a prefix function. Furthemore, define : $Sarrow\{0, 1\}$ by
if $b_{m}=0$ ,if $b_{m}=1$ .
$\mathrm{c}\mathrm{a}\mathrm{u}$$S\subset B^{*}$$B^{*}-\mathcal{U}$$\mathcal{U}=$$S$$\{u_{1}.u_{2\prime}\ldots u_{l-1}\}$$\beta^{(c)}$$\mathrm{u}\mathrm{n}\cdot \mathrm{q}\mathrm{u}\mathrm{e}$$\varphi$$1_{\backslash }$$\varphi(b_{1}^{m})=0$$B^{*}-\mathcal{U}arrow S$$\mathrm{c}\mathrm{a}\mathrm{u}$$\varphi(b_{1}^{m})=$

207
For example, we consider the case c $5/8$ . In this case the dyadic
resentation of c is c 0.101. In this case we have$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}$(10)$s_{1\prime}s_{2}=11u_{2}=10s3=10\acute{0}\prime u_{3}=101=0u_{1}=1,’\}$

and $S\neg-\{0_{\backslash }11,100,101\}$ . The prefix set and the function on
the set can be described with a binary tree as shown in Fig. 2.
The following theorem states that the binary sequence generated Fig. 2: An example of.
is characterized withbinary tree describingbyand onwith ffinite length
expression
dyadica
has
Theorem 1Suppose that the threshold value$l=l(c)$ . Then, for any $n\geq l-1$ and any $x\in A$ , we have$S$$\varphi$

$S$

$S$

$(\beta^{(c)}, \sigma_{1/2\prime}\tau)$$(\sigma_{c}, \tau)$$\varphi$

$S$

$c$

(11)

$\sigma_{c}(\tau^{n}(x))=\varphi(\beta^{(c)}($$\prod_{j=0}^{l-1}\sigma_{1/2}(\tau^{n+j-l+1}(x))))$

Proof: To prove (11)’ it suffices to show that for any$x\in A_{\backslash }$(12)$\sigma_{c}(\tau^{l-1}(x))=\varphi(\beta^{(c)}(\prod_{j=0}^{l-1}\sigma_{1/2}(\tau^{j}(x))))$

The above equality is merely aconsequence of a simple computation. We omit the detail.
$I^{(c)}(y)$ . To this end
Next, we investigate an explicit characterization of the rate function$\square$we defifine$\Omega_{n}^{(c)}(\theta)=\int_{A}\exp\{\theta\sum_{k=0}^{n-1}\sigma_{c}(\tau^{k}(x))\}\mu(x)\mathrm{d}x$,$q^{(c)}( \theta)=\lim_{narrow\infty}\frac{1}{n}\log\Omega_{n}^{(c)}$According to G\"artner-Ellis [8], under some regularly conditions for$I^{(c)}(y)= \sup_{\theta}\{\theta y-q^{(c)}(\theta)\}$$q^{(\mathrm{r})}(\theta)$

we have(14).

Hence, the determination problem of $I^{(c)}(y)$ results in the problem of calculating$q^{(c)}(\theta)$.

By the definition of$\Omega_{n}^{(c)}(\theta)$$\Omega_{n}^{(c)}(\theta)$

(13)

(&).

$\Omega_{n}(\theta)$

andand Theorem 1, we obtain the following another form of.

expresTheorem 2Suppose that the threshold value is a rational number having a dyadic$n\geql$, we havesion finite length $l=l(c)$ . Then, for any$c$$\Omega_{n}^{(c)}$$( \ )=\frac{1}{2^{n}}\sum_{b_{1}^{n}\in \mathcal{B}^{n}}\exp[\theta\sum_{j=1}^{r\iota-l+1}\varphi(\beta^{(c)}(b_{j}^{n}))]$

The above form is useful for computing$\Omega_{n}^{(c)}(\theta)$

.

(15)

. Set

$M_{n}^{(c)}( \theta)=\sum_{b_{1}^{n}\in \mathcal{B}^{n}}\exp[\theta\sum_{j=1}^{n-l+1}\varphi(\beta^{(c)}(b_{j}^{n}))]$$\rho^{(c)}(\theta)=\lim_{narrow\infty}\frac{1}{n}\log M_{n}^{(c)}(\theta)$.

. Thus, it suffices to examine the properties of
It is obvious thatfor the computation of the rate function$q^{(c)}(\theta)=(1/2)\rho^{(c)}(\theta)$(16)$M_{n}^{(c)}(\theta)$

208
Rate Function for Threshold Values with Finite Dyadic

4

Expression

In this section we deal with the problem of computing the rate functions for threshold valuesof some rational numbers.
arguments of the previous section it suffices to discuss thecalculation of
for the computation of the rate function.
$c$$\mathrm{R}\mathrm{o}\mathrm{m}$$M_{n}^{(c)}(\theta)$

4.1

Threshold Values with General Finite Dyadic Expression

We fifirst deal with the case that the rational number hasa general dyadic expression withfifinite length. Suppose that has the
dyadic expression given by (8) in the previous
section. Throughout this subsection we assume that the threshold value is given by (8).
Furthermore, the definition of , $u_{i}i=1\prime 2$ ,and $S$ and are the same as those in theprevious section.
, define
For
by
$c$

$c$

$\mathrm{f}\mathrm{i}\mathrm{n}\cdot \mathrm{t}\mathrm{e}$$c$$b_{1}^{m}\in\beta^{*}$$l$$\cdots$$s_{i}$$\mathcal{U}$’$M_{n.b_{1}^{m}}^{(c)}(\theta)$(17)$M_{n,b_{1}^{m}}^{(c)}( \theta)=\sum_{b_{m+1}^{\mathfrak{n}}\in B^{n-m}}\exp[\theta\sum_{j=1}^{n-l+1}\varphi(\beta^{(c)}(b_{j}^{n}))]$

In particular if
is the null string ,as above have the following properties.
$\lambda$$b_{1}^{m}$

Property 1 For any prefix set$M_{n,b_{1}^{m}}^{(c)}(\theta)$$\overline{S}\subset B_{f}^{*}$

is regarded as$M_{n}^{(c)}(\theta)$. The quantity defined

we have$M_{n}^{(c)}( \theta)=\sum_{s\in\overline{S}}M_{n,s}^{(c)}(\theta)$

.

(18)

Property 2
a)

(19)

$M_{n,s_{1}}^{(c)}(\theta)=e^{\theta\overline{a}_{1}}M_{n-1}^{(c)}(\theta)$$M_{n,s_{j}}^{(c)}$$(\ )=e^{\theta\overline{a}_{j}}M_{n-1,a_{2}^{\mathrm{j}-1}\overline{a}_{\mathrm{j}}}^{(c)}(\theta)$

for $j=2$ .

(20)

$l$
$\cdots\backslash$(21)$M_{n.u_{l}}^{(c)}(\theta)=e^{\theta}M_{n-1,a_{2}^{l}}^{(c)}(\theta)$b) For any, there exists the minirnurn integer , $0\leq i\leq m$ such that $b_{i+1}^{m}=u_{m-i}$ .
When $i=m$ , $u_{m-i}$ is regarded as the null
. Then, we have the following:$b_{1}^{m}\in B^{*}$$i$$st\sqrt.ng\lambda$$M_{n,b_{1}^{m}}^{(c)}( \theta)=\exp[\theta\sum_{j=1}^{i}\varphi(\beta^{(c)}(b_{j}^{m}))]M_{n-i,u_{m-:}}^{(c)}(\theta)$

.

(22)

The following two lemmas provide use ful fomulas for deriving recursive equations withrespect to.
$M_{n}^{(c)}(\theta)$

Lemma 1
$M_{n}^{(c)}( \theta)=(e^{\theta}+e^{\theta\overline{a}_{1}})M_{n-1}^{(c)}(\theta)-(e^{\theta}-1)\sum_{j=2}^{l}a_{j}M_{n-1,a_{2}^{j-1}\overline{a}_{\mathrm{j}}}^{(c)}(\theta)$

.

(23)

209
Proof: By Properties 1and 2-a), we have$M_{n}^{(c)}( \theta)=\sum M_{n,s_{j}}^{(c)}(\theta)+M_{n,u_{l}}^{(c)}(\theta)l$$j=1$$=e^{\theta\overline{a}_{1}}M_{n-1}^{(c)}( \theta)+\sum_{j=2}^{l}e^{\theta\overline{a}_{j}}M_{\gamma\iota-1,a_{2}^{j-1}\overline{a}_{j}}^{(c)}(\theta)+e^{\theta}M_{n-1,a_{2}^{l}}^{(c)}(\theta)$

.

(24)

We note here the following identity:$e^{\theta\overline{a}_{j}}=1+e^{\theta}-e^{a_{j}}=e^{\theta}-(e^{\theta}-1)a_{j}$

.

(25)

Substituting (25) into the second term in the right member of (24)’ we have$M_{n}^{(c)}( \theta)=e^{\theta\overline{a}_{1}}M_{n-1}^{(c)}(\theta)+e^{\theta}[\sum_{j=2}^{l}M^{(c)}(\theta)n-1,a_{2}^{j-1}\overline{a}_{j}+M_{n-1,a_{2}^{l}}^{(c)}(\theta)]$

(26)

.

$-(e^{\theta}-1)$ $\sum_{j=2}^{l}a_{j}M^{(c)}-1(\theta)n-1,a_{2}^{J}\overline{a}_{j}$becomesand$j=2$ ,
We note here that the set consisting of -sequences
aprefix set. Then’ by Property 1, the second term in the right member of (26) is equal to. Hence (23) of Lemma 1 follows.
$3_{\backslash \backslash }\ldots l$$a_{2}^{j-1}\overline{a}j\backslash$$l$$a_{2}^{l}$$\square$$e^{\theta}M_{n-1}^{(c)}(\theta)$

Lemma 2 For any $1\leq k\leq l-1$ ,$M^{(c)}( \theta)=\sum_{\dot{g}=k+1}^{l}n.a_{1}^{k}a_{j}M^{(c)}(\theta)+e^{\theta}n-1.a_{2}^{j-1}\overline{a}_{\mathrm{j}}\{\sum_{j=k+1}^{l}\overline{a}_{j}M_{n-1,a_{2}^{j-1}\overline{a}_{j}}^{(c)}(\theta)+M_{n-1,a_{2}^{l}}^{(c)}(\theta)\}$

.

(27)

Proof: By Properties 1 and 2-a), we have$M_{n,a_{1}^{k}}^{(c)}( \theta)=M_{n}^{(c)}(\theta)-\sum_{j=1}^{k}M_{n,s_{j}}^{(c)}(\theta)=\sum_{j=k+1}^{l}M_{n,s_{j}}^{(c)}(\theta)+M_{n,u_{l}}^{(c)}(\theta)$$= \sum_{j=k+1}^{l}e^{\theta\overline{a}_{j}}M^{(c)}(\theta)+e^{\theta}M_{n-1,a_{2}^{l}}^{(c)}(\theta)n-1,a_{2}^{j-1}\overline{a}_{j}$

.

(28)

Furthermore, observe the following identity$e^{\theta\overline{a}_{j}}=e^{\theta}\overline{a}_{j}+a_{j}$

(29)

.

Substituting (29) into the second term in the right member of (28), we have (27) of Lemma$\square$2.

can be written as a linear function of. Let be a threshold value whose dyadic expression has the prefix,,with theequal to the dyadic expression of . Then, if $m\leq l$ , the expression ofLemma 3 For any$M_{n-1}^{(c)}(\theta)$$\cdots$$M_{n}^{(c)}(\theta)_{\backslash }$$b_{1}^{m}\in B_{f}^{*}M_{n,b_{1}^{m}}^{(c)}(\theta)$$M_{n-m}^{(c)}(\theta)$$\tilde{c}$$M_{n,b_{1}^{m}}^{(\overline{c})}(\theta)$$c$linear combination of$M_{n}^{(\overline{c})}(\theta)$,$M_{n-1}^{(\overline{c})}(\theta)$,$\cdots$,$M_{n-m}^{(\overline{c})}(\theta)$

is the same as that of$M_{n,b_{1}^{m}}^{(c)}$210$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$

We first prove the first statement. By Property 2-b), it suffices to show that for1,C&) can be written as a linear function of,. Since

1,2, \cdots , 1 and for n$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT} 7$$\mathrm{M}\mathrm{A}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}_{\mathrm{j}}$$\ovalbox{\tt\small REJECT}$$Mn^{\ovalbox{\tt\small REJECT}}(\mathit{0})$$M\ovalbox{\tt\small REJECT}^{\ovalbox{\tt\small REJECT}}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}_{1(5?),*\mathrm{e}\mathrm{e}}$$M_{\ovalbox{\tt\small REJECT}}5\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}_{\ovalbox{\tt\small REJECT}}.(\mathrm{e})$n-y,$M_{n,u_{1}}^{(c)}(\theta)=M_{n}^{(c)}(\theta)-M_{n,s_{1}}^{(c)}(\theta)=M_{n}^{(c)}(\theta)-e^{\theta\overline{a}_{1}}M_{n-1}^{(c)}(\theta)$

Lemma 3 is true for $j=1$ . Suppose that Lemma 3 holds for some $j\geq 1$ .

(30)$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{n}_{\backslash }$$M_{n.u_{j+1}}^{(c)}(\theta)=M_{n.u_{\mathrm{j}}}^{(c)}(\theta)-M_{n,s_{j+1}}^{(c)}(\theta)=M_{n,u_{\mathrm{j}}}^{(c)}(\theta)-e^{\theta a_{j+1}}M^{(c)}(\theta)n-1,a_{2}^{j}\overline{a}_{j+1}$

we have.

(31)

which together with Property 2-b) and the induction hypothesis yields that Lemma 3 holds for
The second statement foUows ffom thatcoincides withon the set.

$j+1$ .

$\beta^{(\overline{c})}$$\beta^{(c)}$$\bigcup_{1\leq j\leq}\iota B^{j}-\mathcal{U}$$\square$Combining Lemmas 1 and 3, we obtain the following theorem.
Theorem 3 There exist some polynomial functions
that$\nu_{j}=\nu_{j}(e^{\theta}),$$\sum_{j=2}^{l}a_{j_{n-1,a_{2}^{j-1}\overline{a}_{\mathrm{j}}}}M^{(c)}(\theta)=\sum_{j=1}^{l}\nu_{j}(e^{\theta})M_{n-j}^{(c)}(\theta)$

Then, for $n\geq l$ ,$M_{n}^{(c)}(\theta)$$j=1,2_{\backslash \backslash }\ldots l$.

of$e^{\theta}$

such
(32)

satisfies a linear difference equation given by$M_{n}^{(c)}( \theta)-(e^{\theta}+e^{\theta\overline{a}_{1}})M_{n-1}^{(c)}(\theta)+(e^{\theta}-1)\sum_{j=1}^{l}\nu_{j}(e^{\theta})M_{n-j}^{(c)}(\theta)=0$

.

(33)

Let $f^{(c)}(z)$ be denoted by the chamcteristic polynomial associated with this linear
difference
equation. It has a form$f^{(c)}(z)=1-(e^{\theta}+e^{\theta\overline{a}_{1}})z+(e^{\theta}-1) \sum_{j=1}^{l}\nu_{j}(e^{\theta})z^{j}$

The quantity$\rho^{-1}=(\rho^{(c)}(\theta))^{-1}$

.

(34)

is the minimum positive mot of $f^{(c)}(z)=0$ .

We can compute the characteristic polynomial $f^{(c)}(z)$ for an arbitrary prescribed thresholdvalue with fifinite dyadic expression. We shall demonstrate it for an example. Consider theprevious example in which the threshold value is given by $c=5/8=0.101$ .
this example.
we explicitly derive a linear difference equation thatsatisfies. Furthermore, we
derive an explicit parametricof the rate function. By Lemma 1, we have
$c$

$c$

$\mathrm{h}$$M_{n}^{(5/8)}(\theta)$$\mathrm{f}\mathrm{o}\mathrm{m}$$M_{n}^{(5/8)}(\theta)=(e^{\theta}+1)M_{n-1}^{(5/8)}-(e^{\theta}-1)M_{n-1,00}^{(5/8)}(\theta)$

.

(35)

By Property 2-b), we have$M_{n-1,00}^{(5/8)}(\theta)=M_{n-3}^{(5/8)}(\theta)$$\mathrm{T}\mathrm{h}\mathrm{u}\mathrm{s}_{\backslash }$

.

(36)

we obtain a recursion$M_{n}^{(5/8)}(\theta)-(e^{\theta}+1)M_{n-1}^{(5/8)}+(e^{\theta}-1)M_{n-3}^{(5/8)}(\theta)=0$

.

(37)

The corresponding characteristic polynomial is$f^{(5/8)}(z)=1-(e^{\theta}+1)z+(e^{\theta}-1)z^{3}$

(38)

211
Sinc

$\mathrm{e}$$\rho^{-1}$is the root of the above$\mathrm{p}\mathrm{o}1\mathrm{y}\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{a}1_{\backslash }$we have$e^{\theta}= \frac{\rho^{3}-\rho^{\underline{y}}-1}{\rho^{2}-1}‘$

.

(39)

is a monotone. It can easily be verifified thatWe denote the right member of (39) by$g^{-1}(z)$is an unique branch of inverse
increasing and concave function of for $\rho>1$ . Let
and is monotone$g^{-1}(z)>1$
have
we$g(z)$. Then’that satisfifies
functions ofincreasing and lower convex function of . An expression of the rate function using parameteris given by$g(\rho)$$g(\rho)$$\rho$$\rho=g^{-1}(e^{\theta})$$\rho$$\theta$$\rho$$I^{(5/8)}(y)= \sup_{\rho>1}[y\log$(40)$( \frac{\rho^{3}-\rho^{2}-1}{\rho^{2}-1})-\log(\frac{p}{2})]$

The above supreme is attained by some for which the derivative of the quantity in theabove bracket with respect to is zero. Hence we have$y$$\rho$$y[ \frac{2\rho-3\rho^{3}}{1+\rho^{2}-\rho^{3}}-\frac{-2\rho}{1-\rho^{2}}]-\frac{1}{\rho}=0$

.

(41)

Thus, we obtain the following parametric form of the rate function.
$y= \frac{1}{\rho^{2}}\cdot\frac{(\rho^{2}-1)(\rho^{3}-\rho^{2}-1)}{\rho^{3}-3\rho+4}$4.2,$I^{(5/8)}(y)=y$

tog

(42)

$( \frac{\rho^{3}-\rho^{2}-1}{\rho^{2}-1})-\log(\frac{\rho}{2})$Threshold Values with Some Periodical Finite Dyadic Expression

In this subsection we shall argue a more explicit form of the characteristic polynomials insome special case that has some periodic property. Furthermore’ we establish an explicit
characterization of the rate function in this case.
. For
Let
derate $m$ -concatenation of the binary sequence
dyadicfollowingthehavingexample $[011]^{2}01$ means 01101101. Consider the threshold value$c$$b_{1}b_{2}\cdots$$[b_{1}b_{2}\cdots b_{l}]^{m}\in B^{ml}$$b_{l}$$c$expression:(43)$c=c_{m}=0.a_{1}a_{2}\cdots a_{l-1}[0a_{1}a_{2}\cdots a_{l-1}]^{m}\tilde{l}$We assume that $al-1=1$ and the minimum period of the above binary sequence is .
Througout this subsection we always assume that the threshold value has the above dyadic
expression.
To state our results, we observe that by virtue of Lemma 3, we have
$l$

$c$

(44)

$\sum_{j=2}^{l-1}a_{j}M^{(c_{m})}(\theta)=\sum_{j=1}^{l-1}\nu_{1,j}(e^{\theta})M_{n-j}^{(c_{m})}(\theta)n-1,a_{2}^{j-1}\overline{a}_{j}\backslash$$\sum_{j=1}^{l-1}a_{j}M^{(c_{m})}(\theta)=\sum_{j=1}^{2l-1}\nu_{2,j}(e^{\theta})M_{n-j}^{(c_{m})}(\theta)n-1,a_{2}^{j+l-1}\overline{a}_{j+l}$

,

(45)

, $\cdots\prime 2l-1$ are polynomial functions of, $l-1$ andwhere. Let be a cyclic shift of binary sequences with length . Since is the minimum length of, $l-1$ do not coincide,
the period, any of thewith $ul=a1a2\cdots$ $al-10$ . This means that those $(l-1)$ -sequences are in the domain
the quantity.
of$\nu_{1,j}(e^{\theta})\prime j=1_{\backslash }2’\ldots$$\nu_{2,j}(e^{\theta})\prime j=1_{\backslash }2$$l$$e^{\theta}$

$l$

$\pi$

$(l-1)- \mathrm{s}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{s}\pi^{j}(a1a2\cdots al-10)\prime j=1$

$2_{\backslash }\cdots$$B^{*}-\mathcal{U}$$\beta^{(c_{m})}$$\mathrm{H}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}_{\backslash }$$\exp[\sum_{j=1}^{l-1}\varphi(\beta^{(c_{m})}(\pi^{j}(a_{1}a_{2}\cdots a_{l-1}0)))]$

(46)

212
is well deffined. We denote it by $K$ . Our result is as follows.
Theorem 4 Suppose that the rational number has a binary presentation given byThen, for $n\geq lm+l-1$ ,satisffies a linear difference equation given by$c$$(4\mathrm{S})$.

$M_{n}^{(c_{m})}(\theta)$$M_{n}^{(c_{m})}(\theta)=(e^{\theta}+e^{\theta\overline{a}_{1}})M_{n-1}^{(c_{m})}(\theta)$$-(e^{\theta}-1)[ \sum_{j=2}^{l-1}\nu_{1_{\dot{\theta}}}(e^{\theta})M_{n-j}^{(c_{m})}(\theta)+\sum_{i=1}^{m}\sum_{j=1}^{2l-1}e^{\theta K(\dot{*}-1)}\nu_{2,j}(e^{\theta})M_{n-(i-1)l-j}^{(c_{m})}(\theta)](47)$

Let $f^{(c_{m})}(z)$ be denoted by the characteristic polynomial associated with this linear
difference
equation. Set$f_{1}(z)=1-(e^{\theta}+e^{\theta\overline{a}_{1}})z+(e^{\theta}-1) \sum_{j=1}^{l-1}\nu_{1,j}(e^{\theta})z^{j}$,$f_{2}(z)=(e^{\theta}-1) \sum_{j=1}^{2l-1}\nu_{2,j}(e^{\theta})z^{j}$

.

(48)

Using $f1(z)$ and $f2(z)$ , $f^{(c_{m})}(z)$ is computed as$f^{(c_{m})}(z)=f_{1}(z)+ \frac{1-(e^{\theta K}z^{l})^{m}}{1-e^{\theta K_{Z}l}}\cdot f_{2}(z)$The quantity$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}$$\rho^{-1}=(\rho^{(c_{m})}(\theta))^{-1}$

.

(49)

is the minimum positive root of $f^{(c_{m})}(z)=0$ .

By Lemma 1 and the periodic property of the dyadic expression of$c_{m\prime}$

we have$M_{n}^{(c_{m})}(\theta)=(e^{\theta}+e^{\theta\overline{a}_{1}})M_{n-1}^{(c_{m})}(\theta)$$-(e^{\theta}-1)$$\{$$\sum_{j=2}^{l}a_{j}M^{(c_{m})}(\theta)n-1,a_{2}^{j-1}\overline{a}_{\mathrm{j}}+\sum_{\dot{l}=1j}^{m}\sum_{=1}^{l-1}a_{j}M^{(c_{m})}.(\theta)]n-1,a_{2}^{l+j-1}\overline{a}:\iota+\mathrm{j}$

.

(50)

Suppose that $aj=1$ . Using Properties 2-a) and b) and periodic property of the binarypresentation of for $i=1$, $m$ we obtain the following
$c$

.

.

$2_{\backslash }\ldots$.

$M^{(c_{m})}.(\theta)=e^{\theta K}M^{(c_{m})}\cdot(-1,a_{2}^{l+j-1}\overline{a}:l+\mathrm{j}n-l,a_{2}^{(\cdot-1)l+j-1}\overline{a}_{(:-1)l+j}\theta)=e^{\theta(i-1)K}M^{(c_{m})}(n\theta)n-(i-1)l-1,a_{2}^{l+j-1}\overline{a}_{l+\mathrm{j}}$

,

(51)

which together with (44), (45), and (50), yields (47) of Theorem 4.
Considerexample given by $l=2$ . In this case $c=c_{m}=0.1[01]^{m}= \frac{2}{3}[1-2^{-2(m+1)}]$ .
Characteristic polynomial is given by$\square$$\mathrm{m}$$f^{(c_{m})}(z)=1-(e^{\theta}+1)z+(e^{\theta}-1) \frac{1-z^{2m}}{1-z^{2}}\cdot z^{3}$

Since$\rho^{-1}$

.

(52)

is the root of the above polynomial, we have$e^{\theta}= \frac{\rho^{3}-\rho^{2}-\rho+\rho^{-2m}}{\rho^{2}-2+\rho^{-2m}}$

.

(53)

By the argument quite similar to the previous example we obtain the following parmetricof the rate function.

$\mathrm{f}\mathrm{o}\mathrm{m}$$y= \frac{1}{\rho}[\frac{3\rho^{2}-2\rho+1-2m\rho^{-2m-1}}{\rho^{3}-\rho^{2}+\rho-\rho^{-2m}}-\frac{2\rho-2m\rho^{-2m-1}}{\rho^{2}-2+\rho^{-2m}}]-1\backslash$(54)$I^{(c_{m})}(y)=y\log$ $\{\frac{\rho^{3}-\rho^{2}-\rho+\rho^{-2m}}{\rho^{2}-2+\rho^{-2m}}\}-\log(\frac{\rho}{2})$213
5Rate Function for Threshold Values with Infinite Dyadic
Expression

In this section we shall argue an explicit form of the rate function for with infifinite periodical
asof
dyadic expression. Consider the threshold value that is obtained by taking a$marrow\infty$ :$c$$1\mathrm{i}_{\mathrm{I}}\mathrm{n}\mathrm{i}\mathrm{t}$$c$$c_{m}$(55)$c= \lim_{marrow\infty}c_{m}=0.a_{1}a_{2}\cdots$$a_{l-1}0a_{1}a_{2}\cdots a_{l-1}\tilde{l}\ldots$

On $|z|<e^{-(K/l)\theta}$ . the characteristic polynomial
function$f^{(c)}(z)$as$marrow\infty$$f^{(c_{m})}(z)$converges to the following rational:.

$\lim_{marrow\infty}f^{(c_{m})}(z)=f^{(c)}(z)=f_{1}(z)+\frac{f_{2}(z)}{1-e^{\theta K_{Z}l}}$(56)

Our result is as follows.
Theorem 5 Suppose that the rational number has a binary presentation given by (55).
is the minimum root of the equation $f^{(c)}(z)=0$ . This
Then, the quantity
implies that$c$$\rho^{-1}=(\rho^{(c)}(\theta))^{-1}$$I^{(c)}(y)= \lim_{marrow\infty}I^{(c_{m})}(y)$

.

(57)

The proof of Theorem 5 will be stated later.
Consider an example given by $l=2$ . In this case $c= \lim_{marrow\infty}c_{m}=0.10101\cdots=\frac{2}{3}$ . By
letting $marrow\infty$ in (54), we obtain the following parametric expression of the rate function$y= \frac{1}{\rho}[\frac{3\rho^{2}-2\rho+1}{\rho^{3}-\rho^{2}+\rho}-\frac{2\rho}{\rho^{2}-2}]-1$$I^{(2/3)}(y)=y \log\{\frac{\rho^{3}-\rho^{2}-\rho}{\rho^{2}-2}\}-\log(\frac{\rho}{2})$(58)

The remaining part of this section is devoted to the proof of Theorem 5. Consider thecase that the threshold value has the following dyadic expression:$c$$\tilde{c}_{m}=0$

It is obvious that
we haveof.aia2$\cdots a_{l-1}[0a_{1}a_{2}\ldots a_{l-1}]^{m}1\tilde{l}$$\sigma_{\tilde{c}_{m}}(x)\leq\sigma_{c}(x)\leq\sigma_{c_{m}}(x)$.

for any real number

(59)

$x$

. Then, by the defifinition$q^{(c)}(\theta)$’$\frac{1}{2}\rho^{(\tilde{c}_{m})}(\theta)\leq q^{(c)}(\theta)\leq\frac{1}{2}\rho^{(c_{m})}(\theta)$

.

(60)

Hence, to prove Theorem 5, it suffices to show that on some suitable open disc of ,converges to $f^{(c)}(z)$ as $marrow\infty$ . Before proving this, we defifine some polynomial functions.
By virtue of Lemma 3, we have
$z$

(61)

,

$\sum_{j=1}^{l-1}a_{j_{n-1,a_{2}^{j+l-1}\overline{a}_{j+l}}}M^{(\overline{c}_{m})}(\theta)=\sum_{j=1}^{2l-1}\nu_{2,j}(e^{\theta})M_{n-j}^{(\overline{c}_{m})}(\theta)$$f^{(\overline{c}_{m})}(z)$, $2l-1$ are the same as those in (45). Furthermore, again by
,
where
,
$2l-1$ andLemma 3, there exist some polynomial functions $\nu 3,j(e^{\theta}),j=1$ , 2,such that, 1 of$j=1,2$ ,$\nu_{2,j}(e^{\theta})_{\backslash }j=1,2$$\cdots$$\cdots$$\nu_{4,j}(e^{\theta})$’$e^{\theta}$$\cdots$$\sum_{j=1}^{l}\overline{a}_{j}M^{(\overline{c}_{m})}(\theta)=\sum_{j=1}^{2l}\nu_{3,j}(e^{\theta})M_{n-j}^{(\overline{c}_{m})}(\theta)n-1,a_{2}^{j+l-1}\overline{a}_{j+l}$$M_{n-1,a_{2}^{l-1}\overline{a}_{l}}^{(\overline{c}_{m})}( \theta)=\sum_{j=1}^{l}\nu_{4,j}(e^{\theta})M_{n-j}^{(\overline{c}_{m})}(\theta)$

,

(62)

.

(63)

214

$\tilde{f}_{2}(z)=\sum_{j=1}^{2l-1}\nu_{2,j}(e^{\theta})z^{j}$,$f_{3}(z)= \sum_{j=1}^{2l}\nu_{3,j}(e^{\theta})z^{j}$.

$f_{4}(z)= \sum_{j=1}^{l}\nu_{4,j}(e^{\theta})z^{j}$

.

(64)

Then. we have the following lemma.
Lemma 4$f^{(\overline{c}_{m})}(z)-f^{(c_{m})}(z)=(e^{\theta K}z^{l})^{m}\tilde{f}_{2}(z)+(e^{\theta(K+1)}z^{l})^{m}[f_{3}(z)+e^{\theta(K+1)}z^{l}f_{4}(z)]$(65)

Since Theorem 5 immediately follows from the above lemma, we omit the detail of the proofof this theorem. In the following we shall give the proof of Lemma 4.
Proof of Lemma 4: By Lemma 3, there exist some polynomial functions, $1\leq j\leq$$(m+1)l-1$ of such that$\kappa j(e^{\theta})$$e^{\theta}$$M^{(\overline{c}_{m})}n-1,a_{2}^{(m+1)l-1}\overline{a}_{(m+1)l}$$( \ )=\sum_{j=1}^{(m+1)l-1}\kappa_{j}(e^{\theta})M_{n-j}^{(\overline{c}_{m})}(\theta)$

.

(66)

Set
$\eta(z)=\sum_{j=1}^{(m+1)l-1}\kappa_{j}(e^{\theta})z^{j}$

.

(67)

Then, by Lemmas 1 and 3, we have$f^{(\overline{c}_{m})}(z)-f^{(c_{m})}(z)=\eta(z)$

.

(68)

Hence’ it suffices to examine a form of (66). By Properties 2-a) and b) and the periodic
property of the binary presentation of ’ we have the following$c\sim m$$M^{(\overline{c}_{m})}(\theta)=e^{\theta K}M_{n-l,a_{1}^{ml}}^{(\overline{c}_{m})}(\theta)n-1,a_{2}^{(m+1)l-1}\overline{a}_{(m+1)l}$

.

(69)

Applying Lemma 2 to the right member of (69) and using the periodic property of the dyadic
expression of cm, we obtain$M^{(\overline{c}_{m})}$$n-1,a_{2}^{(m+1)l-1}\overline{a}_{(m+1)l}(\theta)$$=e^{\theta K} \sum_{j=1}^{l-1}a_{j_{n-l-1,a_{2}^{ml+j-1}\overline{a}_{ml+\mathrm{j}}}}M^{(\overline{c}_{m})}(\theta)$$+e^{\theta(K+1)} \{_{j=1}\sum^{l}\overline{a}_{j}M^{(\overline{c}_{m})}n-l-1,a_{2}^{ml+\mathrm{j}-1}\overline{a}_{m\mathrm{t}+\mathrm{j}n-l-1,a_{2}^{(m+1)l}}(\theta)+M^{(\overline{c}_{m})}(\theta)\}$Using Properties 2-a) and b) and periodic property of the dyadic expression of
we obtain the following.

$\tilde{c}_{m}$

(70)
, for

$aj=1_{\backslash }$$M^{(\overline{c}_{m})}(\theta)=e^{\theta K}M^{(\overline{c}_{m})}(\theta)n-l-1,a_{2}^{ml+\mathrm{j}-1}\overline{a}_{ml+j}n-2l-1,a_{2}^{(m-1)l+\mathrm{j}-1}\overline{a}_{(m-1)1+j}$$=e^{\theta(m-1)K}M^{(\overline{c}_{m})}$$n-m\iota_{-1,a_{2}^{l+j-1}\overline{a}_{l+\dot{r}}}^{(\theta)}$

Similarly, for$aj=0_{\backslash }$

.

(71)

we obtain the following$M^{(\overline{c}_{m})}(\theta)=e^{\theta(K+1)}M^{(\overline{c}_{m})}(\theta)n-l-1,a_{2}^{ml+j-1}\overline{a}_{m}\iota+jn-2l-1,a_{2}^{(m-1)l+j-1}\overline{a}_{(m-1)l+\mathrm{j}}$$=e^{\theta(m-1)(K+1)}M_{n-ml-1,a_{2}^{l+j-1}\overline{a}_{l+f}}^{(\overline{c}_{m})}(\theta)$

.

(72)

215
Furthermore, we have$M^{(\tilde{c}_{m})}(\theta)=e_{n-2l-1,a_{2}^{ml-1}\overline{a}_{ml}}^{\theta(K+1)_{M^{(\overline{c}_{m})}}}n-l-1,a_{2}^{(m+1)l-1}a_{(m+1\rangle l}$(の$=e^{\theta m(K+1)}M_{n-(m+1)l-1,a_{2}^{l-1}\overline{a}_{l}}^{(\overline{c}_{m})}(\theta)$

Combining (70)

-

.

(73)

(73), we have$M^{(\overline{c}_{m})}(\theta)n-1,a_{2}^{(m+1)l-1}\overline{a}_{(m+1)l}$$=e^{\theta mK} \sum_{j=1}^{l-1}a_{j}M_{n-ml-1,a_{2}^{l+j-1}\overline{a}_{l+j}}^{(\tilde{c}_{m})}(\theta)$$+e^{\theta m(K+1)}\{$$\sum_{j=1}^{l}\overline{a}_{j}M^{(\overline{c}_{m})}(\theta)n-ml-1,a_{2}^{l+j-1}\overline{a}_{l+j}+e^{\theta(K+1)}M_{n-(m+1)l-1,a_{2}^{l-1}\overline{a}_{l}}^{(\overline{c}_{m})}(\theta)\}$which together with (61)-(64) and (66)-(68) yields (65) of Lemma 4.

,

(74)

$\square$

References[1] T. Kohda and A. Kakimoto, “Pseudorandom number generators and chaotic orbits inthe logistic map,” Trans. Information Processing Soc. Jpn., 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, 1993.

[3] T. Geisel and V. Fairen, “Statistical properties of chaos in Chebyshev maps,” Physics. 263-266, 1986.
Letters,$105\mathrm{A}- 6_{\backslash }\mathrm{p}\mathrm{p}$[4] T. Kohda and A. Tsuneda, “Explicit evaluations of correlation functions of Chebyshev
binary and bit sequences based on Perron-Fronbenius operator,” IEICE Trans., E77-A,
no. 11, pp. 1794-1800, 1994.

[5] Y. Oono and Y. Takahashi, “Chaos, external noise and Fredholm theory,” Prog. Theor.
Phys., vol. 63, no. 5, pp. 1804-1807, 1980.

[6] Y. Takahashi and Y. Oono, “Towards the statistical mechanics of chaos,” Prog. Theor.
Phys., vol. 71. no. 4, pp.851-854, 1984.
[7] Y. Oono, “Large deviation and statistical’$\mathrm{p}\mathrm{h}\mathrm{y}\mathrm{s}\mathrm{i}\mathrm{c}\mathrm{s},\backslash$Prog. Theor. Phys. Suppl., no. 99,

pp.165-205, 1989.
[8] J. A. Bucklew, Large Deviation Techniques in Decision, Simulation, and Estimation.

John Wiley&Sons, 1990.