Prediction in the dark #3

1回目：Prediction in the dark #1

2回目：Prediction in the dark #2

Prediction in the darkの3回目。前回示したアルゴリズムによって予測確率がどのように変化するのかを解析的に求めていく。$n$日目までに自分が間違えた回数を$w$とし、最優秀トレーダー$i'$が予測を間違えた回数を$w'$とする。このときの$w$と$w'$の関係がどのようになっていくのかを解析する。

$t$日目の時点での全トレーダーの重みの合計を$S(t)$とする。

$$\begin{eqnarray} S(t)=\sum_i m(i, t) \end{eqnarray}$$
自分の予測は全トレーダーによる“上がる”または“下がる”の多数決で決めるため、正答を出したグループと誤答を出したグループに別れる。
$$\begin{eqnarray} \frac{S(t)}{2}+\frac{\beta S(t)}{2} \end{eqnarray}$$
予測を間違えたグループは$t$日目よりも$t+1$日目の方が$S$の値が小さくなるので、
$$\begin{eqnarray} S(t+1)&\le& \frac{1+\beta}{2}S(t) \end{eqnarray}$$
が成り立つ。$S(1)=M$なので、自分が$w$回間違えた$n$日目は、
$$\begin{eqnarray} S(n)\le \Bigl(\frac{1+\beta}{2}\Bigr)^w M \end{eqnarray}$$

となる。最優秀トレーダー$i'$の重みは、$w'$回間違えているので、
$$\begin{eqnarray} m(i', n)=\beta^{w'} \end{eqnarray}$$
である。$n$日目での自分の重みと最優秀トレーダー$i'$の重みを整理すると、
$$\begin{eqnarray} S(n)=\sum_i m(i, n)\\ m(i', n)=\beta^{w'} \end{eqnarray}$$
式$(6), (7)$より、$m(i, t)$が全て正の数であることから、和である$S(n)$の方が大きい。すなわち、
$$\begin{eqnarray} \sum_i m(i, n) \ge m(i', n) \end{eqnarray}$$
である。ここで、式$(4), (5), (6), (8)$から、
$$\begin{eqnarray} \beta^{w'} \le \Bigl(\frac{1+\beta}{2}\Bigr)^w M \end{eqnarray}$$
という関係が導き出される。式$(9)$を$w$と$w'$について解く。
$$\begin{eqnarray} w'\log \beta &\le& w\log \Bigl(\frac{1+\beta}{2}\Bigr)+\log M\\ w&\le& \frac{w'\log\beta -\log M}{\log (\frac{1+\beta}{2})}\\ &\le& \frac{w'\log\beta}{\log (\frac{1+\beta}{2})}-\frac{\log M}{\log (\frac{1+\beta}{2})} \end{eqnarray}$$
ここで、$\frac{\log M}{\log (\frac{1+\beta}{2})}$は試行回数に依存しないため、$w$や$w'$が十分に大きければ無視出来る程度の項である。次に、$\beta \rightarrow1$である場合を考える。
$$\begin{eqnarray} \lim_{\beta \rightarrow1}\frac{\log\beta}{\log(\frac{1+\beta}{2})} \end{eqnarray}$$
式$(13)$は不定形となっているため、$\log \beta$および$\log (\frac{1+\beta}{2})$を$1$の回りでtaylor展開すると$\log \beta$は、
$$\begin{eqnarray} \log\beta&=&\beta-1-\frac{(\beta-1)^2}{2}+\frac{(\beta-1)^3}{3}\cdots\\ &=&(\beta-1)\Biggl\{1-\frac{\beta-1}{2}+\frac{(\beta-1)^2}{3}\cdots\\ \end{eqnarray}$$

となり、$\log (\frac{1+\beta}{2})$は、
$$\begin{eqnarray} \log\Bigl(\frac{1+\beta}{2}\Bigr)&=&\frac{\beta-1}{2}-\frac{(\beta-1)^2}{8}+\frac{(\beta-1)^3}{24}\cdots\\ &=&(\beta-1)\Biggl\{\frac{1}{2}-\frac{\beta-1}{8}+\frac{(\beta-1)^2}{24}\cdots \end{eqnarray}$$

となる。ここで、$(\beta-1)$が消え、$\beta\rightarrow 1$とすると以下のようになる。
$$\begin{eqnarray} \lim_{\beta \rightarrow1}\frac{\log\beta}{\log(\frac{1+\beta}{2})}=\frac{1}{\frac{1}{2}}=2 \end{eqnarray}$$

よって最終的に、
$$\begin{eqnarray} w\le 2w' \end{eqnarray}$$
が得られる。したがって、自分が予測を外す回数$w$を最優秀トレーダーが予測を外す回数$w'$の$2$倍以下にすることができる。$Q.E.D.$


…いかがでしたでしょうか。試行回数を十分に大きくする必要がありますが、この威力が分かってもらえたと思います。数学の力は凄いですね、こういうことをゼロから考え出せる人は偉大です。


終わり


2014/02/03 3:17 taylor展開が間違っていたので修正しました。