数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー323. ~Bitwise-OR operations on random integers~


スポンサードリンク

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桁までの答えが合わなかったので,long double型で計算しました.

#include<bits/stdc++.h>
using namespace std;
void print(int n, double d){cout << fixed << setprecision(n) << d << endl;}
int code(int i){if(i % 2 == 0) return 1; else return -1;}

int main(){
    const int N = 32;
    long double ans = 0.0;
    long long comb = 1;
    long long P = 1;
    for(int k = 1; k <= N; k++){
        comb = comb * (N - k + 1) / k;
        P *= 1;
        ans = ans + (code(k+1) * comb * P) / (ld)(P-1);
    }
    print(10, ans);
    return 0;
}