(57)【要約】【課題】複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布である第二確率分布に従う乱数の系列を生成する技術を提供する。【解決手段】実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成部の処理と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部の処理とを繰り返し行う。【選択図】図１
2014109913.tif 000002
【特許請求の範囲】
【請求項１】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降の繰り返し処理で生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成部と、
上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、
上記確率分布生成部及び上記乱数生成部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御部と、
を含む乱数系列生成装置。
【請求項２】
請求項１の乱数系列生成装置において、
Xを確率変数とし、[X]をXのとり得る値の集合とし、Xに対応する確率分布をpXとし、集合Sの大きさを|S|とし、Xn≡(X1,X2,…,Xn)を所定のn次元の確率変数とし、xn≡(x1,x2,…,xn)をXnの実現値とし、[Xn]≡[X1]×[X2]×…×[Xn]とし、Φ≡{φs:[Xn]→Vs}s=1lを所定の関数の集合とし、Φ(xn)∈V1×V2×…×VlをΦ(xn)≡(φ1(xn),φ2(xn),…,φl(xn))とし、vl≡(v1,v2,…,vl)を所定のベクトルとし、kを1以上n以下の整数とし、T(s)⊂{1,2,…,n}を関数φsを計算するときに使用する変数x n≡(x1,x2,…,xn)のインデックスの集合とし、xT(s)をxnからインデックス集合T(s)と対応する部分を取り出した|T(s)|次元のベクトルとし、χ(xT(s),vs)は次式のように定義されるとして、
【数５７】
2014109913.tif 000059
上記所定の条件は、Φ(xn)=vlであり、
上記第一確率分布は、pXnであり、
上記第二確率分布における各実現値の系列ｘｎについての確率は、次式で定義されるμ(xn)であり、
【数５８】
2014109913.tif 000060
上記第三確率分布における各実現値ｘｋについての第三確率は、次式で定義されるfk(xk)であり、
【数５９】
2014109913.tif 000061
上記制御部は、上記確率分布生成部及び上記乱数生成部の処理を異なるkのそれぞれについて行うことにより、上記第二確率分布に従う乱数の系列を生成させる、
乱数系列生成装置。
【請求項３】
請求項１又は２の乱数系列生成装置において、
上記制御部は、上記残りの乱数の系列が唯一に定まる場合には、上記確率分布生成部及び上記乱数生成部の繰り返し処理を終了させる、
乱数系列生成装置。
【請求項４】
請求項１から３の何れかの乱数系列生成装置において、
上記所定の第一確率分布は、所定の事象を条件とする条件付き確率分布であり、
上記第一確率及び上記第二確率は、上記所定の事象を条件とする条件付き確率である、
乱数系列生成装置。
【請求項５】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
確率分布生成部が、実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成ステップと、
乱数生成部が、上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成ステップと、
制御部が、上記確率分布生成ステップ及び上記乱数生成ステップの処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御ステップと、
を含む乱数系列生成方法。
【請求項６】
請求項１から４の何れかの乱数系列生成装置としてコンピュータを機能させるためのプログラム。
【請求項７】
請求項１から４の何れかの乱数系列生成装置としてコンピュータを機能させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、乱数の系列を生成する技術に関する。
【背景技術】
【０００２】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布である第二確率分布に従って、乱数の系列を生成する技術はこれまで提案されていない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
この発明は、第二確率分布に従う乱数の系列を生成する乱数系列生成装置、方法、プログラム及びその記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００４】
この発明の一態様による乱数系列生成装置は、複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての複数の値の系列である実現値についての確率の分布を第二確率分布として、実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての第三確率の分布である第三確率分布を生成する確率分布生成部と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、確率分布生成部及び乱数生成部の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させる制御部と、を備える。
【発明の効果】
【０００５】
第二確率分布に従う乱数の系列を生成することができる。
【図面の簡単な説明】
【０００６】
【図１】乱数系列生成装置の例を説明するためのブロック図。
【図２】乱数系列生成装置の他の例を説明するためのブロック図。
【図３】乱数系列生成方法の例を説明するためのフローチャート。
【発明を実施するための形態】
【０００７】
［記法の説明］
まず、記法の説明を行う。Xが確率変数であるとき、Xのとり得る値の集合を[X]と記す。集合Sの大きさ、すなわち集合Sに含まれる要素の数を|S|と記す。差集合をS＼S’と記し、これは集合Sに含まれており、かつ集合S’に含まれていない要素全体からなる集合を表す。
【０００８】
Xn≡(X1,X2,…,Xn)はn次元の確率変数で、その実現値をxn≡(x1,x2,…,xn)と記す。
[Xn]≡[X1]×[X2]×…×[Xn]と記す。確率変数Xと対応する確率分布をpXと記す。なお、pXをp_(X)と記すこともある。
【０００９】
Φは一般には関数を表し、Φ(xn)は関数Φのベクトルxnにおける値を表す。qを素数として、関数Φ:GF(q)n→GF(q)mがq元の有限体GF(q)上ベクトル空間の線形写像の場合、
【００１０】
【数１】
2014109913.tif 000003
【００１１】
のように行列で表記する。このとき、xnは列ベクトル
【００１２】
【数２】
2014109913.tif 000004
【００１３】
となる。この場合はΦ(xn)をΦxnと記す。
【００１４】
変数のとり得る値の集合が有限であることが明示されていないときは、連続値をとることができる。また、和Σをとる変数が連続値である場合にはΣは積分∫となる。
【００１５】
［制約条件を満たす素朴な乱数系列生成法］
関数の集合Φ≡{φs:[Xn]→Vs}s=1lに対してΦ(xn)∈V1×V2×…×Vlを
【００１６】
【数３】
2014109913.tif 000005
【００１７】
と定義する。vl≡(v1,v2,…,vl)及び確率変数Xn≡(X1,X2,…,Xn)の分布pXnが与えられたときに、次式で定義されるμ(xn)を考える。
【００１８】
【数４】
2014109913.tif 000006
【００１９】
所定の条件をΦ(xn)=vlとし、所定の第一確率分布をpXnとすると、実現値xn≡(x1,x2,…,xn)についての確率μ(xn)は、所定の第一確率分布pXnにおいてその実現値xnが出現する確率に応じた確率である。
【００２０】
ここでは、所定の条件Φ（ｘｎ）＝ｖｌを満たす全ての実現値についての確率μ(xn)の分布（第二確率分布）に従ういずれか一つの実現値xnを乱数の系列として発生させる素朴な２つの方法を記述する。
【００２１】
＜方法１＞
まず最初に、Φ(xn)=vlを満たすxnを列挙した集合Ωを求める。続いて、各xn∈Ωについて、関係式
【００２２】
【数５】
2014109913.tif 000007
【００２３】
を用いて(a2)の右辺を計算することにより、確率分布μを求める。最後に、確率分布μに従いxn∈Ωを選択する。
【００２４】
なお、＜方法１＞において、入力はpXn、関数の集合Φ及びベクトルvlであり、出力は乱数xnである。
【００２５】
＜方法２＞
確率分布pXnに従いxn∈[Xn]を選択する。続いて、xnが条件Φ(xn)=vlを満たすかどうかを確認する。これをΦ(xn)=vlを満たすxnが選択されるまで繰り返し、最終的に、この条件を満たすxnを乱数の系列として出力して終了する。
【００２６】
なお、＜方法２＞において、入力はpXn、関数の集合Φ及びベクトルvlであり、出力は乱数xnである。
【００２７】
＜方法１＞では、Φ(xn)=vlを満たすxnを列挙した集合Ωを求める必要があるが、一般に|Ω|はnの増大に伴い指数的に増大するため、集合Ωを求めることが困難となる可能性がある。この事実は(a3)の計算も困難とするため、確率分布μを求めることも困難となる可能性がある。また、仮に、確率分布μが求まったとしても、μに従いxn∈Ωを選択することも困難となる可能性がある。さらに、pXnが事前に固定されている場合は、Ωやμを事前に計算して記憶部に記録することもできるが、この場合は記憶量がnとともに指数的に増大する可能性がある。
【００２８】
＜方法２＞では、Φ(xn)=vlを満たすxnを選択するまで繰り返し乱数を発生させるが、一般にΦ(xn)=vlを満たすxnを選択する確率はnとともに指数的に0に近付くことから、繰り返し回数が指数的に増大する可能性がある。
【００２９】
［乱数系列生成装置及び方法の第一実施形態］
以下では、関数の集合Φ≡{φs:[Xn]→Vs}s=1lとvl≡(v1,v2,…,vl)を与え、Φ(xn)∈V1×V2×…×Vlを(a1)で定義したときに、(a2)の確率分布μに従う乱数の系列xnを発生させる乱数系列生成装置について説明する。
【００３０】
T(s)⊂{1,2,…,n}を関数φs(xn)を計算する際に使用する変数xn≡(x1,x2,…,xn)のインデックスの集合とする。xT(s)をxnからインデックス集合T(s)と対応する部分を取り出した|T(s)|次元のベクトルとする。以下では、関数φs(xn)を計算する際に使用する変数だけに注目して、φs(xn)をφs(xT(s))と記す。例えば、関数φs(xn)を計算するときに使用する変数がx1,x2であるときには、T(s)={1,2},φs(xT(s))≡φs(x1,x2)=φs(xn)を満たしている。
【００３１】
Φ≡{φs:[Xn]→Vs}s=1lより定まるχ(xT(s),vs)を次のように定義する。
【００３２】
【数６】
2014109913.tif 000008
【００３３】
確率分布pXnを次のように分解する。
【００３４】
【数７】
2014109913.tif 000009
【００３５】
ここで、上式の右辺でt=1の時には
【００３６】
【数８】
2014109913.tif 000010
【００３７】
とする。例えば、pXnが無記憶の場合は、
【００３８】
【数９】
2014109913.tif 000011
【００３９】
となり、pXnがδ次Markov性を持つ場合は
【００４０】
【数１０】
2014109913.tif 000012
【００４１】
となる。
乱数系列生成装置１は、図１に示すように、制御部１１、確率分布生成部１２、乱数生成部１３、記憶部１４及び乱数推定部１５を例えば備えている。
【００４２】
(a2)で定義された確率分布μに従う乱数を発生させるために、乱数系列生成装置は次の処理を実行する。以下、Σはその下に書かれている変数の全てのとり得る値に関する和を表すこととする。例えば、Σxtは全てのxt∈[Xt]に関する和である。
【００４３】
制御部１１は、k=1とする（ステップＡ１，図３）。
【００４４】
確率分布生成部１２が、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。sum-productアルゴリズムについては、後述する。
【００４５】
【数１１】
2014109913.tif 000013
【００４６】
なお、上式の右辺ではこれまでに記録したx1,…,xk-1を代入する。
【００４７】
また、χ(xT(s),vs)が定数となったものを記録しておけば将来の計算を省略できる。例えばT(s)が{1,…,k}である場合には、χ(xT(s),vs)の値はxk+1,…,xnの値によらず0又は1となり定数となる。この場合、定数であるχ(xT(s),vs)を次回以降の繰り返し処理で用いるために記憶部１４に記録する。
【００４８】
x1,…,xk-1を既に生成された乱数の系列とし、今回生成される乱数をxkとし、次回以降生成される残りの乱数の系列をxk+1,…,xnとすると、(a5)の右辺の分子に現れる
【００４９】
【数１２】
2014109913.tif 000014
【００５０】
は、既に生成された乱数の系列x1,…,xt-1を条件としたときに実現値xtが出現する第一確率と言える。
【００５１】
また、(a5)の右辺の分子に現れる
【００５２】
【数１３】
2014109913.tif 000015
【００５３】
は、既に生成された乱数の系列x1,…,xk-1及び今回生成される乱数xkを条件としたときに、次回以降生成される残りの乱数の系列xk+1,…,xnが、所定の条件（この場合、Φ(xn)=vl）を満たす第二確率と言える。
【００５４】
(a5)の分母は正規化項なので、例えば(a5)で表されるfk(xk)は、実現値が上記第一確率と上記第二確率との積に応じた値である確率分布ということができる。
【００５５】
乱数生成部１３が、確率分布fk(xk)に従い乱数xkを発生させ記憶部１４に記録する（ステップＡ３）。
【００５６】
制御部１１は、k=nであるか判定する（ステップＡ４）。
【００５７】
k=nであれば、制御部１１は、これまでに記録した変数の値を連結したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ５）。
【００５８】
k<nであれば、制御部１１は、これまでに記録した(x1,…,xk)からΦ(xn)=vlを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する（ステップＡ６）。
【００５９】
もし唯一定まるのであれば、乱数推定部１５は(xk+1,…,xn)を求めてxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ７）。なお、唯一定まるかどうかを確認するための基準及びこの場合の(xk+1,…,xn)の求め方の例は、乱数系列生成装置及び方法の第二実施形態で説明する。
【００６０】
唯一に定まらない場合には、制御部１１はkの値を１増やしてステップＡ２に戻る（ステップＡ８）。
【００６１】
このようにして、制御部１１は、確率分布生成部１２及び乱数生成部１３の処理を繰り返すことにより、確率分布μに従う乱数の系列を生成させる。
【００６２】
なお、ステップＡ６及びステップＡ７の処理は行わなくてもよい。例えば、(xk+1,…,xn)が唯一に定まるかどうかを確認する処理に時間がかかるか、この確認をすることができない場合、また唯一定まる(xk+1,…,xn)を求める処理に時間がかかるか、この処理をすることができない場合、この確認処理を省略し、k<nであればkの値を1増やしてステップＡ２に戻る構成としてもよい。この場合、乱数系列生成装置１は、図２に例示するように、乱数推定部１５を備えていなくてもよい。
【００６３】
乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1)}t=1nと関数の集合{χ(xT(s),vs)}s=1lであり、乱数系列生成装置１の出力はxnである。上述のように、記憶部１４には、入力の他にχ(xT(s),vs)が定数となったものを記録しておいてもよい。
【００６４】
ステップＡ２において(a5)を計算する際に、変数(xk,xk+1,…,xn)のなかで注目する変数(上記ではxk)を自由に選択できる。従って、ステップＡ２では全ての変数(xk,xk+1,…,xn)に対して周辺化関数を求めた結果から、後の計算に都合のよい周辺化関数を利用することができる。これは、変数(x1,…,xn)の周辺化を行う順序をステップＡ２で適応的に変えられることを意味する。ここで、注目する変数の順序の変更にともない、(a5)の右辺に現れるp_(Xn|X1t-1)の再計算を必要とする場合があることを注意しておく。ただし、pXnが無記憶、すなわち(a4)を満たすときは、ステップＡ２において(a5)を計算する際に変数(xk,xk+1,…,xn)のなかで注目する変数(上記ではxk)を変えても、注目する変数の順序の変更にともなうp_(Xt|X1t-1)=pXtの再計算の必要はない。
【００６５】
なお、条件式Φxn=vlと等価で、かつsum-productアルゴリズムの計算精度が向上する条件式に変形した後で、制約条件を満たす乱数生成アルゴリズムを適用してもよい。
sum-productの近似精度を上げるために、例えば、集合T(s)の大きさが小さくなるように、また条件式Φｘｎ＝ｖｌと対応するファクターグラフが短いループを持たないように、条件式を変形することなどが考えられる。
【００６６】
なお、ステップＡ２において所望の乱数を発生させるために、参考文献１に記載されている区間アルゴリズムを用いて一様乱数列からxkを求めてもよい。参考文献１では発生させる乱数列は独立同分布であることを仮定しているが、ここではこの仮定が成り立たないので、次のような改良を施す。今、ωを2以上の整数として、十分な長さの一様ω元乱数列r1,r2,…があるとする。この乱数列r1,r2,…は、例えば図１に破線で示した一様乱数生成部１６により生成される。以下では
[ζ,η)≡{θ:ζ≦θ＜η}
とする。
【００６７】
〔参考文献１〕[11] T.S. Han and M. Hoshi, “Interval algorithm for random number generation,” IEEE Trans. Inform. Theory, vol. IT-44, no. 2, pp. 599-611, Mar. 1997.
【００６８】
ステップＡ１において、区間の初期値を[ζ1,η1)≡[0,1)とする。
【００６９】
ステップＡ３において、区間[ζk,ηk)を長さ{fk(x)}x∈[Xk]の部分区間に分割し、長さfk(x)と対応する区間にラベルx∈[Xk]を付ける。そして、ω進小数0.r1r2…を含む区間と対応するラベルをxkとする。ステップＡ２の最後に、先程求めたxkと対応する区間、すなわちω進小数0.r1r2…を含む区間を[ζk+1,ηk+1)とする。
【００７０】
この改良によって、xn=(x1,…,xn)と対応する区間の幅はμ(xn)となるので、(x1,…,xn)と対応する区間に一様乱数より求めたω進小数0.r1r2…が含まれる確率はμ(xn)となる。ここで、アルゴリズムがk=k’で停止した場合は(x1,…,xk’)までしか乱数は発生させないが、k=k’の時点の区間の分割は後述する(a11)と対応しているので、所望の確率分布に従う乱数系列(x1,…,xn)が得られている。
【００７１】
ステップＡ２でsum-product アルゴリズムを適用してO(n)で実行することを仮定し、ステップＡ６及びステップＡ７の計算時間はO(n2)であることを仮定すれば、このアルゴリズムは全体でO(n2)の計算時間で終了する。このため、このアルゴリズムにより、上述の［制約条件を満たす素朴な乱数系列生成法］よりも短い計算時間で乱数系列を生成することができる。
【００７２】
以下では、本アルゴリズムが期待する結果を出力することを証明する。(a5)の右辺の分子に現れる式を
【００７３】
【数１４】
2014109913.tif 000016
【００７４】
とすると、
【００７５】
【数１５】
2014109913.tif 000017
【００７６】
が成り立っている。
【００７７】
xn=(x1,x2,…,xn)を最終的に出力した乱数系列とする。アルゴリズムのステップＡ４においてk=nで終了した場合は、
【００７８】
【数１６】
2014109913.tif 000018
【００７９】
となる。一方で、 アルゴリズムのステップＡ６及びステップＡ７でk=k’<nで終了した場合は、(x1,x2,…,xk’)からΦ(xn)=vlを満たす残りの変数の値(xk’+1,…,xn)が唯一定まることから、
【００８０】
【数１７】
2014109913.tif 000019
【００８１】
となる。(a8)は(a7)をk’=nの場合として含んでいるので、以下、k=k’で終了した場合を考える。
【００８２】
(a6)よりk≧2の時は
【００８３】
【数１８】
2014109913.tif 000020
【００８４】
が成り立つ。また、k=1の時は
【００８５】
【数１９】
2014109913.tif 000021
【００８６】
が成り立つ。(a8),(a9),(a10)より最終的にxnを出力する確率は
【００８７】
【数２０】
2014109913.tif 000022
【００８８】
となる。したがって、このアルゴリズムは、確率分布(a2)に従う乱数列xnを出力する。
【００８９】
＜sum-productアルゴリズムについて＞
一般的にsum-productアルゴリズムとは、変数ベクトルxnの一部からなる変数ベクトルxT(s)で定まる関数es(xT(s))が各s∈Sで与えられたとき、周辺化関数
【００９０】
【数２１】
2014109913.tif 000023
【００９１】
を求める手続きである。ここで、N≡{1,2,…,n}として、各s∈SでT(s)⊂Nである。また
Σxn＼{xt}は、ベクトルxnに現れる変数xt以外の全てのxnの値を動かした時の総和である。また、(a12)で定めたg(xt)ではなく、右辺の分子に現れた
【００９２】
【数２２】
2014109913.tif 000024
【００９３】
を求める手続きとしてsum-productアルゴリズムが記述される場合があるが、以下では、(a12)で定めたg(xt)を求める手続きをsum-productアルゴリズムと呼ぶことにする。
【００９４】
以下にsum-productアルゴリズムを記述する。メッセージと呼ばれる関数πxt→es(xt),σes→xt(xt)を次のように定義する。
【００９５】
【数２３】
2014109913.tif 000025
【００９６】
ここで、Σx_(T(s)＼{t})は全ての{xt’}t’∈T(s)＼{t}を動かした時の総和であり、Σx_(T(s))は全ての{xt}t∈T(s)を動かした時の総和を表す。また、T(s)={t}の時は
【００９７】
【数２４】
2014109913.tif 000026
【００９８】
と定め、xt∈T(s’)を満たすs’∈S＼{s}が存在しないときは
【００９９】
【数２５】
2014109913.tif 000027
【０１００】
と定める。
以下、sum-product アルゴリズムの具体処理について説明する。
Step 1 T(s)={t}を満たすt∈N,s∈Sに対して
【０１０１】
【数２６】
2014109913.tif 000028
【０１０２】
と初期化する。
Step 2 xt∈T(s’)を満たすs’∈S＼{s}が存在しないようなt∈N,s∈Sに対して
【０１０３】
【数２７】
2014109913.tif 000029
【０１０４】
と初期化する。
Step 3 t∈T(s)を満たすt∈N,s∈Sに対して、πxt→es(xt)をStep 2 で初期化しなかったならば、これに適当な初期値を設定する。例えば、xtのとり得る値の集合が[Xt]であれば、
【０１０５】
【数２８】
2014109913.tif 000030
【０１０６】
とする。
Step 4 t∈T(s)を満たしているような全てのt∈N,s∈Sに対して(a13)によって
σes→xt(xt)を求める。ここで、Step 1で初期化したs,tの組合せについてはσes→xt(xt)の計算を省略する。
Step 5 t∈T(s)を満たしているような全てのt∈N,s∈Sに対して(a14)によってπxt→es(xt)を求める。ここで、Step 2で初期化したs,tの組合せについてはπxt→es(xt)の計算を省略する。
Step 6 Step 4とStep 5を予め定めた繰り返し回数繰り返した後、以下の関数を求めて終了する。
【０１０７】
【数２９】
2014109913.tif 000031
【０１０８】
なお、制約を満たす乱数生成アルゴリズムにsum-productアルゴリズムを用いる場合、(a5)において
【０１０９】
【数３０】
2014109913.tif 000032
【０１１０】
を{es}s∈Sとみなして適用する。sum-productアルゴリズムの実行後に得られた(a15)の右辺がfk(xk)の近似式となる。
【０１１１】
［乱数系列生成装置及び方法の第二実施形態］
乱数系列生成装置及び方法の第二実施形態は、関数が線形性を持つときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１１２】
以下では、[X1]=[X2]=…=[Xn]=[V1]=[V2]=…=[Vl]=GF(q)を仮定し、l≦nとして、フルランクのl×n行列
【０１１３】
【数３１】
2014109913.tif 000033
【０１１４】
を考える。関数φs:[Xn]→Vsを
【０１１５】
【数３２】
2014109913.tif 000034
【０１１６】
と定義する。上式の右辺は行列Φのｓ行目のｎ次元ベクトル（φs,1, φs,2,...,φs,n）とxn≡(x1,x2,…,xn)∈[Xn]の内積である。
【０１１７】
上記のように定義されたΦ≡{φs}s=1lとベクトル
【０１１８】
【数３３】
2014109913.tif 000035
【０１１９】
に対して、確率分布(a2)で定まる分布を発生させる乱数系列生成装置１の具体処理を記述する。
【０１２０】
ここで、Φとｖｌは与えられた行列とベクトルそのままを利用しても良いが、Φとｖｌを連結した以下の行列
【０１２１】
【数３４】
2014109913.tif 000036
【０１２２】
に対して行基本変形を施した結果
【０１２３】
【数３５】
2014109913.tif 000037
【０１２４】
の左側l×n行列Φ´と右側l×1行列（l次元ベクトル）ｖ´ｌを、それぞれΦおよびｖｌとして代用しても良い。例えば、行列Φ´の０となる成分が多く、Φ´とｘnとｖ´lから定まるファクターグラフが短いループを持たないようなΦ´とｖ´lを用いることにより、sum-product アルゴリズムによる近似精度が向上する場合があるので、本願発明の乱数系列生成装置が出力する乱数の確率分布の精度をより向上させることができる。
【０１２５】
以下、Φをフルランクの行列として、行列Φの右側のl×l行列Ψ2が正則行列であると仮定しても一般性は失われない。実際に、任意の行列Φとベクトルvlから冗長な条件式を構成するΦの行とvlの成分を取り除いた行列を求め、この行列の行ベクトルと変数(x1,x2,…,xn)の順序を適切に並びかえることにより所望の行列を求めることができる。
【０１２６】
行列Φの左側のl×(n-l)行列をΨ1とすると、上記の仮定から、xn-l≡(x1,…,xn-l)を決定すれば
(xn-l+1,…,xn)≡Ψ2-1(vl-Ψ1xn-l)
によってΦxn=vlを満たす残りの変数(xn-l+1,…,xn)を求めることができる。ここで、Ψ2-1はΨ2の逆行列を表し、アルゴリズムの実行前に求めることができる。
【０１２７】
T(s,k)⊂{k,…,n}を行列Φに現れるベクトル(φs,k,…,φs,n)の中で、φs,t≠0を満たすインデックスsの集合とする。すなわち、T(s,k)は以下のように定義される。
【０１２８】
T(s,k)≡{t∈{k,…,n}:φs,t≠0}
ここで、χ(xT(s,k),vs(k))を次のように定義する。
【０１２９】
【数３６】
2014109913.tif 000038
【０１３０】
以上の設定により、乱数系列生成装置１の具体処理を以下のように変更することができる。
【０１３１】
制御部１１は、k=1とする。各s∈{1,…,l}でvs(k)=vsとする。
【０１３２】
確率分布生成部１２は、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。
【０１３３】
【数３７】
2014109913.tif 000039
【０１３４】
乱数生成部１３が、確率分布fk(xk)でxkを発生させ、記憶部に記録する（ステップＡ３）。
【０１３５】
制御部１１は、k=nであるか判定する（ステップＡ４）。
【０１３６】
k=nであれば、制御部１１は、これまでに記録した変数の値を連結したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ５）。
【０１３７】
k<nであれば、制御部１１は、これまでに記録した(x1,…,xk)からΦxn=vlを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する。この例では、制御部１１はk=lであるか判定する（ステップＡ６）。
【０１３８】
k=lであれば、乱数推定部１５は、残りの変数の値(xl+1,…,xn)≡Ψ2-1vl(k+1)を求めて記録し、これまでに記録したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ７）。
【０１３９】
k<lであれば、制御部１１はkの値を1増やして、ステップＡ２に戻る（ステップＡ８）。なお、ステップＡ２に戻る際に、vl(k+1)≡(v1(k+1),…,vl(k+1))を各s∈{1,…,l}で
vs(k+1)≡vs(k)-φs,kxk
とする。
【０１４０】
なお、上記の具体処理において、ステップＡ４とステップＡ５の処理を省略して、ステップＡ３から直ちにステップＡ６に進んでもよい。あるいは、ステップＡ７において、Ψ2-1vl(k+1)の計算に時間がかかる場合は、ステップＡ６とステップＡ７の処理を省略して、ステップＡ４から直ちにステップＡ８に進んでもよい。
【０１４１】
第二実施形態の乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1)}t=1nと行列Φであり、出力はxnである。記憶部１４には入力とGF(q)の計算に必要な情報qの他に、ΦからΨ2-1を求めて記録しておくことができる。(xT(s,k),vs(k))はkとともにΦを用いて更新される。
【０１４２】
［乱数系列生成装置及び方法の第三実施形態］
乱数系列生成装置及び方法の第三実施形態は、pXnが条件付き確率分布のときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１４３】
条件付き確率分布p_(Xn|Un)が与えられたとき、制約条件を満たし、
【０１４４】
【数３８】
2014109913.tif 000040
【０１４５】
に従う乱数を生成するときには、
【０１４６】
【数３９】
2014109913.tif 000041
【０１４７】
と置き換えて乱数系列生成装置の具体処理を実行する。すなわち、例えば(a5)は、次式のようになる。
【０１４８】
【数４０】
2014109913.tif 000042
【０１４９】
第三実施形態の乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1Un)}t=1n、関数の集合Φ,vl,unであり、出力はxnである。
【０１５０】
記憶部１４には入力の他に
【０１５１】
【数４１】
2014109913.tif 000043
【０１５２】
を計算するために必要な情報を保持しておき、確率分布の計算に利用する。
【０１５３】
なお、上記同様にして、乱数系列生成装置及び方法の第二実施形態においてもpXnが条件付き確率分布であってもよい。
【０１５４】
［乱数系列生成装置及び方法の第四実施形態］
乱数系列生成装置及び方法の第四実施形態は、定義域が同一の関数を複数用いて制約条件が記述されるときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１５５】
c∈Cとする。Cは2以上の所定の定数である。制約条件を満たす乱数生成法において、定義域が同一の複数の関数の集合
Φc≡{φc,s:[Xn]→Vc,s}s=1lc
及び
vclc≡(vc,1,vc,2,…,vc,l)∈Vc,1×Vc,2×…×Vc,lc
および分布pXnが与えられたとき、
【０１５６】
【数４２】
2014109913.tif 000044
【０１５７】
に従う乱数を生成するには
【０１５８】
【数４３】
2014109913.tif 000045
【０１５９】
とおいて、乱数系列生成装置及び方法の第一実施形態の具体処理を実行すればよい。すなわち、例えば(a5)は、次式のようになる。
【０１６０】
【数４４】
2014109913.tif 000046
【０１６１】
ここで、T(c,s)⊂{1,2,…,n}はφc,s(xn)=vc,sを計算する際に使用する変数xn=(x1, x2, …, xn)のインデックスの集合であり、
【０１６２】
【数４５】
2014109913.tif 000047
【０１６３】
である。
もちろん、関数Φcが全て線形写像(行列)である場合は、関数を表す行列を連結した１つのl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を実行してもよい。
【０１６４】
また、［乱数系列生成装置及び方法の第四実施形態］においても、［乱数系列生成装置及び方法の第三実施形態］のように確率分布が条件付き確率分布で与えられていてもよい。この場合、fk(xk)は以下のようになる。
【０１６５】
【数４６】
2014109913.tif 000048
【０１６６】
［乱数系列生成装置及び方法の第五実施形態］
乱数系列生成装置及び方法の第四実施形態は、定義域が異なる関数を複数用いて制約条件が記述されるときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１６７】
i∈K≡{1,2,…,κ},XK*≡{Xini}i∈Kとする。ここで、
[Xini]≡[Xi,1]×[Xi,2]×…×[Xi,n]
Xini≡(Xi,1,Xi,2,…,Xi,ni)∈[Xini]
である。制約条件を満たす乱数生成法において、定義域が異なる複数の関数の集合
Φi≡{φi,s:[Xini]→Vi,s}s=1li
及び
vili≡(vi,1,vi,2,…,vi,li)∈Vi,1×Vi,2×…×Vi,li
および分布p_(XK*)が与えられたとき、
【０１６８】
【数４７】
2014109913.tif 000049
【０１６９】
に従う乱数
【０１７０】
【数４８】
2014109913.tif 000050
【０１７１】
を生成するには
【０１７２】
【数４９】
2014109913.tif 000051
【０１７３】
とおいて、乱数系列生成装置及び方法の第一実施形態の具体処理を実行すればよい。ここで、
θk*≡{θi}i∈K
であり、XK*およびxnに含まれる確率変数を並べる順序は任意である。以下，xの下に付くインデックスはそのように並べ替えた後のインデックスを指すものとする。
すなわち、例えば(a5)は、次式のようになる。
【０１７４】
【数５０】
2014109913.tif 000052
【０１７５】
ここで、T(i,s)⊂{1,2,…, n}は
【０１７６】
【数５１】
2014109913.tif 000053
【０１７７】
を計算する際に使用する変数xiniのxnにおけるインデックスの集合であり、
【０１７８】
【数５２】
2014109913.tif 000054
【０１７９】
である。
もちろん、[Xini]∈GF(q)niであり、関数Φcが全て線形写像(行列)である場合は、関数を表す行列を連結した１つのl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を実行してもよい。すなわち、行列を対角線上に連結して関数と無関係な変数の部分を0で埋めたl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を利用することができる。例えば、Φ1,Φ2がそれぞれl1×n1行列、l2×n2行列で表現できるときは、Φを表現する行列は(l1＋l2)×(n1＋n2)行列
【０１８０】
【数５３】
2014109913.tif 000055
【０１８１】
となる。ここで、Oは零行列を表す。
【０１８２】
また、［乱数系列生成装置及び方法の第五実施形態］においても、［乱数系列生成装置及び方法の第三実施形態］のように確率分布が条件付き確率分布で与えられていてもよい。この場合、fk(xk)は以下のようになる。
【０１８３】
【数５４】
2014109913.tif 000056
【０１８４】
［乱数系列生成装置及び方法の実施形態の変形例］
なお、［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせることができる。このとき、unがない場合、fk(xk)は以下のようになる。
【０１８５】
【数５５】
2014109913.tif 000057
【０１８６】
［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせたときであって、unがある場合、fk(xk)は以下のようになる。
【０１８７】
【数５６】
2014109913.tif 000058
【０１８８】
［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせるとき、集合Cはiに依存して決まり、l(ベクトルvlの次元)はiとcに依存して決まる。fk(xk)の式に現れる(x1,x2,…,ｘn)のインデックスは{xini}i∈Kを適切な順序で並べたものを(x1,x2,…,ｘn)としたときのインデックスと対応し、T(i,c,s)は関数φi,c,sを計算する際に用いる変数の(x1,x2,…,ｘn)に関するインデックスを表す。なお、n≡Σi∈Kniである。
【０１８９】
上記装置及び方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１９０】
また、乱数系列生成装置における処理手段をコンピュータによって実現する場合、乱数系列生成装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、乱数系列生成装置における処理手段がコンピュータ上で実現される。
【０１９１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１９２】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１９３】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０１９４】
１  乱数系列生成装置
１１  制御部
１２  確率分布生成部
１３  乱数生成部
【図１】
2014109913.tif 000062
【図２】
2014109913.tif 000063
【図３】
2014109913.tif 000064