Project Euler 323. Bitwise-OR operations on random integers

この記事の所要時間: 642

No.323 Bitwise-OR operations on random integers

久々のProject Euler は確率・期待値の問題です.高校数学でも使うことのある確率の考え方も出てきます.

問題.

\(y_0, y_1, y_2, \ldots\) をランダムな符号なし32ビット整数とする(つまり,\(0\leq y_i<2^{32}\), 任意の値が同様に確からしく現れるとする).

列\(x_i\)に対して,次の漸化式が与えられている:

  • \(x_0=0\),
  • \(x_i=x_{i-1}|y_{i-1}\), (i>0). (\( | \)はビットごとのORをとる操作)

最終的に,ある添字\(N\)が存在して全ての\(i\geq N\)に対して\(x_i=2^{32}-1\)(すべての桁が1であるビットパターン)となることが分かる.
\(N\)の期待値を求めよ.答えは小数点以下10桁に四捨五入して答えよ.

コンピュータの中では整数は2進法の0と1の列として扱われます.\(1\leq n\leq 2^{32}-1\)を満たす自然数\(n\)は,(左端に0が並ぶことを許すと)32桁の0, 1列で表されます.

\( | \)はビットごと(桁ごと)にOR演算を行う計算です.OR演算は,
\begin{align*}
0 \quad\mathrm{OR}\quad 0 &= 0\\
0 \quad\mathrm{OR}\quad 1 &= 1\\
1 \quad\mathrm{OR}\quad 0 &= 1\\
1 \quad\mathrm{OR}\quad 1 &= 1
\end{align*}

という演算で,1が1個以上あれば答えが1になる演算です.そのため,上の問題は各桁に対してランダムに0または1が与えられて,すべての桁において1が1回以上登場するまでの回数の期待値,と考えることができます.

また,\(N=k\)になる確率\(\mathrm{P}(N=k)\)を直接求めるのは難しいため,\(N\leq k\)となる確率\(Q(k)=\mathrm{P}(N\leq k)\)を求めて,

\begin{align*}
\mathrm{P}(N=k) &= \mathrm{P}(N\leq k) – \mathrm{P}(N \leq k-1)\\
&= Q(k) – Q(k-1)
\end{align*}

として求めます.この考え方は高校数学などの場合の数・確率の分野でも役に立つので知っておいて損はないでしょう.

解説とプログラム例.(c++)

\(x\)の\(j\)桁目(\(j=1, 2, \ldots, 32\))が初めて\(1\)になるときの添字を表す確率変数を\(S_j\)とする.このとき,
\begin{align*}
\mathrm{P}(S_j=i) &= \left(\frac{1}{2}\right)^i\\
\mathrm{P}(S_j\leq i) &= \sum_{k=1}^i \left(\frac{1}{2}\right)^k\\
&= 1-\left(\frac{1}{2}\right)^i.
\end{align*}
このとき,\(x_i=2^{32}-1\)である確率は,
\begin{align*}
\mathrm{P}(x_i=2^{32}-1) &= \mathrm{P}(S_1\leq i, S_2\leq i, \ldots, S_{32}\leq i)\\
&= \mathrm{P}(S_1\leq i)\cdot\mathrm{P}(S_2\leq i)\cdots\mathrm{P}(S_{32}\leq i)\\
&= \left\{1-\left(\frac{1}{2}\right)^i\right\}^{32}.
\end{align*}
よって,\(x_i\)ではじめて\(2^{32}-1\)になる確率(\(N=i\)である確率)は,
\begin{align*}
\mathrm{P}(x_{i-1}\neq 2^{32}-1, x_i=2^{32}-1) &= \left\{1-\left(\frac{1}{2}\right)^i\right\}^{32} – \left\{1-\left(\frac{1}{2}\right)^{i-1}\right\}^{32}\\
&= \sum_{k=0}^{32} \binom{32}{k}(-1)^k\left(\frac{1}{2}\right)^{ik}(1-2^k)\\
&= \sum_{k=1}^{32} \binom{32}{k}(-1)^k\left(\frac{1}{2}\right)^{ik}(1-2^k).
\end{align*}
したがって,\(N\)の期待値は
\begin{align*}
\mathrm{E}[N] &= \sum_{i=1}^{\infty} i \sum_{k=0}^{32} \binom{32}{k}(-1)^k\left(\frac{1}{2}\right)^{ik}(1-2^k)\\
&= \sum_{k=1}^{32} \binom{32}{k}(-1)^k(1-2^k)\sum_{i=1}^\infty i\left(\frac{1}{2}\right)^{ik}
\end{align*}
ここで,

\begin{align*}
T = \sum_{i=1}^\infty i\left(\frac{1}{m}\right)^i
\end{align*}

とおくと,

\begin{align*}
\frac{m-1}{m}T = T – \frac{1}{m}T &= \left(\frac{1}{m}+\frac{2}{m^2}+\frac{3}{m^3}+\cdots\right)-\left(\frac{1}{m^2}+\frac{2}{m^3}+\frac{3}{m^4}+\cdots\right)\\
&= \frac{1}{m}+\frac{1}{m^2}+\frac{1}{m^3}+\cdots\\
&= \frac{1}{m}\cdot\frac{1}{1-\frac{1}{m}}\\
&= \frac{1}{m-1}
\end{align*}

より
\begin{align*}
T = \sum_{i=1}^\infty i\left(\frac{1}{m}\right)^i &= \frac{m}{(m-1)^2}
\end{align*}
となる.これを利用すると,
\begin{align*}
\mathrm{E}[N] &= \sum_{k=1}^{32} \binom{32}{k}(-1)^k(1-2^k)\frac{2^k}{(2^k-1)^2}\\
&= \sum_{k=1}^{32} \binom{32}{k}(-1)^{k+1}\frac{2^k}{2^k-1}.
\end{align*}

\(k=1, 2, \ldots, 32\)について各項は容易に計算できます.

以下がc++によるプログラム例です.ちなみに,double型で計算すると誤差で小数点以下10桁までの答えが合わなかったので,log double型で計算しました.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加