従って、FKVアルゴリズムは行列がセグメント木の形式で保持されている場合は効率的に行うことができる。FKVアルゴリズムの実装は以下のようになる。u)下のコードで示すように、量子状態のボルンの規則と合わせるため、量子状態の値はL2-normでサンプリングされる。セグメント木は和に対して定義されるため、総和がL2-normの二乗となるよう、セグメント木行列の要素には嗜好行列の要素の事情の値が格納される。従って、サブ行列を作成した後に特異値分解する際には、全要素のsqrtを取る必要がある。algorithmを試してみよう。50\)のサブ行列を作成し、Top-10の特異値を表示している。最大特異値はおおむねあっているものの、以降の特異値でずれがひどいことが分かる。1000\)のサブ行列(というのか分からないが)を作成し、Top-10の特異値を表示している。当たり前だが、この計算自体は元の行列より大きな行列をサンプリングしているため有用ではない操作である。6.50609105]まだ十分とは言えないが、正しい値に漸近的に近づいていることが分かる。\right)\)というとんでもない多項式になっている。\epsilon=0.1\)に対して理論的な精度保証を得るためには、\(p=10^{29.5}\)というとんでもない数のサイズの行列が要請される。p\)である必要があり、その行列のサイズは各要素が1bitだとしても\(10^{59}\)byteとなり、行ですら\(10^{14}\)PBという到底保持できないサイズとなる。上記の多項式や係数は理論的な証明のためのオーバーヘッドを含むため、実際にはそれほど大きくしなくともそこそこの結果は得られると思われるが、いずれにせよ無条件に多項式だから有用だと言える手法ではないことは念頭に入れておきたい。一般に確率分布は高速にサンプリング可能とは限らない。\(2^n\)個の要素のうち\(i\)番目の要素が\(p_i\)の確率で得られる分布で、\(i\)に対して\(p_i\)が効率的に計算できるとしても、サンプリングには一般に指数的な時間を要する。\(P\)と類似している効率的にサンプリング可能な分布\(Q\)を用いて\(P\)からのサンプリングを効率的に行う手法である。近いと期待される効率的にサンプリング可能な分布\(Q\)を提案分布と呼ぶ。具体的な手続きは以下である。\right)\)となる\(M\)を求める。\(Q\)からサンプリングを行い、\(i\)を得る。\frac{p_i}{Mq_i}\)を計算する。\(r<t\)なら\(i\)を出力する。なければ1.からやり直す。上記の手続きで得られるサンプリング操作は\(Q\)からのサンプリング操作と一致する。上記の操作に必要な計算量は\(Q\)からのサンプリングの操作が効率的なら\(O(M)\)の期待値で終了する。効率の最良のケースは確率分布\(P\)と\(Q\)が一致している場合であり、\(M=1\)となる。この場合はそもそも棄却サンプリングを行う意味がない。0\)でかつ\(q_i=0\)となるような\(i\)が存在する場合である。\infty\)となり棄却サンプリングはそもそも実行できない。例として、一様分布に十分近い\(n\)個のシンボルについての確率分布\(\{p_i\}\)を考えよう。(1/n)\)であることが保障されているとする。n\)の速度で高速にサンプリングすることができる。このことを利用して、\(\{p_i\}\)からのサンプリングを一様分布のサンプリングを用いて棄却サンプリングしてみよう。(以下の実装では規格化のために微妙に\(M=1.1\)からずれているが、おおむね\(M=1.1\)となる。sampling_countまず、棄却サンプリングからサンプリングされる分布が、オリジナルの分布を再現しているかを検証してみよう。label="rejection")plt.legend()plt.xlabel("synbols")plt.ylabel("probability")plt.show()確かに棄却サンプリングから得られる分布と目的分布が一致していることがわかる。次に、通常のサンプリングとの速度比較のベンチマークを取ってみよう。1.050053426899406良いサンプラーを持っている場合、直接的なサンプリングに比べ、棄却サンプリングは圧倒的に高速であることがわかる。\(M\)の値とサンプリング回数がおおむね一致している。棄却サンプリングを行うにあたって注意しなければならない点が二つある。一つ目は、棄却サンプリングを用いる代わりに、目的分布の確率ベクトルに関する累積和やセグメント木などのデータ構造を用いることでも高速にサンプリングが可能になるという可能性が存在する点である。セグメント木を与えられたベクトルで初期化する手続きには\(O(n)\)が必要となる。