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型で計算しました．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#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; } |
