1 - WEB PARK 2014

EFKP 型の重複対数法則のゲーム論的証明
笹井健行 (東大情報理工)
宮部賢志 (明治大理工)
竹村彰通 (東大情報理工)
2014 年 9 月 26 日日本数学会広島大学
原稿
“A game-theoretic proof of
Erdos-Feller-Kolmogorov-Petrowsky law of the
iterated logarithm for fair-coin tossing”
T.Sasai, K.Miyabe and A.Takemura
arXiv:1408.1790
1
項目
1. EFKP 形式の重複対数の法則
2. ゲーム論的確率論の枠組み
3. 証明の概略
4. まとめと今後の課題
2
EFKP 形式の重複対数の法則
(EFKP-LIL)
コイン投げの場合の通常の LIL (A.Khintchin(1924))
• P (Xi = +1) = P (Xi = −1) = 1/2，独立，
∑n
Sn = i=1 Xi .
Sn
lim inf √
= −1, a.s.
n
2n ln ln n
Sn
= 1,
lim sup √
n
2n ln ln n
3
• Sn についてもっと詳しい挙動が知りたい．
→ 比でなく差の形で考える．
• 用語 (L´
evy)
– ψ(n) が upper class に属する:
√
P(Sn > nψ(n) i.o.) = 0.
– ψ(n) が lower class に属する:
√
P(Sn > nψ(n) i.o.) = 1.
4
• Kolmogorov-Erd˝
os の LIL (Erd˝
os(1942))


∫ ∞
Upper
ψ(t) −ψ(t)2 /2 < ∞
ψ(t) ∈
if
e
dt
Lower
= ∞
t
• 任意の k > 0 に対して lnk t = ln
. . . ln} t とおく．
| ln{z
ktimes
• 次の形の ψ(t) を考える．
√
2 ln ln t + 3 ln ln ln t + 2 ln4 t + · · · + (2 + ϵ) lnk t
• 上の積分の条件により
ϵ > 0: upper class, ϵ ≤ 0: lower class
5
• これは以下の積分の収束・発散より従う．

∫ ∞
< ∞, ϵ > 0
1
dt
(1+ϵ/2)
= ∞, ϵ ≤ 0
t ln t ln2 t . . . lnk−1
• 以上は測度論での結果だが，これをゲーム論的確率の
設定で考える．
6
ゲーム論的確率論の枠組み
• プロトコル (Fair-Coin Game)
K0 := 1.
FOR n = 1, 2, . . .:
Skeptic announces Mn ∈ R.
Reality announces xn ∈ {−1, 1}.
Kn := Kn−1 + Mn xn .
Collateral Duty:
Skeptic は破産してはいけない
(Kn ≥ 0).
• path: x1 x2 . . .
(Reality の手の無限列)
• 標本空間: Ω = {−1, 1}∞
7
(path の全体)
• 事象: E ⊂ Ω
• “Skeptic can force E”
lim Kn = ∞, ∀x1 x2 · · · ̸∈ E
n
となるような Skeptic の戦略が存在する．
•
∫
∞
I(ψ) =
1
とおく．
8
ψ(t) −ψ(t)2 /2
e
dt
t
定理 1. ψ(t) > 0, t ≥ 1 を単調非減少連続関数とする．
Fair-Coin Game において
√
I(ψ) < ∞ ⇒ Skeptic can force Sn < nψ(n) a.a. (1)
√
(2)
I(ψ) = ∞ ⇒ Skeptic can force Sn ≥ nψ(n) i.o.
• (1) 式を validity, (2) 式を sharpness と言う．
• ゲーム論的な結果は測度論的な結果を含意する．
9
証明の概略
• validity, sharpness それぞれを force する戦略を構
成する．
• 戦略の構成には，残高の一定割合を賭ける戦略の
mixture を利用．Bayes 戦略とよぶ．
• 戦略は ψ に依存する．
• validity の証明はやさしい (証明 2 ページ程度)．
• sharpness の証明は長いが，初等的かつ明示的 (10
ページ以上)
10
Validity の証明
• 積分の離散化
∞
∑
ψ(k)
k
k=1
e
−ψ(k)2 /2
<∞
• 賭け比率 γ を一定とする戦略:
Mn = γKn−1
• この戦略の資金過程:
Knγ =
n
∏
i=1
11
(1 + γxi )
• ak ↑ ∞ で以下の性質を満たすものを選ぶ
∞
∑
ψ(k) −ψ(k)2 /2
ak
e
= Z < ∞.
k
k=1
• pk , γk を次のようにおく
1 ψ(k) −ψ(k)2 /2
pk = ak
e
,
Z
k
ψ(k)
γk = √
k
• validity を強制する mixture 戦略:
Kn =
∞
∑
k=1
12
pk Knγk ,
Sharpness の証明の流れ
• Shafer and Vovk (2001) の本の第 5 章，Miyabe
and Takemura (2013) と同様に 3 つの戦略を組み合
わせる．
• 1 つの戦略を「売り」，両側からヘッジする (破産を防
ぐ) ため 2 つの戦略を「買う」．
13
• さらに，時間軸を C k ln k , k = 1, 2, . . . , のように指数間
隔の時間よりやや長い時間で区切り，各区間で 3 つの
戦略の組み合わせを用いる．(C はある程度大きい．)
√
• 各区間の終点で， nψ(n) より Sn が小さいならば，
売った戦略により Skeptic が儲ける．
• それぞれの戦略は，賭け比率一定戦略 Knγ の次のよう
な連続混合を用いる．
∫ ln k ∫ 1
1
uC −w γ
Kn
dudw
ln k 0
0
14
まとめと今後の課題
• ゲーム論的確率論では，比で考える LIL の証明は存在
した．
• EFKP 形式の LIL は今回が初めて．
• ゲーム論的確率論において EFKP 形式の LIL を扱う
基礎ができた．
15
今後の課題
• EFKP 形式の重複対数の法則は，コイン投げ以外の
様々な条件の下で成り立つ．ゲーム論での証明におい
ては，ほぼコイン投げの場合に帰着させられる．
• ψ(n) が事前に定まらず動的に定まる場合に同様の結果
が成り立つか．より具体的には第 3 の player である
Forecaster が ψ(n) を各ラウンドで宣言する場合に同
様の結果が成り立つか，がゲーム論的には興味が持た
れる．
• 測度論的確率論で議論されている self-normalized
sums の場合への拡張
16
References
[1] P. Erd˝
os. On the law of the iterated logarithm.
Annals of Mathematics, Second Series,
43:419–436, 1942.
¨
[2] A. Khinchine. Uber
einen Satz der
Wahrscheinlichkeitsrechnung. Fundamenta
Mathematica, 6:9–20, 1924.
[3] K. Miyabe and A. Takemura. The law of the
iterated logarithm in game-theoretic probability
with quadratic and stronger hedges. Stochastic
Process. Appl., 123(8):3132–3152, 2013.
17

Download Report