離散力学系に基づく情報源の設計に関する研究

(1)

離散力学系に基づく情報源の設計に関する研究

藤崎, 礼志

https://doi.org/10.11501/3180597

出版情報：Kyushu University, 2000, 博士（工学）, 論文博士バージョン：

権利関係：

(2)

(3)

藤崎礼志

(4)

1 6 6

779

序論

系列生成と情報源

2.1 はじめに

2.2 シフトレジスタ系列と離散力学系に基づく情報源

2.2.1 最大周期系列(\1系列) _•

2.2.2 離散力学系に基づく無記憶情報源

1

2

5 5

6840

1i 1i 1i 1i

つムqJ

定和性(CSP) . ^{. . .}

理写像に基づく無記憶情報源の構成無記憶情報源の設計

3.1 はじめに

3.2 均等分布性(EDP)と

3.3 位相共役

3.4:

Jacobi Chebvshev

3.5 まとめ

3

1 1

282

qd っd

qδ丹、UAせ

マルコフ情報源の設計はじめに .

Kahnallによるマルコフ情幸郎原の言支言十 Kahnanの写像の部分区間数の最小化

まとめ

4.1 4.2 4.3 4...1 4

3345892

4 4 4 4 4 4

3

情報源の同定について

5.1 はじめに

ヘ2 パタンの頻度の期待値と分散

3.3 観測すべきパタンの指定

3.4 マルコフ推移行列の固有多項式の係数推定とYule \\-alker方程式

5.5 議論

3.6 まとめ

5

6 33

4 1吐

5ハU9

vhd 戸川U FO Hn・u vovdva

離散力学系に基づくスペクトル拡散符号の設計

6.1 はじめに

6.2 スペクトル拡散通信システム

6.2.1 符号分割多元接続(CD\IA)

6.2.2 スペクトル拡散通信システム

6.2.3 スペクトル拡散変調および復調の原理

6.2...1 拡散符号に要求される相関特性

(5)

まとめ .

7 結論と今後の課題 80

謝辞 83

参考文献

85

付録A予想、3.1について 90

付録B定理6.2の証明 91

11

(6)

第1章序論

本章では，初めに，研究の背景，動機について述べ，次に，研究の主な成果について述べる. 最後に，本論文の構成を述べる.

デジタル通信システムにおいて，擬似乱数は特に重要な役割を果たしている. 例えば，

ストリーム暗号システムやスペクトル拡散(叩n、以1 spc、ch・11111; SS)通信システムの信頼性は，

用いられる擬似乱数がどれだけ真の乱数に近いかによって決定されると言われている. ストリーム暗号は，

{

^Oぅ1

}

^{の2値データ列と}

{

^O、1

}

の2値擬似乱数列との排他的論理和を取ることによって，データ信号を暗号化する技術であり，スペクトル拡散は，データ信号に拡散符号と呼ばれる擬似乱数を掛け合わせ，周波数帯域を広げる変調技術である. ストリーム暗号システムにおいては予測不可能な擬似乱数が必要とされ一方 ss通信システムにおいては良好な相関特性を有する擬似乱数が必要とされる.

最近，符号分割多元接続(cocle clivisioll 11lultiple access: CD:.vIA)を実現するss通信システムが携帯電話で実用化されており，そのユーザ数が幾何級数的に増大している. 同周波数帯域，同時刻におけるss通信のユーザ数の限界を与えるのはピット誤り確率である

から，ユーザ数を増大させるために，ピット誤り確率を低くするような拡散符号の設計が益々重要になってきている.

従来，拡散符号として，シフトレジスタによって生成される最大周期系列(M系列) や，非同期ss通信システムにおいて重要な統計量の一つである偶相互相関関数に関して最適な， :YI系列を基本とするKasaIni系列やGold系列が主に用いられている.

次元写像によって定義される非線形差分方程式は，カオスと呼ばれる振舞いを示す解軌道を持ち得る最も簡単な離散力学系として知られている. 近年，シフトレジスタによる系列生成とは全く異なった方法として，カオスを呈する一次元離散力学系に基づいた2値

(7)

系列を生成する試みが行なわれている. 硬貨投げや釆振りの確率モデルとして，独立同分布(illd(、pClldclltλlld ich古川iC'ally clistrihllf，ccl; i.i.cl.)確率変数がある. ある種の離散力学系が与えられたとき，その実数値解軌道を適切に2値あるいは多値化して得られる系列は，理論上， i.i.cl. 確率変数列となることが知られている. これとは逆に， i.i.cl 確率変数列など，

所望の確率過程を実現する離散力学系とその実数値解軌道を離散値化する方法とを同時に与えよ，という問題が考えられる. これを離散力学系に基づく情報源、の構成問題という.

情報源の構成問題に関する研究の起源は， Kah l lallの修士論文[1]に見られる. Kaln lêUl は V\ïCllClによる信号の予測理論を拡張し，最適な信号の推定値を求める独自の算法であるカルマン・フィルタを発明したことで有名であるが，彼は，この論文において，情報源の構成問題を考察し，離散力学系に基づくマルコフ情報源の構成問題に対する一つの解答を与えていた.

Kahllanによって成し遂げられた離散力学系に基づく情報源の構成の成功から半世紀を経ょうとしている現在，無記憶情報源の構成問題に関して， I\:ohcl aらによって，ある種の一次元離散力学系に対して，実数値解軌道から得られる系列がi.i.cl. 2値または多値確求変数列となるための十分条件が与えられ問-[3]，この種の離散力学系の有する特性や，十分条件を成立させる系列生成法が詳細に調べられている[4]. また， Oohaluaらによって，

離散力学系に基づくマルコフ情報源の構成に関する研究も行なわれており[5]，さらに，

Bar llslcyやI(anayaによって，離散力学系に基づく無記憶情報源やマルコフ情報源の構成法とデータ圧縮の方法の一つである算術符号との類似性に関する議論がなされている [6]-[8]. これらの研究を契機に， Kahnè111の修士論文が，カオスが認知される以前のカオスを呈する離散力学系の発見だけでなく，離散力学系に基づく情報源構成に関する研究の創始を示していたことが再認識された. 最近， Kahnallによるマルコフ情報源の構成法を応用

して，木情報源の構成に関する研究も行なわれている[9] .

本論文は，一次元離散力学系に基づく情報源の設計に関する研究，情報源の同定問題に関する研究，並びに，離散力学系に基づくスペクトル拡散符号の設計に関する研究をまとめたものである.

離散力学系に基づく無記憶情報源の構成に関して， [0、1]区間の実数の2進展開を定める 2進写像から一様分布i.i.cl. 2値確率変数列が得られることが，確率論の分野ではよく知られている[10]. しかしながら，区分線形の2進写像には桁落ちの問題があるため，計算機への実装が難しいという問題がある. Kohclaらによって，桁落ちの影響が少ないと思われる

(8)

多項式型のChclろでhcy写像の統計的性質が詳細に調べられ，最近，偶数次のChchy<・hcv写像を含むある種の一次元離散力学系に対して， 1個の実数値解軌道を十分精度良く計算すれば，それから得られる多数の系列がi.i.cl.

2

値確率変数列となるための十分条件が与

えられた[2]. 本論文では，

p

(ρ= 2

^.3. ・・・^;

)次Ch('hych<、γ写像を特別な場合として含む有理関数列l 写像のより広いクラスを与え，新たに導入したこの写像を用いて無記憶情報源を構成する.

方，マルコフ情報源の構成に関しては，

l\_ahn<-111が，マルコ

フ推移行列の各要素がいずれも正という条件の下で，任意の入ア状態マルコフ連鎖を実現する区分線形 (ω1)1町cα'CCW1附s肘，('一liI肘i

報j源源原原、設計の立場から， K孔叫h11は則a削仰1..1山11の結果を再考する. その結果， Kahn札口は，まず， N2個のlメ聞を有する離散力学系を構成した後，入吋固の区間を入'個とみなす，言い換えれば，粗視化することによって，八マ状態マルコフ連鎖を実現していたことを明らかにする. さらに，マルコフ推移行列の階数が入'であるとき，推移行列が..:y2一入1屈のパラメータによって決定されることに注目して， Kahllêl11の構成法を改良し，入ゴ一入+1個の最小の部分区間数を有する離散力学系による構成法を与える.

本論文では，離散力学系に基づいた系列生成について論ずるが，これに関連して，系列を生成する機構が未知であるとき，すなわち，暗箱から系列が生成されているとき，得られる系列の生成過程を確率過程と想定し，情報源を最適に推定する問題が考えられる. これを情報源の同定問題と呼ぶ. 情報源の同定問題に関して本論文では特にマルコフ情報源の同定問題を考える. 得られるN値系列をAア状態、マルコフ連鎖と想定したとき，定常マルコフ情報源はマルコフ推移行列によって完全に決定されるので，情報源を推定する方法としては，入吋固ある行列の各要素の値を推定する方法が考えられる. これに対して，本論文では，できるだけ少ない観測量で，特にXのオーダの観測量でマルコフ情報源を推定する問題を考える. マルコフ情報源から生成される系列の相関特性を決定するのは，マルコフ推移行列の固有値であることに注目する. まず，マルコフ推移行列の固有値と固有多項式の係数が有する未知数の数2JY -2と同数の観測すべき有限列パタンを指定する. 次に，固有多項式の係数が満たすべき方程式は，パタンのヒストグラムの期待値と分散を変数とする関数を係数行列とする， Ynle-\ YalkcI方程式と類似の線形方程式に帰着できることを明らかにする.

これまで，無記憶情報源から生成される系列が， ss通信システムにおける拡散符号系列の候補のーっとして考えられきた. そのため，拡散符号系列は，少なくとも次の2つの要求を満足するように設計されるのが普通であった

.

i)自己相関関数がデルタ関数的，

ii)

(9)

相互相関関数のイ直がいたるところ小. しかしながら，最近， 1\lazz iu iらによって，非同期ss通信システムにおいては，自己相関関数が指数関数的に減少する，九'状態、マルコフ連鎖から生成される系列を拡散符号として使用することが提案されており， PU1'sh、γ

に導入された平均干渉パラメータ(加でIλgc illtC1'fC1'CllC・(、 p孔l(-ll11etc、1': A1P)と呼ばれる統計量を指標としたときに最適な，すなわち， A1Pを最小化するような系列は，マルコフ情報源から得られるという報告がなされている

[

¹¹

]

. 通信の信頼性を表す重要な指標のっとして，ビット誤り確率が挙げられる. ss 通信システムにおいて，ビット誤りの原因としては，共通チャンネルにおける雑音と多元接続干渉(lllult iplc C1，C・('CSS illtC1'fc1'CllCC;

:\IA1)がある. 本論文では，まず， :-\.1P は九1:-\.1のデータ信号に関する分散を遅れ時間に関して二重に平均化した量であるため， 1\1:-\.1が原因で発生するピット誤りの生起確求を表す指標としては不十分であり，ピット誤り確率を厳密に評価するためには， 1\1:-\.1の拡散符号に関する分散で評価すべきことを指摘する. 次に， 2状態マルコフ連鎖から生成される系列に対して， :\IA1の拡散符号に関する分散を理論的に求め，ピット誤り確或て

を厳密に評価する. このとき，遅れ時間が拡散符号のパルス幅の整数倍に制限した状態を準同期状態，それ以外の状態を非同期状態と，通常いわれる非同期状態をさらに一つの状態に分けて評価しその結果，ビット誤り確率に関して準同期の場合には無記憶情報源から生成される系列が最適で、あるが，非同期の場合には:\laχZ1111らが与えたマルコフ連鎖から生成される系列が最適であることを確認する. これは非同期通信にお

けるピット誤り確率を指標としたとき，無記憶情報源から生成される2値系列が必ずしも最適でないことを意味しており，将来の拡散符号の設計に新たな視点を与えるであろう.

論文は，本章を含み， 7章から構成される. 第2章以降の構成は以下の通りである.

第2章では，シフトレジスタによる系列生成と離散か学系に基づくそれとの差異を明確にするために，まず，擬似乱数として主に用いられている，シフトレジスタによって生成さ

れるM系列について概説し次に離散力学系に基づく i.i.cl.確率安数列の生成に関してこれまで得られている結果について簡単に述べる.

第3， 4章では，離散力学系に基づく情報源の設計に関する本研究の成果を述べる. 第 3章では，無記憶情報源の設計に関する本研究の成果を述べ，第4章では，マルコフ情報

源の設計に関する本研究の成果を述べる.

第5章では，情報源の同定問題に関して，できるだけ少ない観測量でマルコフ情報源を

推定する

-方法を与える.

(10)

第6章では， 2状態マルコフ連鎖から生成される拡散符号系列を考え，非同期55通信システムにおけるI\IAIを原因とするビット誤りの生起確率を厳密に評価する.

第7章では，以上の研究のまとめと今後の課題について述べる.

(11)

第2章

系列生成と情報源

2.1 はじめに

計算機工学やデジタル通信システムにおいて，擬似乱数として，シフトレジスタによって生成される系列(シフトレジスタ系列)が主に用いられている. 本論文の第6章で議論するスペクトル拡散(spread spectrunl; SS) 通信において主に使用されている擬似乱数もシフトレジスタ系列である. また，非同期SS通信システムにおいて重要な統計量の一つである偶相互相関関数に関して最適な系列として， KasanlÏ系列やGold系列があるが，これらは最大周期系列(1\1系列)を生成する2つのシフトレジスタによって生成される.

方，シフトレジスタによる系列生成とは全く異なった方法として，カオスを呈する次元離散力学系に基づいた2値系列を生成する試みが行なわれている. 最近， Kohdaらによって，ある種の一次元離散力学系に対して，実数値解軌道から得られる系列が独立同分布(indepenclent and iclentically distributecl; i.i.cl.) 2値確率変数列となるための十分条件が与えられた[2].

本章では，シフトレジスタに基づく系列生成法と離散力学系に基づく系列生成法の差異を理解するために，前者の基本的な例として\1系列を，一方，後者の例として，離散力学系に基づく無記憶情報源について述べる.

(12)

2.2 シフトレジスタ系列と離散力学系に基づく情報源

本節では，まず，シフトレジスタ系列の基本である最大周期系列(�I系列) について概説しl，次に，前節で触れた離散力学系に基づく無記憶情報源の設計に関するKohcl孔らの結果について簡単に述べる.

2.2.1 最大周期系列(M系列)

ガロアイ本GF(2)上のρ次の多項式

f ( I) = 1

+ C1 �l、+C2I2+ - +CP17P， c-p ⁼ l

(2.1 )

を考える.

1 +.r1lという形の多項式のうちでf( .(、)で割り切れる最低次のものの次数12のことをf(x) の指数という. 指数= 2P-1である場合に， f(x)はGF(2)上の原始多項式であるという.

f (J:')の係数(1，Cl・C'2，' .・， cp) を用いたp次の線形プ、

([/1 ⁼Ct(JII-] + ^C2([/I-2+

・

^・

・

+ ('1凡1一jJ

(1ωd 2) (2.2)

によって生成されるGF(2)上の数列(lO，(ll，旬、・・・.^(/1/，.・\を考え，これをやtη}之。と表す.

ただし，初期値旬、α1，・・. ) (Lpー1は，すべてが0とはならないように選ぶものとする. この数列が周期列でありその周期Tが2P -1を越えないことは明らかである. ちょうど T ⁼2]) - 1となるための必要十分条件は， f(けが原始多項式であることである. この条件が成り立っとき， {(ln }ユ。のことをp次の線形最大周期列(Ì\Ia，XÜll11111-1cllgt11 lillcarly r^{付 U l}^'ⁿⁿg SCqUCllCC、)，略してM系列と呼ぶ.

\1系列は，シフトレジスタ系列と呼ばれることもある. これは， 1'vl系列がフィードパックイナのシフトレジスタによって発生できることに由来する. (2.2)によって生成されるM系

列を発生するフィードパックイナシフトレジスタを図2.1に模式的に示す.

111系列の説明については伏見正則著「乱数J (東京大学出版会)第1章節2の内容を参考にさせていただいた.

(13)

出力

図2.1: :\1系列を発生するフィードパックイ寸シフトレジスタ

@は各要素の排他的論理和を表す.

刈2.1はCln-l)・・1α17-pの1 またはOの値が011またはoffとしてシフトレジスタに保持されている状態を示している. 一定の時間間隔で図2.1のp個のレジスタに保持されている

値はそれぞれ右隣りのレジスタに転送(シフト)され，出力と図2.1において現在ο'17-]の値

が保持されているレジスタとには，各レジスタの保持していた値の( C1ぅ匂γ・. 1

cp) (cp

= 1) による加重和(1110cl2)，すなわち， ^([nが出力または転送される.

M系列の自己相関関数はデルタ関数的である. 非同期ss通信において重要な統計量の一つに偶相互相関関数があるが， 2つのM系列の聞の偶相互相関関数は '般にあまり良くない. しかしながら，中には，偶相互相関関数に関して，一様に小さな値を取るような組み合わせが存在する. このような組をプリファードペアと呼ぶ.

偶相互相関関数に関して最適な系列として， KasanlÏ系列やGolcl系列がある. Kas孔1111 系列は， GF(2)上のρ次の原始多項式f(.l') から生成される:\1系列とGF(2)上の2p次の

原始多項式y(.r)

ク(.1') = 1 + d1.)' + d2，r2 +・・ +fl21JI21J、 dp = 1

(2.3 )

から生成されるM系列との排他的論理和を取り，得られる系列である. また， Gold系列は，プリファードペアである2つのM系列の排他的論理和を取り得られる系列である.

1心情旧日i系列を発生するフィードノてック付シフトレジスタを図2.2に模式的に示す.

(14)

←一①

出力

図2.2: KasalllÍ系列を発生するフィードパック付シフトレジスタ

2.2.2 離散力学系に基づく無記憶情報源

区分線形の2進写像とRadclllac仕1関数とを基に一様分布i.i.cl. 2値確率変数列が得られることは，確率論の分野でよく知られている[10]. これは，情報源構成の立場から， 2進写像に基づく無記憶情報源の構成例と見ることができる. 図2.3に2進写像とRad(、lnachcl 関数から得られる定義関数を示す.

112

d

1(ω)

。

(3)ド

。

||

日円

。

112

一一一一"(0 Rademacher関数から

得られる定義関数

一一一+ ^ω

2進写像

ω 〆，，‘、司ノ』 AU

-- nu 口 -- AU 丹、d ^ω

ハU

「一

勺I

図2.3: 2進写像とRaclclll礼(・lH、1関数から得られる定義関数

2進写像はßerlloulliシフトとも呼ばれ，区間[0、1]の実数を2進展開したときに得られる系列を左に1桁だけシフトする写像と同じである. 2進写像をァと表すと， T�こ対して，あ

(15)

る初期値ωが与えられれば，写像の合成の繰り返しによって，実数値解軌道{TIl(ω)}之。が得られる. このとき，任意のm(m二l.2. 3.・…)に対して，凶2.3のRaclc、111a('l!('1関数から得られる定義関数d川を基に得られる2値系列{d川(TII(ω))}之oは，一様分布i.i.cl. 2値確率変数列となる.

2進写像の解軌道{TII (ω)}之υの区間上の出現頻度は，合成回数11が十分大きくなると，

JIに無関係で写像に固有の密度分布に従う. この密度関数は，不変測度の密度関数と呼ばれる. 2進写像の密度関数は一様である. 良く知られている区分線形の2進写像，テント写像，多項式のロジスティック写像， ]J (ρ=2、三...)次多項式のCl!cbyc・11('γ写像は絶対連続な不変(λbsolutcly COlltillUOllS illYariallt; ACI)測度を持つ. 2進写イ像象およびテント写{像象の不変測度の密密、度関数1を図2.--1に，ロジステイツク写イ像象の不変測度の密密、度関数 l を

図即2.5比に

，

ρ 次灯刈Cα11川1C向削b同)乃庁引判刊山y戸川川r叱叶油巾(什d巾伽hc\刊lCY J; π\/1一ω2

5

4

3ト

2

。。)

判2.4: 2進写像およびテント写像の不変密度の密度関数

(16)

5

4

3

2

。。)

図2.5: ロジスティック写像の不変密度の密度関数

5

4

3

2

州2.6: p次Chebychev写像の不変密度の密度関数

最近， Kohdaらは，写像とそのACI測度の密度関数が共に対称性を有するようなある種の一次元離散力学系に対して， Radcl1lé-ì.chcl関数を拡張することによって，一つの実数値解軌道からi.i.d. 2値確率変数を得る方法を与えた

[

²

]

. Kohclaらが考えた写像の例として，

州2.7，図2.8，および\図2.9にテント写像， .J次および8次のChc、byC'hcv写像をそれぞれ不し，図2.10にRadc、lllachcl関数を拡張して得られる定義関数を示す.

(17)

32

。 ω

図2.7:テント写像

←主

3

ω

図2.8: 4次のChebychev写像

(18)

3

p

d

^{2 to-t]}

d

^{2 to-t3} ^{2 to-t2}

ω

判2.9: 8次のCIH、hn'ht、v写像

to

to t]

。

ε

10

ε

t3 e

。

to 一一.CO

d {(ω)

dì(ω)

di(ω)

図2.10: Radelnacher関数を拡張して得られる定義関数

テント写像入)を考えよう. テント写像は一様なACI測度の密度関数を有する. テント像の解軌道{入子(�)}三。に対して，図2.3のRa仁lenlacher関数から得られる定義関数dm (η1==1、2.3，^. ^・ ^・ ^.)を基に得られる2値系列{dm

(_y.y (ω))

}た。は，一様分布i.i.d. 2値確涼変数列となることは自明である. これに対して， Kohclaらの結果によると，図2.10において， d==O、e =1.fn=v

1

^{とすると，} 例えば，図2.10の定義関数djは，明らかに，函2.3

2

(19)

のRacl(、lnachcl関数から得られる定義関数のとは異なるが， d�3を基に得られる2値系列 { d�3(入7(ω))}之。も一様分布i.i.d.2値確率変数列となる.

(20)

第3章

無記憶情報源の設計

3.1 はじめに

不変測度の密度関数は，もし存在するとすれば，解軌道の区間上の出現頻度を表すが，

Chebychev 多項式写像は絶対連続な不変(absolutely continuous invaria.nt: ACI)測度の密度関数を持つ. I\:ohcla Kaj iharaは， Chebvchey写像の高次相関特性を調べることによって，

Chebychev写像のACI測度の密度関数に非常に興味深い性質があることを示した[12]. 最近， Kohda Tsunedaは，この性^質^を均等分布性 (equidistrib'Ldivity pToperty: EDP)と名付け， EDPを有するあるクラスの区分的単調全射(piecewise lllonotonic onto; PÌ\l onto)写像を考え，離散力学系に基づいて無記憶情報源を実現するのにEDPが非常に都合の良い性質であることを利用して，離散力学系の解軌道から得られる2値系列が独立同分布 (independent ancl iclentically distributecl; i.i.d.)確率変数列となるための十分条件を与えた [2]. さらに， I\:ohclaは， EDPを有する離散力学系の実数値解軌道を2値化または多値化する定義関数が一定和性(constαηt S'l.Lrnmαtion property; CSP)と呼ばれる性質を有するとき，

先にKohda Tsuneclaによって得られた十分条件を満足することを示した[4].

本章では，まず， EDPが位相共役に対して不変な性質であることを示す. 次に，同位相像を利用して，新たな無記憶情報源の構成を可能にする，一次元写像のクラスを与える.

新たに導入する写像は， Jacobi楕円関数を介してテント写像と位相共役な有理関数写像であり， Chebychev p次多項式写像を特別な場合として含むため， .Tacobi-Chebyshev有理像と呼ぶ. このJacobi Chebvshev有理写像がEDPを布し，かつ， .T aco bi Che b:vshev有理関数がChebyshe，r多項式と同じように半群的性質を有することを明らかにする. さらに，

I\:ohcla Tsunedaの結果を利用して， Jacobi Chebyshev有理写像に基づき i.i.d. 離散確率変数列を生成する方法についても議論する.

(21)

3.2 均等分布性(EDP)と一定和性(CSP)

Kohda-Tsuncdaによって導入された均等分布性( cquúhstr幼川れJity prOpcTty: EDP)を有するよく知られた写像として，区分線形の2進写像，テント写像，多項式のロジスティック写像，p (pニ2，3、・・・)次多項式のChcbychc、v写像が挙げられるが，I\:ohcla-TSUllC、山はこの

ような写像を含む写像のクラス，すなわち，区分的単調全射( pic、代、WlS(、 lllOllotouic OlltO;

P�f onto)写像を考え，P�1 onto写像の実数値解軌道を2値化した系列が独立同分布

(

illclcpCllclcllt ancl idc、lltically distribllt吋: i.i.d.)確率変数列となるための十分条件を与えた [2]. 1\:011山-TSUllcdaが， [2] で考えたP:\1 OlltO写像の性質を以下にまとめる. i) EDPを有する， ii)区分的に単調なc2関数で全射である， iii)絶対連続な不変(absolutdy contillUOllS

invariallt; ACI)測度を唯一有する. 本章で議論するPlvI onto写像は，まず， ii)の条件を満

たすとする.

P:vI onto写像T: 1 →Iを考える. T がACI測度を有するためには，Lasota-Yorkeの定理[13] より，ァが拡大的，すなわち，

ぜ

l J L ^(ω) 1

^>

1，

10二

! ^ωεI

^:

^J ¹ ⁷ ^{(ω)が存在する} � ^{( 3.1)}

u.) ξJ ⁰1αμ) 1 (/μ) 1

であればよい. ここで，Lasota-York(、の定理は，ァがACI測度を有するための十分条件であることに注意されたい. 実際，P:vl onto写像の一つであるロジスティック写像

3 5. . _ld _ ， . 1

L2(ω)二4ω(1

-ω) _{(ωε[ 0} ヲ1] )は，区

間

[�

₈

， �]

_; ₈

に

おいて

I -i-

L2(ω)

1

� 1となるので，拡大

J

I d ω | 一

的ではないが，ACI測度を有する写像として知られている. また，Tを拡大的なものに限ったとしても，ァがn個の不連続点を持つ場合，Li-Yorkcの定理[14] より，ァは高々n個の ACI測度を持つことが知られている. 本章では，必ずしも拡大的ではない一般のPìv1 OlltO

写像ァを議論するが，本章の目的は，TのACI測度が存在するための条件や，さらに，それが唯一存在するための条件を求めることではない. そこで，簡単のため，T はACI測度 j*(ω)dω(ωε 1 )を唯一有すると仮定する.

次に，ァの実数値解軌道より得られる系列の統計的性質を評価するために，以下の準備を行なう.

まず，写像に対する

Pcrroll-Frobcllius

(P-F) 作用素を導入する.

定義3.1

(Perron 丹obenÚlS作用素)[16) ₁

=

[d. e]， Hを有界変動関数とする. 区分的c2

写像T:

1 →Iに対するペロンフロベニウス作用素PT

は，次式で定義される.

問山ω'Jh)片二

元引L'([d.lj川二￡2 |d凶ルル州川(いい川州山J川�)I引何州州州)川何胴州川|凶阿阿附州川H削町州均州cωM凶9仏似川q仏似ルgi(�パルμ(いい山ω、

(22)

ただし， gi(ω) は，写像7 に関するj番目のJの逆像を表し， jJは逆像の総数を表す.

PTの固有値1の固有関数は，ァの不変測度の密度関数である[16].

写像ァに対するPerron Frobenius作用素PTは，ァの実数値解軌道より得られる系列の相

関特性の評価を可能にする次の重要な性質を有する.

!，

G(川{H(ω)}duJ= !

，

G(T(ω) )H(ω)ル (3.3) ここで， Hは有界変動関数であり， GεL∞である.

次に，写像の均等分布性(EDP)を導入する.

定義3.2均等分布性(equidistributivity property; EDP)[2]:区分的c2写像ァ:1→Iとその AC1測度が，

I g� (ω)lfX(gi(山 ; ^f(ω) ^i=Ol， ^p-lぅ ^uJE1

をみたすとき，写像7 は，均等分布性(EDP)を有するという.

(3.4)

写像7 と初期値ωより生成される定常実数値系列{H(.Xll)

}之o

(-\11ニァペω))を考える.

集合平均E[H(_Yn )]を次式で定める.

E[H(丸)]=

]，

^H(TIl(ω))

^fX

^(ω)dω ^{(3.3 )}

".\nの定常性より， E[H()tn)]をE[H(..'\)] で表す. さらに， EDPを有する写像に対する関数の一定和性(CSP) を導入する.

定義3.3一定和性(constαnt surnrnαtion property;

CSP) [4]: EDPを有する写像7に対して，

関数Hが，

: 十 ^l ^H(9 ^{1 (ω ))} = E[H(_-Y)]: ωε1 (3.6)

Pご5

をみたすとき，関数万は写像7に対して一定和性(CSP)を有するという.

以上の準備のもとに EDPを有する写像とその写像に対する関数Hを考えると，次の注意がただちに得られる.

注意3.1 Hが写像に対してCSPを有するとき，写像より生成される2つの定常実数値系列{H(_\n)}に。と{G(-\n)}之。は，互いに無相関である. すなわち，

E[H(_\n )G(-\n+()] = E[H(�\)]E[G(..'\)卜 ( = ^1.

² ^・

(3.7)

ここで，任恵;の GεL∞に対して注意3.1 が成り立つことに注意されたい.

(23)

3.3 位相共役

本節で導入する位相共役を理解するために，トポロジーについて簡単に述べる. ユークリッド空間Rnの部分集合がユークリッド幾何の対象である凶形である. A， BをR"の図形とし，h: �4→BをAからBへの写像とする. 写像11: A→Bが全単射であって，hおよび

h一1:B→止がともに連続であるとき，hを同位相写像という. 二つの図形A，Bに対して，

AからBへの同位相写像が存在するとき，AとBとは同位相であるという. トポロジーとは，図形の同位相に対して不変な性質を扱う幾何学である.

区間Iの変換をァとすると，ァのグラフG二{(.L T(.r)):.tεI}は図形であるから，トポロジーの対象である. TのグラフGではなく，ァそれ自身は図形ではないが，同位相写像11を用いて，次の位相共役が定義される.

定義3.4 (To]Jological Conj'lLgαtion) [15j.μ6]区間7およびIにおける2 つの変換す:J→7とγ:1→Iが位相共役(to]Jological conjugate)であるとは，

ァ(ω)=110ヂ0/1ー1

(ω) (ωε1) (3.8)

を満たすような同位相写像h:J竺�O1が存在することである. ただし，0は写像の合成を表す.

ここで，写像ナが与えられたとき，定義3.4より，すと位相共役な写像全体の集合は，明らかに，同位相写像全体の集合と対等である. しかしながら，h 0 T 0 hーlが，多項式や有理関数のように，陽な関数で表せるような例は意外に少ない . テント写像A"2に対して，h 0入、 017-1が多項式となるようなんを与えたむlalll-YOll ^:-J('11111(-1.1111の結果[17]および

Gl'OSSlllallll-ThoI11礼子の結果[15]についてはすぐ後に述べる.

以下，hは連続で十分なめらかであるとする.

写像ァとナがそれぞれACI測度を持つとし，それらを各々f*(ω)ル(ωε1)とア(LJ)d IJ (ÜJεJ)で表す. 2つの写像が位相共役であるとき，これらのACI測度は次の関係を持つ.

I dh- 1 (ω) I づ - 1

1'><(ω) = 1""

_| _αU.J¹ ^\

--

^/

^I ^f � ⁽ ^/1 ^-

^I

^(ω)). ^(3.9)

11に関する7とナの関係は次の図式にまとめられる

I

一一→

I

'A 、，‘ +11111 --ーす 'b，. 可A +lill l111↓ 'bf _(3.10)

I

一一→ I

(24)

本章の議論で有用な定理を次に与える.

定理3.1EDPは，位相共役に対して不変な性質である.

証明• PM onto写像7がEDP を有するとしよう. すなわち， (/i.4)が成り立っとする.

hは連続で十分なめらかであり，全射となる各区間においてT.干εc'2であるから，各1 について，

一J

ヌy

か句一 J州一い

一一

d nuJ 、、ht''' 1i -』よ

丹、u

，，at‘、

が成り立つ. ただし，百i(ロ)は，写像ナに関するwのi番目の逆像を表す.

ここで， ACI測度の関係(3.9)の ωにgi(ω)を代入し， ¹¹⁰gi(ω) =万i(lJ) に注意すると，

fX(gi(ω)) = Ih'(gi(ω))1ア(瓦(w)) (3.12)

となる.

式(3.11)と(.1.12)より，

1 y�

(ω)I!本(仏(ω))= Ih'(ω) 1 . I?J� ( w) I]� (瓦(w) )

(3.13)

であり，さらに，式(3.4)と(3.9)より，

|百'(lJ)1ア(百(ロ))二1ア(lJ)

(3.14)

が成り立つ.

位相共役な写像に関してこれまで得られている2つの重要な結果について述べ

fl凶j

る. Clanl von :-JeU111ann [17]は， ACI測度!�(ω)dω- _I ‘ を有するロジステイツ

π ゾ _ω(1 _{- ω)}

ク写像L2(ω)二4ω(1一川、ωε[0. 1] とACI測度]*(lJ)diJ =むを有するテント写像入、(w) = (-1)[お12w (lllOcl 1)

1

Wε[0ぅ1]が同位相写像11-1 (ω)二:::_ Sill-1 v0に関して位相2

7了

共役であることを指摘した. ここで， [.]はGallSS記号，すなわち， [.1']はIを越えない最大の整数を表す. ロジステイツク写イ像象を図3.1に示す. テント写イ像象は第2章図2.7⁷ を惨参照肘されたい一寸方， G…11凶川t孔川1.1山

7π「νi一ωゐ有するp

(ωρ=

2. 31、•

.….

_.)次Chい以l('、b均3百叫h('οげ、

]*米(伊3司)川dw

₌

_{rlvJを有する入λ} Tp(伊3司)二(ト一1り)[p:!戸阿1]ρ(lllOcl

1り).

LJε[伊O、1] が同位相写像h川(w司)二ω汚πU

に関して位相共役であることを指摘した. 3次のChcbyshc、v写像を関3.2に，入γ3を図3.3に

不す.

(25)

ヘ3」問、同

。 ω

図3.1: ロジスティック写像

1

戸-..

� "

g

�-

ω

1

図3.2: 3次のChebyshev写像

(26)

第3章無記憶情報源の設計

---

l笠宮

1

21

1 ω

図3.3:写像�Y3

その後，

Katsura-Fllkucla [18]は， 1.;lêUll-V(11)J (\11山1.1111の結果の類推から，テント写像

を基に同位相写像17-1

(ω、よ ) 二ーと \Sl1- l (Vw，

k)によって， ACI測度

Iピ(ん

)

f本(叫ん)dω二

_I f{w

21ピ(1.:

h/vJ(l -ω)(

1

- 1.:2ω) ^(3.13)

および，パラメータんを有する写像

4ω(1 -ω)(1

-

1.:2vJ)

Q2(vJぅk)こう ωε[0，1]

(1 - k2vJ2)2

(3.16)

を与えた. ただし， Sl1(U、k)は母数lの.Jacobi楕円関数，すなわち，

Lcgc11drc-.Jacohiの標

准形における次の第一種楕円積分の逆関数として定義される[19].

であり，1ピ(k)はl' = 1のときの uの値，すなわち，

(1

du

]{(k)

=

/

J ⁰

，/ (1 - ，，2) (1 -k 2 1，2 )

• T二sn(u.k) (3.17)

Oくよ:2 ^<1

(3.18)

を表す. _". = 0のとき， Q2(叫0)= L2(ω)が成り立つので， Q2(ιよ)は有理関数型!のロジス

ティック写像といえる• Q2(w'.0.9)を図3...1に，人二0.9のときのQ:l(w'，k)のACI測度の密度関数を図3.5に示す.

(27)

(。.0JC)NO

1

。)

図3.4:写像Q2(ι0.9)

ω

5

4

。

。 3

2

図3.5: Q2(ωぅ0.9)のACI測度の密度関数

(28)

ここで， sin -¹(.L')， S11-₁

(

_.1') を

f法

^\/.J.^\

三1

^l^'⁾ ^0三I三1， ^門l'^{) は多項式}

^(3.19)

の積分形で表し， Vla111-VOll ^1\ClllllallllおよびKatsulλFllkllcla が与えた同位相写像とACI 測度を表3.1にまとめる

.

表3.1: "Clalll-\'oll ::，JCU111èUlllおよびKatsul孔Fllkllclaの同位相写像とACI測度

I1一1 (ω) f><(ω)dω

じla111-YOll^-:.JCUllla1111

2 j ^f ^dり

π o ゾ1 -

¹⁾²

dω π J ^u)(l

^-ω

⁾

du

dω

1{(ん) f Ji ^l

Katsllra-Fllkllc1a

広

( k) ゾニ ⁽ ¹

^-ω

⁾ ⁽¹ ^{- k2u))}

1，2)(1 - ".2/，"2)

最近， UnlCno [20]は，

K

atsllra-Fukllclaが与えた写像の不変測度(3.15)に興味を持ち，

テント写像を基にして， ACI測度

l d叫j

f><(ω. k )dω 二 ._

.... �

.. ∞<

112

::; l < 1 _{( 3 .20} ₎

21-{( l. 111) ゾ _ω(1 _-ω)( 1 -1ω)(1 - 771ω)

を有する写像を得るためにじlanl von ^I\eUlnannおよびKatsura Fukudaの結果から類推して，式(3.19)のP(υ)の次数が6である超楕円積分

I

⁰

< l'くl.

九

ゾ ₍₁ _-

_�，2

) ₍ 1 _-

l(2

) ( 1

^{- 772V2}

)

^一 ^ー

を考えた. ただし，

d

ω

-∞くlìI < lく1

1{(人711)= 1

^-，

)0

2，/，ω( l -w)(l-lω)(1

-

mω)

である. 表3.1から ^UlllCllOの類推は自然であることがわかる.

(3.21)

(3.22)

ここで， ACI測度(3.20)を持つ写像は一意的に定まるわけではない. 以下のように， J:.'

(3.19)のP(I')の次数が4である通常の楕円積分だけを考えても， ACI測度(3.20 )を持ち

U 111('110が与えたそれとは異なる写像が得られる.

テント写像を基に同位相写像を

1 ， ^"JIてm+vTて1

{w

^dv

11 -1

(

w.

k) =

^v^-

õ\ T �; 7.

; 1_

_ /

2 1 { ( k ) ん2 \ /"(1 - 1')(1 -1/')(1- 7川)'

く m 三

1< 1 (3.23)

(29)

とする. ただし， k = である. (3.23)の被積分関数分母の根号の中の多 Jてm+vTτ7

項式の軒、

(

\

^土

1η

⁰

^{，1 .}， ^{� .}

D

1 ノ ^{をそれぞれ(3}

^.1

⁷⁾^{におけるそれ}

(

\^-

j

f，' ^-^lJ

j )

^に写

^す

^{1 次変換を}

f，' /

Sとすると， S は

- ( 1 + ゾ (1 -川)(l-l ) ) w+1 S(ω)二

( 1

^-

/ ⁽¹ ^{- �ìl)} ⁽¹ ^- ¹⁾ ⁾

^W^-

¹

で与えられる. これより，，，-1 (ω、よ )は，

. . 1 1

h - 1 (ω . k)

⁼ ^�

+ 一一一s n-1( S ( 川、k ).

2 ' 2I{(人)

と表現される. したがって，

1 ( 1 - 2 S(ω ) :2 + k :2S(ω)

⁴

\

hoλ�2

⁰^h^-1( ω )二 S-l

l _\ 1 - 2 k:2S(ω)2 + k2S(ω)!J ) i

を得る. この写像がACI測度(3

.20 )を持つことは， (3.9 ) から容易に確かめられる.

(3.24 )

(3.25)

(3.26)

3.4 Jacobi-Chebyshev有理写像に基づく無記憶情報源の

構成

前節で述べたI\:atsura Fukucla によるl-lanl von ^I\eUlnann の結果の拡張から類推して， GrOSSlnann Tholnaeの結果の拡張が以下のように容易に得られる. 母数んの

J aco bi Che byshev有理写像(

Jacobiαn elliptic Chebyshev r，αtionαlmα，ps)を導入する. すな

わち

Rp(ωうん) 二cn(pcn-1 (ω?ん) .k ) ; ^w^ε[-1 、1 ]. ^p= 2、3 ，4，・ (3

.27 )

を.Jacobi Chebyshev有理写像と呼ぶ. ただし， cn(ω. k) は，母数k の.Jacobi のcn 関数であり，

ゾ

1 ^- sn2(川)=ω(川)により定義される[1 9]. Rp(川 ) と九(w ) は，

h(早川=cn (2I{(ん)w. k)に関して，位相共役である. Rp(ω k)のACI測度は次式で与えられる.

f <(ω、k ) d ω = I

rlω

2I{( k ) ゾ (1 - w.2){ ₍₁ _ーが ₎ _{+ k2u)2}} ^(3.28)

ん=0 のとき， Rp(ι0) = Tp(w)が成り立つ. ん=0

.9

のとき， ^Jaco bi Che byschv有理写像ん(山\ん)およびR:l(ω. k)をそれぞれ図3.6および図3.7に

，

Rp(w. k)のACI測度の密度関数

を関3.8に示す.

(30)

1

。

ヘ川、hs~内向

1

。

。)

3.6:

Jac・obi-Chebysc‘hv有理写像R2(叫0.9)

1)，(

.f'\

l!3(ω，?) =T3(ω)

0 1

ü)

. . ' . . . . . . . E ' . . . . . . . a ' . . . . ー ' . . . .

. . . . . . . . . . .

1

。

-1 -1

ヘベgLMVMN

図3.7: .Jacobi Chebyschv有理写像R:3(ω.k)

(31)

例3.1 ^P= 2のとき，

4

3

2

。。)

図3.8:

Rp(叫0.9)のACI測度の密度関数

1 -2(1-ω2)

^{+ k:2}

(1-ω2)2

R2(ω". )

^二

(3.29 )

任意の p (p ⁼ 2，3ぅ・・・)に対してRp(ω.k)が有理関数型であるのは，次の漸化式より保証される.

定理3.2

R p + 1 (ω，k:) -

¹ 1，')/1 _n

2w

( 1.\')\/1 _.)\R_p

(

^uJ，

k )

⁺

flpー1 (叫k) = 0)

十

1- k 2 (1 - Rp(ω :ん)2)(1-ω2)

^.L"p

p=1.2，'" (3.30 )

が成り立つ. ただし， Ro(ω.k) = ^l.R1(ω.

k)

=ωである.

注意3.2 ^k= 0のとき， Rp(叫0)に関する漸化式は， Chebyshev多項式Tp(ω)に関する漸化式となる，すなわち，

Tp+1(ω)-2ωTp(ω)

⁺

Tp_!(ω)=0 (3.31)

さらに， flp(-.JJ.k)は，半群的性質を有する

(32)

定理3.3Rr(ω、k)と九(-.u."・) (r. sど2)は，

R，.(Rs(山\ん)、ん)

₌

R"S(-.u.

_k) (3.32 )

を満たす.

定理

3

₁_. _より，次^の系が直^ちに得^られる

.

系3.1

Rp(ω. ".)はEDPを有する.

ここで， Q2(ω. "・)とR2(wうよ)は，同位相写像

1 ， " 1-2ω+ん2ω2

h

^-¹

(ω. k)

⁼

_{1 -k2u)'2}

^勺

(3.33)

に関^して位相共役であることを付記^してお^{く. た}だ ^し， k = 0のとき， Q2(ω) 0) = L2(ω)と R2(ω，0)二九(こりが，同位相写像h-1(ι0)二1-2-.uに関して位相共役であるのは，よく知

られている.

Kohda T su n e _cl a の結果[ 2 ] を利用して， .Jacobi Cheb!'she\."有理写像に基づき， pシンボルからなる有限集合S = {80・s・1. _.・. 8p-l}に値を取るi.i.cl確率変数列の生成法について議論しよう. 区間Iを互いに重なり合わないp個の部分区間に分割する. すなわち，

(i + 1) ι=lcn(2K(k)y

k) .cn(2K(ん)

-7-

J) ) 、

各部分区間に対して，定義関数

\$;

(ω) = { ^�

;=0、l、・・・、p -1.

fOlωε人、

;=0‘1，' ..p-1

ot hcrwisc ¹

を定^める

.

_こ _の_とき，次^の補題が成り立^つ.

補題3.1 Rp(ω. k)に関して，定義関数\8，(ω)

(i

= 0.1，'・• ，p - 1)は，

jgu(QJ(JA))=EMani

を満たす.

(3.34)

(3.35)

(3.36)

(33)

これは，い! (ω)がRp(w，人)に対してCSPを有することを意味する. ここで， !}j (ω、ん)はω

のん(U)

，よ)に関するj番目の逆像を表し，

/ ピ( ".)

⁺

^cn一 ¹ { (

^-

l ⁾ j

^ω

} \

gj(ω. k) =

cn

! _\

^J^{-� -}^\..^/ ^' ^�-__P^- ^L^\ ^�^/

^-

^J

₎ I

^.

^J

^ニ

^O

^、

¹

^{. ・・・ .}

^p ^-1 ^(3.37)

で表される.

k

= 0のとき，めい.0)は， ωのTp(ω)に関するj番目の逆像を表す[12].

方，次式で定義される1対l写像σ:1→S

によって，

σ(ω)

= 5i

for

_ωεん; i =

0.1，'"

^，

p ^-

1

(3.38)

Prob(σ(Rp(ω， k ⁾ )

二川

) =

E

\ 8 [

i

(

_.，y

) ]，

ⁱ⁼

0

i 1， . . . ，p ^- 1

( 3 .39 )

が得られる. Rpいうよ)はEDPを有し， Rp(w，よ)に関して定義関数\81 (ω)がCSPを有する

ので， 1(oh山の結果[4]から次の系が直ちに得られる.

系3.2σ(R;; ⁽

^ω�

k))

=じとおこう. このとき，長さmの任意のシンボル列，すなわち，

ioSi1 ^•^•^•si，n_lに対して， {):1}乙。は，

Prob(ìóY'l・・・)�η-1

二SioSil " ' 8imーI

)

二Prob(ì ó二九)Pl'Ob()

'1二ぢi]

)

---

P

10

1

)

(

₃

;

ηー1 - Sⁱm

ー

I

)

(3.40)

を満たす.

これは，確率変数列九.)'11'" が独立であることを意味する.

Jacobi Chc、byschy有理写像R3(ω、人)を用いて， i.i.cl. 3値確率変数を生成する概念図を図3.9に示す.

(34)

rヘ

ーミ

�

3

1

。� 0

ロミ

-1!

白l'

. .

Js。

ぺル _S。

. .

。)

JS1

ペル _S1

。1

JS2

ペル _S2

刻3.9: R3(ω1 ".)に基づくi.i.cl.3値確率変数の生成法

ここでは， Rpを利用して，無記憶情報源を構成するのに，自明と思われる方法を用いたが， (3.28)より， Rp のλCI測度の密度関数は偶関数であるから対称、性を有し(図3.8参照) ， Jacobi楕円関数(・nの偶関数性から， jJが偶数のとき，写像自身も対称、性を有するので，

I\ohclλ-TSlll川laの結果を利用して[2卜[3]，第2章図2.10に示したような，非常に広い2値化または多値化関数からi.i.cl離散確率変数列を生成できることを付記しておく.

本章の終りにR2(ωi k)の実数値解軌道の相関特性に関する興味深い結果とそれから得られる予想、を述べる.

定理3.4R2(ω". )は，

E[�\II-\II+{]

⁼O. (三l

(3.41)

を満たす. ただし， "'\n二R2(ω、k). 11二0.1、2、・・・である.

証明・定常性より， 11 ⁼0の場合に成り立つことを示せば十分で、ある. cu-1(・)は，

C'll-1(-U)

=

21\-(ん)ーぐ11-1/1 _(3.42)

(35)

を満たす. この関係式と(3.37) により， p=2のとき，

i 会

^.9i(ωk)二O

^(3A3)

が得られる. これは， R2(ωうた)に対して， �Yoニω がCSPを有することを意味し，定義 8.1，式(3.3)，および系3.1より，定理が成り立つことがわかる.

定理3.3と定理3.4により，次の系が得られる:

系3.3 R2m (ω うk)う'171二lう2，.・1は

E[-，Yη�Yn+e]

= 0，

C三L

_{(3.44 )}

を満たす. ただし，_"Yn

R2m (ιん)ぅ1/，二Oぅ1，之.. _.である.

予想3.1任意の素数pに対して， Rp(ω， k)は，

E[XnLY叶e]二O. ('三1，

(3.45 )

を満たす. ただし， ^LY^礼二R

;

(叫ん₎，n二0，1ぅ之. ..である.

k二Oのとき， Rp(ω、0)二五(ω)

(p =

2ぅ3γ. .)となるが， p 次Chebyshev写像九(ω)については，任意の素数pに対して，次式が成り立つ[15]， [21].

E[-，YnXn+e]二0， f.三1

(3.46)

ただし， '^-^Y

n

^二^T

^;

^(ω)^，^{1 ì}^. ⁼0、1 ，2.・・・である. 定理3.4は， k-/:Oのとき， R2(い)， k)の自己相関関数がT2(ω)と同様に6関数的であることを意味するが，予想、3.1は，定理3.4の類推から，

pが奇素数の場合にも， Rp(ω， k)の自己相関関数がTp(ω)と同様に6関数的であることを主張している. 予想、3.1 が成り立つための十分条件を付録Aに示す.

3.5 まとめ

本章では，まずず、，写イ像象の均等分布性(いe q卯'I.lωl�ωd，t仏δδd吋山;t:引t:かr仙f

して不変な性質であることを示した. 次に， ^p(p = 2、広・・・)次Chebyshev多項式写像を特別な場合として含む，より広い一次元写像のクラスJacobi-Ch(、hysh(、v有理写像

Rpを与え，

新たに導入したRp'こ基づいて無記憶情報源、を構成した.

(36)

第4章

マルコフ情報源の設計

4.1 はじめに

Kalnlanは， Wienerによる信号の予測理論を拡張し，最適な信号の推定値を求める独自の算法であるカルマン・フィルタを発明したことで有名であるが， 1956年に発表した彼の修士論文山から，彼が，カオスが認知される以前に，カオスを呈する離散力学系を発見していたことがわかる1 この論文において，彼は「非線形サンプル値制御系が，制約条件のもとで，自律非線形システムと同様な振舞をする」ことを指摘し，マルコフ連鎖と非線形一次元差分方程式の等価性を議論した. Eahnanによるカオスの発見は， 'Clanlとvon

� eU1nan [17]によるそれに遅れるものの， Lorenz (1963) [23]より約10年，一次元非線形写像を調べた\Iay (1976) [24] より20年前の発見であった. さらに， Ealnlanは，カオス離散力学系を単に発見しただけに留まらず，区分的線形単調全射( piecewise-linear-lnonotonic

onto; PLr-.1 OlltO)写像を用いて，マルコフ連鎖を構成する方法を与えていた.

Kahnanによるカオス離散力学系の発見から半世紀を経ょっとしている現在，無記憶情報源の構成問題に関して， I\:ohdaらによって，ある種の一次元離散力学系に対して，実数値解軌道から得られる系列が i.i.d. 2値または多値確率変数列となるための十分条件が与えられ[2] [3]，この種の離散力学系の有する特性や十分条件を成立させる系列生成法が詳細に調べられている[4]. また， Oohalnaらによって，離散力学系に基づくマルコフ情報源の構成に関する研究も行なわれており[5]，さらに， BarnsleyやEanavaによって，離散力学系に基づく無記憶情報源やマルコフ情報源の構成法とデータ圧縮の方法のlつである算術符号との類似性に関する議論がなされている[6] [8]. これらの研究を契機に， Kahnanの修

1 Ealmanが， Ulamと'"011 N �Ulllan11とは独立に，如何にしてカオス発見に至ったかというエピソードに興味をお持ちの方は， I�allllaIl自身による回顧と展望[22]を一読されることをお勧めしたい.

(37)

士論文が見直され，離散力学系に基づく情報源の構成に関する研究はKahnallの修士論文を起源とすることが再認識された. その後， Kahnällによるマルコフ情報源の構成法を応して，木情報源2の構成に関する研究も行なわれている[9] .

本章では，離散力学系に基づく情報源構成の立場から，

I\:ahnallの結果を再考する.

その結果， Kahnallが，入7状態マルコフ連鎖を実現するために，入r2個の部分区間を有する離散力学系を構成していたことを明らかにする. さらに，マルコフ推移行列の階数が入γであるとき， Kahnallの構成法を改良して，最小な部分区間数を有する離散力学系による構成法を与える.

4.2 Kalmanによるマルコフ情報源の設計

集合s

= {l， 2， 3， λー)に値を取り，マルコフ推移行列P= {]Jij} ヴ ^{ニ1によって記述}

されるN.s状態、単純マルコフ連鎖を考える.

Kalmanは，任意の人jに対して

Pi) >

0 (4.1 )

を満足するような推移行列Pで表現されるマルコフ連鎖を， Nj個の部分区間を有する区分的線形単調全射(picc円.vis('-lillcar-lllollotonic・OlltO:^PL:\1OlltO)写像ァ:J二[0，1]→J，

ω川+1二r(ω11

)

，

11二O、1，2，"

.、 ωηεJ

から構成する方法を以下のように与えた.

区間J をN8個の部分区間

J= U

Ji に分割する. ただし，

ム= (di ^-1

.

di] ^， do = 0くd1くぬく・ <dん=1 である. さらに，部分区間λ(i= l. 2.・・・入'Jを入ン個の部分区間

九二UλJ

)=1

( 4.2)

( 4.3)

( 4.4)

(4.3 )

22進語頭符号が発生したという条件の下でl(または0)が発生する，条件付き確率によって完全に決定される情報源を定常2進木情報源と呼ぶ.

(38)

に分割する. ただし，

Ji

^，j二

(di，j-l' di.j] fol' T(di)二l.

( di•O二di-1、「liJ78=rlI)、

(di，j. di，j-l] for T( di) = 0

( di.O二di1 di，Ns二di-1)、

である. このとき，分割点は，マルコフ分割と呼ばれる条件[25]

と

ァ(di)ε{

0， 1}

¹ ⁱ= 1，

2，

• • • ， 1\

T ( d i.j) = d j

. i.

j

⁼

1. 2.

・・ \

入二、

を満たし，部分区聞が，推移確率により定まる条件

|ん1二7Ji__‘ i ，

1、i=l、 2.・・・.入二 .

1 Ji 1

^1:'1)^， ^{• ，}^.J ^ぷ

( 4.6)

(4.7)

(4.8 )

(4.9)

を満たすようにする. ただし， 1 1 1 は，区間Iの長さを表す. I\:ahnanが構成した写像7を区間λJに制限したものをTi・Jとすると，

ηj(ω)=

|よ|ω+

( d

i^.

jdj

^一¹

- di.j-1 dj)

|よj l

dεJi.j for T( di) = 1、

-Jilω+ (di.j-1 dj

^-

rli.jrlj-1 )

|よjl

ωε11，j

^for

T( di) = 0

(4.10)

が得られる. 後に，この写像を含む区分線形マルコフ写像と呼ばれる写像が， Bo}孔l'skyによって定義され，詳細に調べられている[25].

構成した写像が意味を持つためには，写像の絶対連続な不変(absolutdy

contilluoUS

iuyariallt;

ACI)測度の存在が保証されていなければならない. ACI測度の存在の問題を最

初に提起したのはUla.nlであり[26]，この問題に最初に解答を与えたのはLasotaとYOl'k(、

[13]であるが， Boyarskyの結果[23]によって， Kahllallが構成した写像は常にACI測度を有することがわかる.

条件(4.7)は，得られる写像に2Ss個の任意性があることを意味する. しかしながら，

これらの写像は同じマルコフ連鎖を実現する.

(39)

Ka1山1.11の写像7と初期値ω( ε[0.1])から得られる実数値解軌道{Tη (ω)}之。に対して，

写像σ:

[0、1]→S

σ(ァベω))=i， T1I(ω)ε ^ん i=l、2.・・・.入:

(4.11 )

を定め， XfJ二σ(TlI(ω))と表すと， Sに値を取る確率変数列{�\1I}に。が得られる. このよ

うに，入二個の部分区間Jリ(j二112 ・・・ .入二)をひとつの区間Jiとみなすことを粗視化とい

う. このとき， {1\n}工。はマルコフ連鎖となる. この事実の証明はKahn<-111によってなされているので省略する[1]. ただし， Kahn札口は，この証明において，部分区間Jiから部分区間みへの推移確率を

ーも!

qL 11ム

一一

Iつ一一7

7J一内一川一山

( 4.12)

で求め，これがPijに等しいとした. ここで，

1II

(止)は集合4のルベーグ測度を表す. 各部分区間ょにおいて不変測度の密度関数が一定であれば， (-!.12)はpりとなるが， Kahllan の写像は，この条件を満足することを示そう.

定義 3.1で定義した写像ァに対するP川1'011F1'ohcllins

(P-F)作用素PT

の固有値

1の固有

関数は，ァの不変測度の密度関数である[16]. したがって， Tの不変測度の密度関数を求めるためには， PTの固有値1の固有関数を求めればよいことになる.

1a111は写像のACI測度の存在の問題を提起した際に写像に対する P-F作用素を近似するために，部分区間1iから部分区間んへの推移確率を

1n[li

n T-1 (ん) ]

J 、i.j=1.2.・・・.Jl

1，)

- _nl(li、 (4.13)

と定義した[26]. ただし，

J = U 1i1 1i ηん=的 '1)二1、2.・ JJ ( 4.14)

i=1

である. これより， Jt!次正方行列{t ij

} i\.� ₌

1が得られる. これをUla111の推移行列と呼ぶ.

写像γ:.]→Jに対するU1a111の推移行列は，区間Iを直和分割する区間列11 ・ん.・・・.IM が与えられれば一意に定まるので，

l-lanlの推移行列をT (11・ん•

• • •

，

1，\}

)

と表す.

先に， l�lalnの推移行列は， P F作用素の近似であると述べたが，区分的線形マルコフ写像の場合，部分区間を適切に選び，各部分区間の定義関数を要素とするベクトルを考えれば， Clanlの推移行列とP F作別素とは相似となる[27]. したがって， I�alnlanの構成した写像の不変測度の密度関数を求めるためには，部分区間を適切に選び， Kalmanの写像に対するじlalllの推移行列の固有値1に対する左同有ベクトルを求めればよい.

(40)

Kahllanの写像に対して， xf個の区間列J1.IぅJ1.2， .・.， JXo.1，.・. ，J，へ'入r を選ぶと， ^P-F 作用素と相似な

P1 P2 P1

^P)

T(

^J1.1ⁱ，]r，2ぅ・ヲJ}叫ん)二 ^ム

Pjへ.�

P:VS

P1 九 ••• Pi\'s が得られる. ただし，

ri二

。

Pi I、

^Pi二(PiJ

，Pi2，

^・ ^.

，]-九九) ，

。

Oニ(0γ・・ぅ0)�ーーヘ

(4.15)

(4.16)

である . これより， Kalnlêlnの写像で定まる区間力学系は， Nj次の推移行列

T(

J1，1ぅJ1).，...，JrvνvJで表されるマルコフ連鎖と等価であることがわかる.

注意4.1任意に与えられたマルコフ推移行列をPとすると， Pで定まるマルコフ連鎖を実現するKalrnαnの写像に対するUlarnの推移行列T(Jl.lぅJ1.2γ・.ⁱJNs，Ns)は，

N::-N

A(T(

^{J1，1ヲJlJ?} 7JM

を満たす. ただし， A(C)は，行列Cの固有値全ての集合を表す.

以上の準備のもとで，次の定理を示す.

(4.17)

定理4.1K alrnanが構成したPLM onto写像のACI密度関数は，各区間Jiにおいて一定である.

証明: Boyαrskyの結果

!

25

j

により， KalrnanのPLM onto写像は，次式のような定義関数で表される不変測度の密度関数を唯一持つ.

r'(.AJ) =乞fh人J (ω)、 ( 4.18)

離散力学系に基づく情報源の設計に関する研究