定理６ . １前半の証明のスケッチ

(1)

メッセージ伝播法の入門から最先端まで第８回講義資料

AMP

の状態発展方程式

九州大学

令和元年１０月２３日

豊橋技術科学大学電気・電子情報工学系

准教授竹内啓悟

(2)

定理６ . １前半の証明のスケッチ

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡 = 〈𝚲𝚲 ^𝑘𝑘 𝜕𝜕 _𝑡𝑡

^′

𝒎𝒎 � _𝑡𝑡 〉

と定義する。

𝑡𝑡 = 0

、

𝑡𝑡 = 1

の場合の証明省略

すべての

0 ≤ 𝑡𝑡 < 𝜏𝜏

、

0 ≤ 𝑡𝑡 ^′ ≤ 𝑡𝑡

に対して、

𝑔𝑔 _𝑡𝑡 (0)

′

,𝑡𝑡 a.s.

0

となるような

1 < 𝜏𝜏 < 𝑇𝑇

が存在すると仮定し、

𝑔𝑔 _𝑡𝑡 (0)

′

,𝜏𝜏 a.s.

0

を証明する。

帰納法による証明

帰納法の仮定から、

𝑡𝑡 < 𝜏𝜏

の場合に一般化誤差モデルはAMP の誤差モデルを含むので、定理６.２から

𝜉𝜉 _𝑡𝑡

は定数とみなせる。

𝑔𝑔 _𝑡𝑡 (0)

′

,𝑡𝑡 a.s.

0

を

𝑡𝑡

に関する数学的帰納法で証明する。

(3)

システムの簡単化

{𝑎𝑎 _𝑡𝑡 }

を

𝑎𝑎 ₀ = 1

と

𝑎𝑎 _𝑡𝑡 = 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _𝑡𝑡−1

を満たす数列とし、

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡 = 𝑎𝑎 _𝑡𝑡 �𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡

とおく。

�

𝑚𝑚 _𝑡𝑡

と

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡

の定義式から、

𝑡𝑡 ^′ < 𝑡𝑡 − 1

の場合に、

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡 = 𝜉𝜉 _𝑡𝑡−1 1 + 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡 ^(𝑘𝑘)

^′

^{,𝑡𝑡−1} − 𝜉𝜉 _𝑡𝑡−1 𝑔𝑔 _𝑡𝑡 𝑘𝑘+1

′

,𝑡𝑡−1 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑔𝑔 _𝑡𝑡 𝑘𝑘

′

,𝑡𝑡−2 + 𝑜𝑜(1).

�𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡 = 1 + 1

𝛿𝛿 �𝑔𝑔 ^𝑡𝑡 ^(𝑘𝑘)

^′

^{,𝑡𝑡−1} − �𝑔𝑔 _𝑡𝑡

^′

^𝑘𝑘+1 _{,𝑡𝑡−1} − 1

𝛿𝛿 �𝑔𝑔 ^𝑡𝑡 ^𝑘𝑘

^′

^{,𝑡𝑡−2} + 𝑜𝑜(1).

𝑡𝑡 ^′ = 𝑡𝑡

、

𝑡𝑡 ^′ = 𝑡𝑡 − 1

の場合に同じ議論を繰り返すと、

�𝑔𝑔 _{𝑡𝑡,𝑡𝑡} ^(𝑘𝑘) = 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 , 𝜇𝜇 _𝑘𝑘 = lim _{𝑀𝑀=𝛿𝛿𝛿𝛿→∞} 1

𝑁𝑁 Tr Λ ^𝑘𝑘 .

�𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡} ^(𝑘𝑘) = − 𝜇𝜇 _𝑘𝑘+1

𝛿𝛿 + �𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡−1} ^𝑘𝑘 − �𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡−1} ^𝑘𝑘+1 + 𝑜𝑜 1 .

(4)

解の構造解析

簡略化されたシステムの解は、

�𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

′

,𝑡𝑡 = 𝑔𝑔 _{𝑡𝑡−𝑡𝑡} (𝑘𝑘)

′と書ける。

𝑔𝑔 ₀ ^(𝑘𝑘) = 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 ₁ ^(𝑘𝑘) = − 𝜇𝜇 _𝑘𝑘+1

𝛿𝛿 + 𝑔𝑔 ₀ ^𝑘𝑘 − 𝑔𝑔 ₀ ^𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘) = 1 + 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡−1 ^(𝑘𝑘) − 𝑔𝑔 _𝑡𝑡−1 ^𝑘𝑘+1 − 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡−2 ^𝑘𝑘 + 𝑜𝑜(1).

すべての

𝑡𝑡 ≤ 𝜏𝜏 < 𝑇𝑇

に対して、

𝑔𝑔 _𝑡𝑡 ⁽⁰⁾ ^{𝑎𝑎.𝑠𝑠.} 0

を証明すればよい。

性質

𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘)

は

𝑡𝑡 + 𝑘𝑘 + 1

次までのモーメント

{𝜇𝜇 _𝑘𝑘

^′

}

のみに依存する。

𝑔𝑔 _𝜏𝜏 ⁽⁰⁾

は

𝜏𝜏 + 1 ≤ 𝑇𝑇

次までのモーメントのみに依存

(5)

母関数

𝐺𝐺 𝑥𝑥, 𝑦𝑦 = �

𝑡𝑡=0

∞

𝐺𝐺 _𝑡𝑡 (𝑥𝑥 ) 𝑦𝑦 ^𝑡𝑡 ,

定理６.１の仮定から、

{𝜇𝜇 _𝑘𝑘 }

はMP分布のモーメント系列に一致すると仮定して、一般性を失わない。

𝑔𝑔 ₋₁ ⁽⁰⁾ = 0.

𝐺𝐺 _𝑡𝑡 𝑥𝑥 = �

𝑘𝑘=0

∞

𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘) 𝑥𝑥 ^𝑘𝑘 − 𝑔𝑔 _𝑡𝑡−1 ⁰ 𝑥𝑥 ,

すべての

𝑡𝑡 ≤ 𝜏𝜏

に対して

𝑔𝑔 _𝑡𝑡 ⁽⁰⁾ ^{𝑎𝑎.𝑠𝑠.} 0

を証明するためには、

帰納法の仮定

𝑔𝑔 _𝑡𝑡−1 ⁽⁰⁾ ^a.s. 0

から、

_𝑥𝑥→0 lim 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 0

を示せばよい。

(6)

母関数の評価

η変換のべき級数表現

𝜂𝜂 𝑥𝑥 = ∑ _𝑘𝑘=0 ^∞ −𝑥𝑥 ^𝑘𝑘 𝜇𝜇 _𝑘𝑘

を使用すると、

𝐺𝐺 ₀ 𝑥𝑥 = 𝜂𝜂 −𝑥𝑥 − 𝜂𝜂 −𝑥𝑥 − 𝜇𝜇 ₀

𝑥𝑥 + 𝑜𝑜 1 ,

𝐺𝐺 ₁ 𝑥𝑥 = − 𝜂𝜂 −𝑥𝑥 − 1

𝛿𝛿𝑥𝑥 + 1 − 1

𝑥𝑥 𝐺𝐺 ⁰ 𝑥𝑥 + 𝑜𝑜 1 , 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 1 + 1

𝛿𝛿 − 1

𝑥𝑥 𝐺𝐺 ^𝑡𝑡−1 𝑥𝑥 − 𝐺𝐺 _𝑡𝑡−2 𝑥𝑥

𝛿𝛿 + 𝑜𝑜 1 .

𝐺𝐺 𝑥𝑥, 𝑦𝑦 = 𝐺𝐺 ₀ 𝑥𝑥 + 𝑦𝑦𝐺𝐺 ₁ 𝑥𝑥 + 1 + 1 𝛿𝛿 −

1 𝑥𝑥 𝑦𝑦 𝐺𝐺 𝑥𝑥 , 𝑦𝑦 − 𝐺𝐺 ₀ 𝑥𝑥

− 𝑦𝑦 ²

𝛿𝛿 𝐺𝐺 𝑥𝑥 , 𝑦𝑦 + 𝑜𝑜 1 .

したがって、

𝜇𝜇 ₀ = 1,

(7)

母関数の有理関数表現

前ページの代数方程式を解くと、

𝐺𝐺 𝑥𝑥 , 𝑦𝑦 = 𝑃𝑃(𝑥𝑥, 𝑦𝑦)

𝑄𝑄(𝑥𝑥, 𝑦𝑦) + 𝑜𝑜 1 ,

𝑃𝑃 𝑥𝑥, 𝑦𝑦 = 𝛿𝛿𝑥𝑥 − 𝛿𝛿 − 𝑥𝑥𝑦𝑦 𝜂𝜂 −𝑥𝑥 + 𝛿𝛿, 𝑄𝑄 𝑥𝑥 , 𝑦𝑦 = 𝛿𝛿𝑦𝑦 + (𝑦𝑦 − 𝛿𝛿) 𝑦𝑦 − 1 𝑥𝑥.

性質１

𝐺𝐺 0, 𝑦𝑦 = 0 for 𝑦𝑦 ≠ 0.

∵ 𝑄𝑄 0, 𝑦𝑦 = 𝛿𝛿𝑦𝑦 ≠ 0, 𝑃𝑃 0, 𝑦𝑦 = −𝛿𝛿𝜂𝜂 0 + 𝛿𝛿 = 0.

性質２

𝑦𝑦 ∈ (0, min 1, 𝛿𝛿 )

の場合に、

𝑃𝑃(𝑥𝑥, 𝑦𝑦)

は

𝑄𝑄(𝑥𝑥 , 𝑦𝑦)

で割り切れる。

𝑥𝑥→0 lim 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 0

性質１と性質２から、

(8)

性質２の証明

𝑄𝑄 −𝑥𝑥 ^∗ , 𝑦𝑦 = 0

を満たす零点

−𝑥𝑥 ^∗

は唯一で、仮定

𝑦𝑦 ∈ (0, min 1, 𝛿𝛿 )

から右式を満たす。

𝑥𝑥 ^∗ = 𝛿𝛿𝑦𝑦

(𝑦𝑦 − 𝛿𝛿)(𝑦𝑦 − 1) > 0.

零点

−𝑥𝑥 ^∗

において、

𝑃𝑃 −𝑥𝑥 ^∗ , 𝑦𝑦 = 0

を示せばよい。

𝑃𝑃 −𝑥𝑥 ^∗ , 𝑦𝑦 = 𝛿𝛿 1 − 𝜂𝜂 𝑥𝑥 ^∗

1 − 𝑦𝑦 = 0.

MP分布の場合のη変換は以下の方程式を満たすので、

𝑥𝑥 ^∗

の定義を代入して、

𝜂𝜂 𝑥𝑥 ^∗ − 𝑦𝑦 − 𝛿𝛿

𝑦𝑦 𝜂𝜂 𝑥𝑥 ^∗ − 1 − 𝑦𝑦 = 0.

η変換は正なので、

𝜂𝜂 𝑥𝑥 ^∗ = 1 − 𝑦𝑦.

𝑃𝑃 (𝑥𝑥, 𝑦𝑦)

の定義から、

𝑥𝑥 ^∗ 𝜂𝜂 ² 𝑥𝑥 ^∗ + 𝛿𝛿𝑥𝑥 ^∗ − 𝑥𝑥 ^∗ + 𝛿𝛿 𝜂𝜂 𝑥𝑥 ^∗ − 𝛿𝛿 = 0

∎

(9)

定理６ .1 後半の証明

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡 , 𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡 , 𝑐𝑐 _{𝜏𝜏,𝑡𝑡} = 1

𝑁𝑁 𝒒𝒒 ^𝜏𝜏 ^T 𝒒𝒒 _𝑡𝑡 ,

大システム極限で、AMPの状態発展方程式を導出する。

𝑑𝑑 _{𝜏𝜏,𝑡𝑡} = 1

𝑁𝑁 �𝒒𝒒 _𝜏𝜏 ^T �𝒒𝒒 _𝑡𝑡 , 𝑒𝑒 _𝑡𝑡 ^(𝑘𝑘) = 1

𝑁𝑁 𝒎𝒎 � _𝑡𝑡 ^T 𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘.

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘 − 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘+1 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘 +𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^(𝑘𝑘) − 𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^𝑘𝑘+1 − 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿 𝑏𝑏 ^{𝑡𝑡−1,𝜏𝜏} ^𝑘𝑘 + 𝑒𝑒 _𝜏𝜏 ^𝑘𝑘 ,

𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ 𝜉𝜉 _𝑡𝑡−1 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^(𝑘𝑘) − 𝜉𝜉 _𝑡𝑡−1 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^(𝑘𝑘+1) − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘 + 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 𝑑𝑑 _{𝜏𝜏,𝑡𝑡} − 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿 𝜇𝜇 ^𝑘𝑘 𝑑𝑑 _{𝜏𝜏,𝑡𝑡−1} , 𝑑𝑑 _{𝜏𝜏,𝑡𝑡} = 𝑐𝑐 _{𝜏𝜏,𝑡𝑡} − 𝜉𝜉 _𝜏𝜏−1 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _{𝜏𝜏−1,𝑡𝑡−1} ⁰ ,

𝑒𝑒 _𝜏𝜏 ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ 𝜉𝜉 _𝜏𝜏−1 𝑒𝑒 _𝜏𝜏−1 ^𝑘𝑘 − 𝜉𝜉 _𝜏𝜏−1 𝑒𝑒 _𝜏𝜏−1 ^𝑘𝑘+1 − 𝜉𝜉 _𝜏𝜏−1 𝜉𝜉 _𝜏𝜏−2

𝛿𝛿 𝑒𝑒 _𝜏𝜏−2 ^(𝑘𝑘) + 𝜎𝜎 ² 𝜇𝜇 _𝑘𝑘+1 .

(10)

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘 ⁾ の評価

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝑰𝑰 − 𝚲𝚲 𝒃𝒃 _𝑡𝑡 + 𝜉𝜉 _𝑡𝑡−1

𝑁𝑁 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 1 + 𝛿𝛿 ⁻¹ 𝑰𝑰 − 𝚲𝚲 � 𝒎𝒎 _𝑡𝑡−1

− 𝜉𝜉 _𝑡𝑡−1

𝑁𝑁𝛿𝛿 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒃𝒃 _𝑡𝑡−1 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝑁𝑁𝛿𝛿 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡−2 + 1

𝑁𝑁 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘

= 𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^(𝑘𝑘) − 𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^𝑘𝑘+1 + 𝜉𝜉 _𝑡𝑡−1 1 + 𝛿𝛿 ⁻¹ 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘 − 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘+1

− 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿 𝑏𝑏 ^{𝑡𝑡−1,𝜏𝜏} ^𝑘𝑘 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑎𝑎 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘 + 𝑒𝑒 _𝜏𝜏 ^(𝑘𝑘) + 𝑜𝑜 1 . 𝑡𝑡 < 0

に対して

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^𝑘𝑘 = 𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^(𝑘𝑘) = 0

として、

�

𝒎𝒎 _𝑡𝑡 = (𝑰𝑰 − 𝚲𝚲)𝒃𝒃 _𝑡𝑡 + 𝜉𝜉 _𝑡𝑡−1 { 1 + 𝛿𝛿 ⁻¹ 𝑰𝑰 − 𝚲𝚲} 𝒎𝒎 � _𝑡𝑡−1 + 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘

− 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿 𝒃𝒃 ^𝑡𝑡−1 + 𝜉𝜉 _𝑡𝑡−2 𝒎𝒎 � _𝑡𝑡−2 , 𝒎𝒎 � _𝑡𝑡 = 𝒃𝒃 _𝑡𝑡 = 0 for 𝑡𝑡 < 0.

(11)

𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘 ⁾ の評価

𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝑰𝑰 − 𝚲𝚲 𝒃𝒃 _𝑡𝑡 + 𝜉𝜉 _𝑡𝑡−1

𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 1 + 𝛿𝛿 ⁻¹ 𝑰𝑰 − 𝚲𝚲 � 𝒎𝒎 _𝑡𝑡−1

− 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒃𝒃 _𝑡𝑡−1 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡−2 + 1

𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘

= 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 𝑑𝑑 _{𝜏𝜏,𝑡𝑡} + 𝜉𝜉 _𝑡𝑡−1 1 + 𝛿𝛿 ⁻¹ 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^(𝑘𝑘) − 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^(𝑘𝑘+1)

− 𝜉𝜉 _𝑡𝑡−1

𝛿𝛿 𝜇𝜇 ^𝑘𝑘 𝑑𝑑 _{𝜏𝜏,𝑡𝑡−1} − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑏𝑏 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘 + 𝑜𝑜 1 .

定理６.２の性質(A2)を使うと、

𝑡𝑡 < 0

に対して

𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 0

、

𝑑𝑑 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 0

として、

ただし、以下を使った。

1 𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝒃𝒃 _𝑡𝑡 = 1

𝑁𝑁 �𝒒𝒒 _𝜏𝜏 ^T �𝒒𝒒 _𝑡𝑡 = 𝑑𝑑 _{𝜏𝜏,𝑡𝑡} .

(12)

𝑑𝑑 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘 ⁾ の評価

1 𝑁𝑁 𝒉𝒉 ^𝜏𝜏−1 ^T 𝒒𝒒 _𝑡𝑡 = 1

𝑁𝑁 𝒉𝒉 ^𝜏𝜏−1 ^T 𝜂𝜂 _𝑡𝑡−1 𝒙𝒙 + 𝒉𝒉 _𝑡𝑡−1 + 𝑜𝑜(1) 𝑑𝑑 _{𝜏𝜏,𝑡𝑡} = 1

𝑁𝑁 �𝒒𝒒 _𝜏𝜏 ^T 𝒒𝒒 _𝑡𝑡 = 𝑐𝑐 _{𝜏𝜏,𝑡𝑡} − 𝜉𝜉 _𝜏𝜏−1

𝑁𝑁 𝒉𝒉 ^𝜏𝜏−1 ^T 𝒒𝒒 _𝑡𝑡

�𝒒𝒒 _𝑡𝑡 = 𝒒𝒒 _𝑡𝑡 − 𝜉𝜉 _𝑡𝑡−1 𝒉𝒉 _𝑡𝑡−1

と定理６.２の性質(B2)を使って、

最後の等号は、以下のためである。

= 𝜉𝜉 _𝑡𝑡−1

𝑁𝑁 𝒉𝒉 ^𝜏𝜏−1 ^T 𝒉𝒉 _𝑡𝑡−1 + 𝑜𝑜 1 = 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _{𝜏𝜏−1,𝑡𝑡−1} ⁰ + 𝑜𝑜(1).

２番目の等号は、定理６.２の性質(B2)から従う。

= 𝑐𝑐 _{𝜏𝜏,𝑡𝑡} − 𝜉𝜉 _𝜏𝜏−1 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _{𝜏𝜏−1,𝑡𝑡−1} ⁰ + 𝑜𝑜(1).

(13)

𝑒𝑒 _𝜏𝜏 ^(𝑘𝑘 ⁾ の評価

𝑒𝑒 _𝜏𝜏 ^(𝑘𝑘) = 1

𝑁𝑁 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝜏𝜏

= 1

𝑁𝑁 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝑰𝑰 − 𝚲𝚲 𝒃𝒃 _𝜏𝜏 + 𝜉𝜉 _𝜏𝜏−1

𝑁𝑁 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 1 + 𝛿𝛿 ⁻¹ 𝑰𝑰 − 𝚲𝚲 � 𝒎𝒎 _𝜏𝜏−1

− 𝜉𝜉 _𝜏𝜏−1

𝑁𝑁𝛿𝛿 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝒃𝒃 _𝜏𝜏−1 − 𝜉𝜉 _𝜏𝜏−1 𝜉𝜉 _𝜏𝜏−2

𝑁𝑁𝛿𝛿 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝜏𝜏−2 + 𝜎𝜎 ² 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜(1).

= 1 + 𝛿𝛿 ⁻¹ 𝜉𝜉 _𝜏𝜏−1 𝑒𝑒 _𝜏𝜏−1 ^(𝑘𝑘) − 𝜉𝜉 _𝜏𝜏−1 𝑒𝑒 _𝜏𝜏−1 ^𝑘𝑘+1 − 𝜉𝜉 _𝜏𝜏−1 𝜉𝜉 _𝜏𝜏−2

𝛿𝛿 𝑒𝑒 _𝜏𝜏−2 ^(𝑘𝑘) + 𝜎𝜎 ² 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 . 1

𝑁𝑁 𝒘𝒘 ^T 𝑼𝑼𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘 = 1

𝑁𝑁 𝔼𝔼 ^𝒘𝒘 Tr 𝚺𝚺𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘𝒘𝒘 ^T 𝑼𝑼 + 𝑜𝑜 1 .

大数の強法則から

= 𝜎𝜎 ²

𝑁𝑁 Tr 𝚲𝚲 ^𝑘𝑘+1 + 𝑜𝑜 1 = 𝜎𝜎 ² 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 .

したがって、

(14)

AMP 状態発展方程式の簡略化

変数変換

𝑥𝑥 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = �𝑥𝑥 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) �

𝜏𝜏

^′

=0 𝜏𝜏−1

𝜉𝜉 _𝜏𝜏

^′

�

𝑡𝑡

^′

=0 𝑡𝑡−1

𝜉𝜉 _𝑡𝑡

^′

, 𝑥𝑥 = 𝑎𝑎, 𝑏𝑏 , 𝑐𝑐, 𝑑𝑑,

ただし、

∏ _𝑡𝑡 ⁻¹

^′

₌₀ 𝜉𝜉 _𝑡𝑡

^′

= 1

と定義する。

̃𝑒𝑒 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 𝑒𝑒 _𝜏𝜏 ^𝑘𝑘

∏ _𝜏𝜏 𝜏𝜏−1

′

=0 𝜉𝜉 _𝜏𝜏

^′

∏ _𝑡𝑡 𝑡𝑡−1

′

=0 𝜉𝜉 _𝑡𝑡

^′

,

状態発展方程式から、

{𝜉𝜉 _𝜏𝜏 }

を消去する。

�𝜎𝜎 _{𝜏𝜏,𝑡𝑡} ² = 𝜎𝜎 ²

∏ _𝜏𝜏 𝜏𝜏−1

′

=0 𝜉𝜉 _𝜏𝜏

^′

∏ _𝑡𝑡 𝑡𝑡−1

′

=0 𝜉𝜉 _𝑡𝑡

^′

,

(15)

簡略化された AMP 状態発展方程式

�𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ �𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘 − �𝑎𝑎 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘+1 − 𝛿𝛿 ⁻¹ �𝑎𝑎 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘

�𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ �𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^(𝑘𝑘) − �𝑏𝑏 _{𝜏𝜏,𝑡𝑡−1} ^𝑘𝑘+1 − 𝛿𝛿 ⁻¹ �𝑏𝑏 _{𝜏𝜏,𝑡𝑡−2} ^𝑘𝑘

添え字が負の場合の変数は、すべて

0

と定義する。

̃𝑑𝑑 _{𝜏𝜏,𝑡𝑡} = _{𝜏𝜏,𝑡𝑡} ̃𝑐𝑐 − �𝑎𝑎 _{𝜏𝜏−1,𝑡𝑡−1} ⁰ ,

+ �𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^𝑘𝑘 − �𝑏𝑏 _{𝑡𝑡,𝜏𝜏} ^𝑘𝑘+1 − 𝛿𝛿 �𝑏𝑏 _{𝑡𝑡−1,𝜏𝜏} ^𝑘𝑘 + ̃𝑒𝑒 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) ,

+ 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 ̃𝑑𝑑 _{𝜏𝜏,𝑡𝑡} − 𝛿𝛿 ⁻¹ 𝜇𝜇 _𝑘𝑘 ̃𝑑𝑑 _{𝜏𝜏,𝑡𝑡−1} ,

̃𝑒𝑒 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1 + 𝛿𝛿 ⁻¹ ̃𝑒𝑒 _{𝜏𝜏−1,𝑡𝑡} ^𝑘𝑘 − ̃𝑒𝑒 _{𝜏𝜏−1,𝑡𝑡} ^𝑘𝑘+1 − 𝛿𝛿 ⁻¹ ̃𝑒𝑒 _{𝜏𝜏−2,𝑡𝑡} ^𝑘𝑘 + 𝜇𝜇 _𝑘𝑘+1 �𝜎𝜎 _{𝜏𝜏,𝑡𝑡} ² .

�𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘)

と

�𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘)

はそれぞれ

(𝑡𝑡 + 𝑘𝑘 + 2)

次と

(𝑡𝑡 + 𝑘𝑘 + 1)

次までの

モーメント

{𝜇𝜇 _𝑘𝑘

^′

}

のみに依存する。

(16)

母関数

𝐺𝐺 𝑦𝑦, 𝑧𝑧 = �

𝜏𝜏=0

∞

�

𝑡𝑡=0

∞

𝑦𝑦 ^𝜏𝜏 𝑧𝑧 ^𝑡𝑡 �𝑔𝑔 _{𝜏𝜏,𝑡𝑡} ,

母関数が満たす代数方程式

𝐴𝐴 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 = 1 + 1

𝛿𝛿 𝑧𝑧𝐴𝐴 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 − 𝑧𝑧

𝑥𝑥 𝐴𝐴 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 − 𝐴𝐴(𝑦𝑦, 𝑧𝑧)

− 𝑧𝑧 ²

𝛿𝛿 𝐴𝐴 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 + 1 − 1 𝑥𝑥 −

𝑧𝑧

𝛿𝛿 𝐵𝐵 𝑥𝑥 , 𝑧𝑧, 𝑦𝑦 + 𝐸𝐸 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 , 𝐺𝐺 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = �

𝑘𝑘=0

∞

�

𝜏𝜏=0

∞

�

𝑡𝑡=0

∞

𝑥𝑥 ^𝑘𝑘 𝑦𝑦 ^𝜏𝜏 𝑧𝑧 ^𝑡𝑡 �𝑔𝑔 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) . 𝑔𝑔 = 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑, 𝑒𝑒, 𝜎𝜎 ²

に対して、

𝐴𝐴 𝑦𝑦, 𝑧𝑧 = lim _𝑥𝑥→0 𝐴𝐴(𝑥𝑥, 𝑦𝑦, 𝑧𝑧) .

ただし、

(17)

母関数が満たす代数方程式

𝐷𝐷 𝑦𝑦, 𝑧𝑧 = 𝐶𝐶 𝑦𝑦, 𝑧𝑧 − 𝑦𝑦𝑧𝑧𝐴𝐴 𝑦𝑦, 𝑧𝑧 ,

定理６.１前半から得られる

_𝑥𝑥→0 lim 𝐵𝐵 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 0

を使うと、

𝐵𝐵(𝑥𝑥 , 𝑦𝑦, 𝑧𝑧) = 1 + 1

𝛿𝛿 𝑧𝑧𝐵𝐵 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧) − 𝑧𝑧

𝑥𝑥 𝐵𝐵 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 − 𝑧𝑧 ²

𝛿𝛿 𝐵𝐵 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 + 𝜂𝜂 −𝑥𝑥 − 1

𝑥𝑥 𝜂𝜂 −𝑥𝑥 − 1 − 𝑧𝑧𝜂𝜂(−𝑥𝑥)

𝛿𝛿 𝐷𝐷(𝑦𝑦, 𝑧𝑧),

𝐸𝐸(𝑥𝑥, 𝑦𝑦, 𝑧𝑧) = 1 + 1

𝛿𝛿 𝑦𝑦𝐸𝐸 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧 ) − 𝑦𝑦

𝑥𝑥 {𝐸𝐸 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 − 𝐸𝐸 𝑦𝑦, 𝑧𝑧 }

− 𝑦𝑦 ²

𝛿𝛿 𝐸𝐸 (𝑥𝑥 , 𝑦𝑦, 𝑧𝑧) + Σ ² 𝑦𝑦, 𝑧𝑧

𝑥𝑥 {𝜂𝜂 −𝑥𝑥 − 1}.

定理６.１の仮定から、

{𝜇𝜇 _𝑘𝑘 }

はMP分布のモーメント系列に一致すると仮定して、一般性を失わない。

(18)

母関数が満たす代数方程式

𝐵𝐵 𝑥𝑥, 𝑧𝑧, 𝑦𝑦 = 𝛿𝛿𝑥𝑥𝜂𝜂 −𝑥𝑥 − 𝛿𝛿 𝜂𝜂 −𝑥𝑥 − 1 − 𝑥𝑥𝑦𝑦𝜂𝜂 −𝑥𝑥

𝛿𝛿𝑦𝑦 + 𝑦𝑦 − 𝛿𝛿 𝑦𝑦 − 1 𝑥𝑥 𝐷𝐷 𝑦𝑦, 𝑧𝑧 ,

𝐴𝐴 𝑥𝑥 , 𝑦𝑦, 𝑧𝑧 = 𝛿𝛿𝑧𝑧𝐴𝐴 𝑦𝑦, 𝑧𝑧 + 𝛿𝛿𝑥𝑥 − 𝛿𝛿 − 𝑥𝑥𝑧𝑧 𝐵𝐵 𝑥𝑥, 𝑧𝑧, 𝑦𝑦 + 𝛿𝛿𝑥𝑥𝐸𝐸(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)

𝛿𝛿𝑧𝑧 + 𝑧𝑧 − 𝛿𝛿 𝑧𝑧 − 1 𝑥𝑥 ,

𝐷𝐷 𝑦𝑦, 𝑧𝑧 = 𝐶𝐶 𝑦𝑦, 𝑧𝑧 − 𝑦𝑦𝑧𝑧𝐴𝐴 𝑦𝑦, 𝑧𝑧 . 𝐷𝐷 𝑧𝑧, 𝑦𝑦 = 𝐷𝐷(𝑦𝑦, 𝑧𝑧)

を使用すると、

𝐸𝐸 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝛿𝛿𝑦𝑦𝐸𝐸 𝑦𝑦, 𝑧𝑧 + 𝛿𝛿Σ ² 𝑦𝑦, 𝑧𝑧 {𝜂𝜂 −𝑥𝑥 − 1}

𝛿𝛿𝑦𝑦 + 𝑦𝑦 − 𝛿𝛿 𝑦𝑦 − 1 𝑥𝑥 .

以下の関係式を証明する。

𝐴𝐴 𝑦𝑦, 𝑧𝑧 = Σ ² 𝑦𝑦, 𝑧𝑧 + 1

𝛿𝛿 𝐶𝐶 𝑦𝑦 , 𝑧𝑧 .

(19)

母関数の評価

𝑥𝑥 ^∗ = 𝛿𝛿𝑧𝑧

(𝑧𝑧 − 𝛿𝛿 )(𝑧𝑧 − 1) .

𝐴𝐴(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)

は解析的なので、

𝐴𝐴(𝑥𝑥 , 𝑦𝑦, 𝑧𝑧)

の分母

𝑄𝑄 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧)

が

0

のとき、

分子

𝑃𝑃(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)

も

0

にならなければならない。

𝑄𝑄 −𝑥𝑥 ^∗ , 𝑦𝑦, 𝑧𝑧 = 0.

𝑃𝑃 −𝑥𝑥 ^∗ , 𝑦𝑦, 𝑧𝑧 = 0

より、

𝐴𝐴 𝑦𝑦, 𝑧𝑧 = − 𝐵𝐵 −𝑥𝑥 ^∗ , 𝑧𝑧, 𝑦𝑦

𝑧𝑧 𝑧𝑧 − 1 + 𝛿𝛿𝐸𝐸 (−𝑥𝑥 ^∗ , 𝑦𝑦, 𝑧𝑧) (𝑧𝑧 − 𝛿𝛿)(𝑧𝑧 − 1) .

定理６.１の証明で示した

𝜂𝜂 −𝑥𝑥 ^∗ = 1 − 𝑧𝑧

を使うと、

𝐵𝐵 −𝑥𝑥 ^∗ , 𝑧𝑧, 𝑦𝑦 = 𝑧𝑧(𝑧𝑧 − 1)

𝑦𝑦𝑧𝑧 − 𝛿𝛿 {𝐶𝐶 𝑦𝑦, 𝑧𝑧 − 𝑦𝑦𝑧𝑧𝐴𝐴 𝑦𝑦, 𝑧𝑧 }.

𝐸𝐸 −𝑥𝑥 ^∗ , 𝑦𝑦, 𝑧𝑧 = 𝑧𝑧 − 𝛿𝛿 𝑧𝑧 − 1 𝑦𝑦𝐸𝐸 𝑦𝑦, 𝑧𝑧 − 𝑧𝑧Σ ² 𝑦𝑦, 𝑧𝑧

(𝑦𝑦𝑧𝑧 − 𝛿𝛿 )(𝑧𝑧 − 𝑦𝑦) .

(20)

母関数の評価

𝐴𝐴 𝑦𝑦, 𝑧𝑧 = Σ ² 𝑦𝑦, 𝑧𝑧 + 1

𝛿𝛿 𝐶𝐶 𝑦𝑦 , 𝑧𝑧 . 𝐸𝐸(𝑥𝑥, 𝑦𝑦, 𝑧𝑧 )

は解析的なので、

𝐸𝐸(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)

の分母が

0

のとき、

分子も

0

にならなければならない。

𝑥𝑥 ^∗∗ = 𝛿𝛿𝑦𝑦/(𝑦𝑦 − 𝛿𝛿)(𝑦𝑦 − 1)

とすると、

𝜂𝜂 𝑥𝑥 ^∗∗ = 1 − 𝑦𝑦

なので、

𝐸𝐸 𝑦𝑦, 𝑧𝑧 = Σ ² 𝑦𝑦, 𝑧𝑧 .

したがって、

𝐸𝐸 −𝑥𝑥 ^∗ , 𝑦𝑦, 𝑧𝑧 = − 𝑧𝑧 − 𝛿𝛿 𝑧𝑧 − 1

𝑦𝑦𝑧𝑧 − 𝛿𝛿 Σ ² 𝑦𝑦, 𝑧𝑧 .

以上の結果をまとめると、

(21)

定理６ . ２後半の証明

定理６.２の性質(B2)から

1 𝑁𝑁 𝒒𝒒 ^𝑡𝑡+1 ² = 1

𝑁𝑁 𝔼𝔼 𝜂𝜂 ^𝑡𝑡 𝒙𝒙 + �𝒉𝒉 _𝑡𝑡 − 𝒙𝒙 ² + 𝑜𝑜 1 .

�𝒉𝒉 _𝑡𝑡

は

𝔼𝔼 �𝒉𝒉 _𝑡𝑡 �𝒉𝒉 _𝑡𝑡 ^T = 𝑁𝑁 ⁻¹ 𝒎𝒎 � _𝑡𝑡 ² 𝑰𝑰 _𝛿𝛿

を満たす平均

0

のガウス分布に従う。

定義から、大システム極限で以下を証明した。

1 𝑁𝑁 𝒎𝒎 � _𝑡𝑡 ² = 𝜎𝜎 ² + 1

𝛿𝛿𝑁𝑁 𝒒𝒒 ^𝑡𝑡 ² + 𝑜𝑜(1).

これは発見的に導出されたAMPの状態発展方程式が正しいことを意味している。

定理６ . １前半の証明のスケッチ

AMP

定理６ . １前半の証明のスケッチ

𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 〈𝚲𝚲 𝑘𝑘 𝜕𝜕 𝑡𝑡

𝒎𝒎 � 𝑡𝑡 〉

𝑡𝑡 = 0

𝑡𝑡 = 1

0 ≤ 𝑡𝑡 < 𝜏𝜏

0 ≤ 𝑡𝑡 ′ ≤ 𝑡𝑡

𝑔𝑔 𝑡𝑡 (0)

,𝑡𝑡 a.s.

0

1 < 𝜏𝜏 < 𝑇𝑇

𝑔𝑔 𝑡𝑡 (0)

,𝜏𝜏 a.s.

0

𝑡𝑡 < 𝜏𝜏

𝜉𝜉 𝑡𝑡

𝑔𝑔 𝑡𝑡 (0)

,𝑡𝑡 a.s.

0

𝑡𝑡

システムの簡単化

{𝑎𝑎 𝑡𝑡 }

𝑎𝑎 0 = 1

𝑎𝑎 𝑡𝑡 = 𝜉𝜉 𝑡𝑡−1 𝑎𝑎 𝑡𝑡−1

𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝑎𝑎 𝑡𝑡 �𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡

�

𝑚𝑚 𝑡𝑡

𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡

𝑡𝑡 ′ < 𝑡𝑡 − 1

𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝜉𝜉 𝑡𝑡−1 1 + 1

𝛿𝛿 𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡−1 − 𝜉𝜉 𝑡𝑡−1 𝑔𝑔 𝑡𝑡 𝑘𝑘+1

,𝑡𝑡−1 − 𝜉𝜉 𝑡𝑡−1 𝜉𝜉 𝑡𝑡−2

𝛿𝛿 𝑔𝑔 𝑡𝑡 𝑘𝑘

,𝑡𝑡−2 + 𝑜𝑜(1).

�𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 1 + 1

𝛿𝛿 �𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡−1 − �𝑔𝑔 𝑡𝑡

𝑘𝑘+1 ,𝑡𝑡−1 − 1

𝛿𝛿 �𝑔𝑔 𝑡𝑡 𝑘𝑘

,𝑡𝑡−2 + 𝑜𝑜(1).

𝑡𝑡 ′ = 𝑡𝑡

𝑡𝑡 ′ = 𝑡𝑡 − 1

�𝑔𝑔 𝑡𝑡,𝑡𝑡 (𝑘𝑘) = 𝜇𝜇 𝑘𝑘 − 𝜇𝜇 𝑘𝑘+1 + 𝑜𝑜 1 , 𝜇𝜇 𝑘𝑘 = lim 𝑀𝑀=𝛿𝛿𝛿𝛿→∞ 1

𝑁𝑁 Tr Λ 𝑘𝑘 .

�𝑔𝑔 𝑡𝑡−1,𝑡𝑡 (𝑘𝑘) = − 𝜇𝜇 𝑘𝑘+1

𝛿𝛿 + �𝑔𝑔 𝑡𝑡−1,𝑡𝑡−1 𝑘𝑘 − �𝑔𝑔 𝑡𝑡−1,𝑡𝑡−1 𝑘𝑘+1 + 𝑜𝑜 1 .

解の構造解析

�𝑔𝑔 𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝑔𝑔 𝑡𝑡−𝑡𝑡 (𝑘𝑘)

𝑔𝑔 0 (𝑘𝑘) = 𝜇𝜇 𝑘𝑘 − 𝜇𝜇 𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 1 (𝑘𝑘) = − 𝜇𝜇 𝑘𝑘+1

𝛿𝛿 + 𝑔𝑔 0 𝑘𝑘 − 𝑔𝑔 0 𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 𝑡𝑡 (𝑘𝑘) = 1 + 1

𝛿𝛿 𝑔𝑔 𝑡𝑡−1 (𝑘𝑘) − 𝑔𝑔 𝑡𝑡−1 𝑘𝑘+1 − 1

𝛿𝛿 𝑔𝑔 𝑡𝑡−2 𝑘𝑘 + 𝑜𝑜(1).

𝑡𝑡 ≤ 𝜏𝜏 < 𝑇𝑇

𝑔𝑔 𝑡𝑡 (0) 𝑎𝑎.𝑠𝑠. 0

𝑔𝑔 𝑡𝑡 (𝑘𝑘)

𝑡𝑡 + 𝑘𝑘 + 1

{𝜇𝜇 𝑘𝑘

}

𝑔𝑔 𝜏𝜏 (0)

𝜏𝜏 + 1 ≤ 𝑇𝑇

母関数

𝐺𝐺 𝑥𝑥, 𝑦𝑦 = �

𝑡𝑡=0

∞

𝐺𝐺 𝑡𝑡 (𝑥𝑥 ) 𝑦𝑦 𝑡𝑡 ,

{𝜇𝜇 𝑘𝑘 }

𝑔𝑔 −1 (0) = 0.

𝐺𝐺 𝑡𝑡 𝑥𝑥 = �

𝑘𝑘=0

∞

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 〈𝚲𝚲 ^𝑘𝑘 𝜕𝜕 _𝑡𝑡

𝒎𝒎 � _𝑡𝑡 〉

0 ≤ 𝑡𝑡 ^′ ≤ 𝑡𝑡

𝑔𝑔 _𝑡𝑡 (0)

𝑔𝑔 _𝑡𝑡 (0)

𝜉𝜉 _𝑡𝑡

𝑔𝑔 _𝑡𝑡 (0)

{𝑎𝑎 _𝑡𝑡 }

𝑎𝑎 ₀ = 1

𝑎𝑎 _𝑡𝑡 = 𝜉𝜉 _𝑡𝑡−1 𝑎𝑎 _𝑡𝑡−1

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝑎𝑎 _𝑡𝑡 �𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

𝑚𝑚 _𝑡𝑡

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

𝑡𝑡 ^′ < 𝑡𝑡 − 1

𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝜉𝜉 _𝑡𝑡−1 1 + 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡 ^(𝑘𝑘)

^{,𝑡𝑡−1} − 𝜉𝜉 _𝑡𝑡−1 𝑔𝑔 _𝑡𝑡 𝑘𝑘+1

,𝑡𝑡−1 − 𝜉𝜉 _𝑡𝑡−1 𝜉𝜉 _𝑡𝑡−2

𝛿𝛿 𝑔𝑔 _𝑡𝑡 𝑘𝑘

�𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

𝛿𝛿 �𝑔𝑔 ^𝑡𝑡 ^(𝑘𝑘)

^{,𝑡𝑡−1} − �𝑔𝑔 _𝑡𝑡

^𝑘𝑘+1 _{,𝑡𝑡−1} − 1

𝛿𝛿 �𝑔𝑔 ^𝑡𝑡 ^𝑘𝑘

^{,𝑡𝑡−2} + 𝑜𝑜(1).

𝑡𝑡 ^′ = 𝑡𝑡

𝑡𝑡 ^′ = 𝑡𝑡 − 1

�𝑔𝑔 _{𝑡𝑡,𝑡𝑡} ^(𝑘𝑘) = 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 , 𝜇𝜇 _𝑘𝑘 = lim _{𝑀𝑀=𝛿𝛿𝛿𝛿→∞} 1

𝑁𝑁 Tr Λ ^𝑘𝑘 .

�𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡} ^(𝑘𝑘) = − 𝜇𝜇 _𝑘𝑘+1

𝛿𝛿 + �𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡−1} ^𝑘𝑘 − �𝑔𝑔 _{𝑡𝑡−1,𝑡𝑡−1} ^𝑘𝑘+1 + 𝑜𝑜 1 .

�𝑔𝑔 _𝑡𝑡 (𝑘𝑘)

,𝑡𝑡 = 𝑔𝑔 _{𝑡𝑡−𝑡𝑡} (𝑘𝑘)

𝑔𝑔 ₀ ^(𝑘𝑘) = 𝜇𝜇 _𝑘𝑘 − 𝜇𝜇 _𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 ₁ ^(𝑘𝑘) = − 𝜇𝜇 _𝑘𝑘+1

𝛿𝛿 + 𝑔𝑔 ₀ ^𝑘𝑘 − 𝑔𝑔 ₀ ^𝑘𝑘+1 + 𝑜𝑜 1 , 𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘) = 1 + 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡−1 ^(𝑘𝑘) − 𝑔𝑔 _𝑡𝑡−1 ^𝑘𝑘+1 − 1

𝛿𝛿 𝑔𝑔 ^𝑡𝑡−2 ^𝑘𝑘 + 𝑜𝑜(1).

𝑔𝑔 _𝑡𝑡 ⁽⁰⁾ ^{𝑎𝑎.𝑠𝑠.} 0

𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘)

{𝜇𝜇 _𝑘𝑘

𝑔𝑔 _𝜏𝜏 ⁽⁰⁾

𝐺𝐺 _𝑡𝑡 (𝑥𝑥 ) 𝑦𝑦 ^𝑡𝑡 ,

{𝜇𝜇 _𝑘𝑘 }

𝑔𝑔 ₋₁ ⁽⁰⁾ = 0.

𝐺𝐺 _𝑡𝑡 𝑥𝑥 = �

𝑔𝑔 _𝑡𝑡 ^(𝑘𝑘) 𝑥𝑥 ^𝑘𝑘 − 𝑔𝑔 _𝑡𝑡−1 ⁰ 𝑥𝑥 ,

𝑔𝑔 _𝑡𝑡 ⁽⁰⁾ ^{𝑎𝑎.𝑠𝑠.} 0

𝑔𝑔 _𝑡𝑡−1 ⁽⁰⁾ ^a.s. 0

_𝑥𝑥→0 lim 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 0

𝜂𝜂 𝑥𝑥 = ∑ _𝑘𝑘=0 ^∞ −𝑥𝑥 ^𝑘𝑘 𝜇𝜇 _𝑘𝑘

𝐺𝐺 ₀ 𝑥𝑥 = 𝜂𝜂 −𝑥𝑥 − 𝜂𝜂 −𝑥𝑥 − 𝜇𝜇 ₀

𝐺𝐺 ₁ 𝑥𝑥 = − 𝜂𝜂 −𝑥𝑥 − 1

𝑥𝑥 𝐺𝐺 ⁰ 𝑥𝑥 + 𝑜𝑜 1 , 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 1 + 1

𝑥𝑥 𝐺𝐺 ^𝑡𝑡−1 𝑥𝑥 − 𝐺𝐺 _𝑡𝑡−2 𝑥𝑥

𝐺𝐺 𝑥𝑥, 𝑦𝑦 = 𝐺𝐺 ₀ 𝑥𝑥 + 𝑦𝑦𝐺𝐺 ₁ 𝑥𝑥 + 1 + 1 𝛿𝛿 −

𝑥𝑥 𝑦𝑦 𝐺𝐺 𝑥𝑥 , 𝑦𝑦 − 𝐺𝐺 ₀ 𝑥𝑥

− 𝑦𝑦 ²

𝜇𝜇 ₀ = 1,

𝑥𝑥→0 lim 𝐺𝐺 _𝑡𝑡 𝑥𝑥 = 0

𝑄𝑄 −𝑥𝑥 ^∗ , 𝑦𝑦 = 0

−𝑥𝑥 ^∗

𝑥𝑥 ^∗ = 𝛿𝛿𝑦𝑦

−𝑥𝑥 ^∗

𝑃𝑃 −𝑥𝑥 ^∗ , 𝑦𝑦 = 0

𝑃𝑃 −𝑥𝑥 ^∗ , 𝑦𝑦 = 𝛿𝛿 1 − 𝜂𝜂 𝑥𝑥 ^∗

𝑥𝑥 ^∗

𝜂𝜂 𝑥𝑥 ^∗ − 𝑦𝑦 − 𝛿𝛿

𝑦𝑦 𝜂𝜂 𝑥𝑥 ^∗ − 1 − 𝑦𝑦 = 0.

𝜂𝜂 𝑥𝑥 ^∗ = 1 − 𝑦𝑦.

𝑥𝑥 ^∗ 𝜂𝜂 ² 𝑥𝑥 ^∗ + 𝛿𝛿𝑥𝑥 ^∗ − 𝑥𝑥 ^∗ + 𝛿𝛿 𝜂𝜂 𝑥𝑥 ^∗ − 𝛿𝛿 = 0

𝑎𝑎 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒎𝒎 � _𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡 , 𝑏𝑏 _{𝜏𝜏,𝑡𝑡} ^(𝑘𝑘) = 1

𝑁𝑁 𝒃𝒃 ^𝜏𝜏 ^T 𝚲𝚲 ^𝑘𝑘 𝒎𝒎 � _𝑡𝑡 , 𝑐𝑐 _{𝜏𝜏,𝑡𝑡} = 1

𝑁𝑁 𝒒𝒒 ^𝜏𝜏 ^T 𝒒𝒒 _𝑡𝑡 ,

𝑑𝑑 _{𝜏𝜏,𝑡𝑡} = 1

𝑁𝑁 �𝒒𝒒 _𝜏𝜏 ^T �𝒒𝒒 _𝑡𝑡 , 𝑒𝑒 _𝑡𝑡 ^(𝑘𝑘) = 1

𝑁𝑁 𝒎𝒎 � _𝑡𝑡 ^T 𝚲𝚲 ^𝑘𝑘 𝚺𝚺 ^T 𝑼𝑼 ^T 𝒘𝒘.