RANDOM NUMBER GENERATION APPARATUS, METHOD AND PROGRAM

Abstract

A random number generation apparatus comprises: a first random number generating part 2 generating a random number u=(u.sub.1, . . . ,u.sub.D).sup.T∈[−∞,∞].sup.D; a second random number generating part 3 generating a random number v∈[0,f′.sub.max]; and a determining part 4 determining whether f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v or not, and, if f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v, adopting u as a random number according to f′(x.sub.1, . . . ,x.sub.D), wherein D is a predetermined positive integer, for i=1, . . . ,D, [h.sub.i] is a predetermined possible range for a random variable x.sub.i, a hole [h] is [h]=([h.sub.1], . . . ,[h.sub.D]).sup.T, H is a probability of a predetermined basic distribution function f(x.sub.1, . . . ,x.sub.D) in the hole [h], α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . ,x.sub.D) is defined by Expressions (1) and (2), and f′.sub.max is a maximum value of f′(x.sub.1, . . . ,x.sub.D).

Claims

1. A random number generation apparatus, comprising: a first random number generating part generating a random number u=(u.sub.1, . . . ,u.sub.D).sup.T∈[−∞,∞].sup.D; a second random number generating part generating a random number v∈[0,f′.sub.max]; and a determining part determining whether f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v or not, and, if f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v, adopting u as a random number according to f′(x.sub.1, . . . ,x.sub.D), wherein D is a predetermined positive integer, for i=1, . . . ,D, [h.sub.i] is a predetermined possible range for a random variable x.sub.i, a hole [h] is [h]=([h.sub.1], . . . ,[h.sub.D]).sup.T, H is a probability of a predetermined basic distribution function f(x.sub.1, . . . ,x.sub.D) in the hole [h], α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . ,x.sub.D) is defined by Expressions (1) and (2):
[Formula 29]
H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D
f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)
f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2) and f′.sub.fax is a maximum value of f′(x.sub.1, . . . ,x.sub.D).

2. A random number generation apparatus comprising: an arithmetic operation part obtaining r=(r.sub.1, . . . ,r.sub.D).sup.T in the end, by performing, for each of i=1, . . . ,D, a process for generating a random number u.sub.i∈[0,1], obtaining a random number r.sub.i=F.sup.−1(u.sub.i) according to f′(x.sub.i) using the generated and x.sub.i=r.sub.i, wherein D is a predetermined positive integer, for i=1, . . . ,D, [h.sub.i] is a predetermined possible range for a random variable x.sub.i, a hole [h] is [h]=([h.sub.1], . . . ,[h.sub.D]).sup.T, H is a probability of a predetermined basic distribution function f(x.sub.1, . . . ,x.sub.D) in the hole [h], α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . ,x.sub.D) is defined by Expressions (1) and (2):
[Formula 30]
H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D
f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)
f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2) f′(x.sub.i) is a peripheral distribution of f′(x.sub.1, . . . ,x.sub.D) of x.sub.i, F(t.sub.i) is a function defined by Expression (2′):
[Formula 31]
f′(x.sub.i)=∫.sub.−∞.sup.∞ . . . ∫.sub.−∞.sup.∞f′(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.i−1dx.sub.i+1 . . . dx.sub.D
F(t.sub.i)=∫.sub.−∞.sup.t.sup.if′(x.sub.i)dx.sub.i  (2′) and F.sup.−1(t.sub.i) is an inverse function of F(t.sub.i).

3. The random number generation apparatus according to claim 1 or 2, wherein when D=2, N is a predetermined positive integer, there are N predetermined possible ranges [h.sub.i] for the random variable x.sub.i, the N predetermined possible ranges are {[h.sub.i]}.sub.i=1.sup.N{([h.sub.1].sub.i,[h.sub.2].sub.i).sup.T}.sub.i=1.sup.N={([(s.sub.1).sub.i,(e.sub.1).sub.i],[(s.sub.2).sub.i,(e.sub.2).sub.i]).sup.T}.sub.i=1.sup.N, (μ.sub.x1,2σ.sub.x1.sup.2),(μ.sub.x2,2σ.sub.x2.sup.2) are predetermined parameters, the basic distribution function f(x.sub.1, . . . ,x.sub.D) is Lap(x.sub.1,x.sub.2) defined by Expression (3), sign(a) is a function that outputs a sign {+,−} of an input a, a function g(s,e) is defined by Expressions (5) and (6) when s≤e, H described above is defined by Expression (4), and the corrected distribution function f′ is Lap′(x.sub.1,x.sub.2) defined by Expressions (7) and (8): $\begin{array}{cc}\left[\mathrm{Formula}32\right]& \\ \mathrm{Lap}\left(x_1,x_2\right)=\frac{1}{2{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\frac{1}{2{\sigma }_{x_2}}\exp \left(-\frac{.Math.x_2-{\mu }_{x_2}.Math.}{{\sigma }_{x_2}}\right)& \left(3\right)\\ \left[\mathrm{Formula}33\right]& \\ \begin{array}{c}H=\underset{i=1}{\overset{N}{.Math.}}\left\{{\int }_{{\left[h_2\right]}_i}{\int }_{{\left[h_1\right]}_i}Lap\left(x_1,x_2\right)d{x}_{1}d{x}_2\right\}\\ =\frac{1}{4}\underset{i=0}{\overset{N}{.Math.}}\left\{g\left({\left(s_1\right)}_i,{\left(e_1\right)}_i\right)g\left({\left(s_2\right)}_i,{\left(e_2\right)}_i\right)\right\}\end{array}& \left(4\right)\\ \left[\mathrm{Formula}34\right]& \\ g\left(s,e\right)=2-\exp \left(\frac{s-{\mu }_{x_1}}{{\sigma }_{x_1}}\right)-\exp \left(\frac{-e+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)\mathrm{if}s\le {\mu }_{x_1}.Math.{\mu }_{x_1}\le e& \left(5\right)\\ g\left(s,e\right)=\mathrm{sign}\left(e-{\mu }_{x_1}\right)\exp \left(-\frac{.Math.e-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)-\mathrm{sign}\left(s-{\mu }_{x_1}\right)\exp \left(-\frac{.Math.s-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}& \left(6\right)\\ \left[\mathrm{Formula}35\right]& \\ {\mathrm{Lap}}^{\text{'}}\left(x_1,x_2\right)=0\mathrm{if}{x}_1\in {\left[h_1\right]}_i.Math.\mathrm{.Math.}.Math.x_D\in {\left[h_D\right]}_i{.Math.}^{{\exists }_i}& \left(7\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1,x_2\right)=\frac{\alpha }{4{\sigma }_{x_1}{\sigma }_{x_2}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\exp \left(-\frac{.Math.x_2-{\mu }_{x_2}.Math.}{{\sigma }_{x_2}}\right)\mathrm{otherwise}.& \left(8\right)\end{array}$

4. The random number generation apparatus according to claim 2, wherein when D=2, the predetermined possible range [h.sub.i] for the random variable x.sub.i is [h.sub.i]=([h.sub.1].sub.i,[h.sub.2].sub.i).sup.T=([a,b],[c,d]).sup.T, (μ.sub.x1,2σ.sub.x1.sup.2) and (μ.sub.x2,2σ.sub.x2.sup.2) are predetermined parameters, a first area S.sub.1 is (x.sub.1≥μ.sub.x1)∧(x.sub.2≥μ.sub.x2), a second area S.sub.2 is (x.sub.1≤μ.sub.x1)∧(x.sub.2≥μ.sub.x2), a third area S.sub.3 is (x.sub.1≥μ.sub.x1)∧(x.sub.2≤μ.sub.x2) and a fourth area S.sub.4 is (x.sub.1≤μ.sub.x1)∧(x.sub.2≤μ.sub.x2), if the hole [h] is in the first area S.sub.1 or the second area S.sub.2, the corrected distribution function f′ is Lap′(x.sub.1) defined by Expressions (9) and (10), and if the hole [h] is in the third area S.sub.3 or the fourth area S.sub.4, the corrected distribution function f′ is Lap′(x.sub.1) defined by Expressions (11) and (12): $\begin{array}{cc}\left[\mathrm{Formula}36\right]& \\ \mathrm{La}{p}^{\text{'}}\left(x_1\right)=\frac{\alpha }{4{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\left(2-\exp \left(\frac{-c+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)+\exp \left(\frac{-d+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)\right)\mathrm{if}a\le x_1\le b& \left(9\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1\right)=\frac{\alpha }{2{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}& \left(10\right)\\ \mathrm{La}{p}^{\text{'}}\left(x_1\right)=\frac{\alpha }{4{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\left(2+\exp \left(\frac{c-{\mu }_{x_2}}{{\sigma }_{x_2}}\right)-\exp \left(\frac{d-{\mu }_{x_2}}{{\sigma }_{x_2}}\right)\right)\mathrm{if}a\le x_1\le b& \left(11\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1\right)=\frac{\alpha }{2{\sigma }_{x_i}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}.& \left(12\right)\end{array}$

5. A random number generation method comprising: a first random number generating step of a first random number generating part generating a random number u=(u.sub.1, . . . ,u.sub.D).sup.T∈[−∞,∞].sup.D; a second random number generating step of a second random number generating part generating a random number v∈[0,f′.sub.max]; and a determining step of a determining part determining whether f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v or not, and, if f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v, adopting u as a random number according to f′(x.sub.1, . . . ,x.sub.D), wherein D is a predetermined positive integer, for i=1, . . . ,D, [h.sub.i] is a predetermined possible range for a random variable x a hole [h] is [h]=([h.sub.1], . . . ,[h.sub.D]).sup.T, H is a probability of a predetermined basic distribution function f(x.sub.1, . . . ,x.sub.D) in the hole [h], α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . ,x.sub.D) is defined by Expressions (1) and (2):
[Formula 37]
H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D
f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)
f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2) and f′.sub.max is a maximum value of f′(x.sub.1, . . . ,x.sub.D).

6. A random number generation method, comprising: an arithmetic operation step of an arithmetic operation part obtaining r=(r.sub.1, . . . ,r.sub.D).sup.T in the end, by performing, for each of i=1, . . . ,D, a process for generating a random number u.sub.i∈[0,1], obtaining a random number r.sub.i=F.sup.−1(u.sub.i) according to f′(x.sub.i) using the generated and x.sub.i=r.sub.i, wherein D is a predetermined positive integer, for i=1, . . . ,D, [h.sub.i] is a predetermined possible range for a random variable x.sub.i, a hole [h] is [h]([h.sub.1], . . . ,[h.sub.D]).sup.T, H is a probability of a predetermined basic distribution function f(x.sub.1, . . . ,x.sub.D) in the hole [h], α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . ,x.sub.D) is defined by Expressions (1) and (2):
[Formula 38]
H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D
f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)
f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2) f′(x.sub.i) is a peripheral distribution of f′(x.sub.1, . . . ,x.sub.D) of x.sub.i, F(t.sub.i) is a function defined by Expression (2′):
[Formula 39]
f′(x.sub.i)=∫.sub.−∞.sup.∞ . . . ∫.sub.−∞.sup.∞f′(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.i−1dx.sub.i+1 . . . dx.sub.D
F(t.sub.i)=∫.sub.−∞.sup.t.sup.if′(x.sub.i)dx.sub.i  (2′) and F.sup.−1(t.sub.i) is an inverse function of F(t.sub.i).

7. A program for causing a computer to function as each part of the random number generation apparatus according to claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] FIG. 1 is a block diagram for illustrating an example of a random number generation apparatus of a first embodiment;

[0026] FIG. 2 is a flowchart for illustrating an example of a random number generation method of the first embodiment;

[0027] FIG. 3 is a diagram for illustrating a prior-art technique;

[0028] FIG. 4 is a block diagram for illustrating an example of a random number generation apparatus of a second embodiment;

[0029] FIG. 5 is a flowchart for illustrating an example of a random number generation method of the second embodiment;

[0030] FIG. 6 is a diagram for illustrating a specific example 1; and

[0031] FIG. 7 is a diagram for illustrating a specific example 2.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0032] Embodiments of the present invention will be described below with reference to drawings.

[0033] Hereinafter, a distribution function that generates random numbers included in an impossible area is called a basic distribution function f(x.sub.1, . . . ,x.sub.D), and a distribution function that does not generate random numbers included in an impossible area is called a corrected distribution function f′(x.sub.1, . . . ,x.sub.D), where, ∀D∈N.sup.+\{0}. In other words, D is a predetermined positive integer.

[0034] An impossible area of a random variable is called “a hole”, and the area of the hole is given as a parameter, for example, as shown below.

[0035] A hole [h]=([h.sub.1], . . . ,[h.sub.D]).sup.T is a hypercube in D-dimensional space, and each [h.sub.i] indicates a range [s.sub.i,e.sub.i] for a random variable x.sub.i.

[0036] The present invention is to generate a random number r∈R.sup.D according to an arbitrary D-dimensional probability distribution function f(x.sub.1, . . . ,x.sub.D). Intuitively, the process of the present invention is to express the function f(x.sub.1, . . . ,x.sub.D) as D one-dimensional probability distribution functions, sequentially generate a random number r.sub.i∈R D times, and obtain r=(r.sub.1, . . . ,r.sub.D).sup.T, a set of r.sub.i, in the end.

First Embodiment

[0037] For example, a random number generation apparatus of a first embodiment is provided with a first random number generating part 2, a second random number generating part 3 and a determining part 4 as shown in FIG. 1. The random number generation apparatus may be further provided with a function generating part 1 indicated by a broken line in FIG. 1.

[0038] For example, a random number generation method of the first embodiment is realized by each part of the random number generation apparatus performing processes from step S2 to step S4 illustrated in FIG. 2 and described below.

[0039] Hereinafter, when the basic distribution function f is given, a procedure for generating a random number r∈R.sup.D of the first embodiment will be shown below. In this procedure, a technique of a rejection method is used. Hereinafter, a maximum value of the corrected distribution function f′ is indicated by f′.sub.max.

[0040] The random number generation apparatus outputs a D-dimensional random number r=(r.sub.1, . . . ,r.sub.D).sup.T with the basic distribution function f and the hole [h] as input.

[0041] A probability H of a basic distribution function f(x.sub.1, . . . , x.sub.D) in the hole [h] is defined as below.

[Formula 4]

H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D

[0042] When α=1/(1−H), a corrected distribution function f(x.sub.1, . . . , x.sub.D) is defined by Expressions (1) and (2).

[Formula 5]

f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)

f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2)

[0043] For example, the random number generation apparatus is provided with the function generating part 1 that calculates the probability H and the corrected distribution function f′(x.sub.1 . . . , x.sub.D), and the function generating part 1 calculates the probability H and the corrected distribution f′(x.sub.1 . . . , x.sub.D) in advance before subsequent processes are performed (step S1). The random number generation apparatus may not be provided with the function generating part 1. In this case, in subsequent processes, as the probability H and the corrected distribution function f′(x.sub.1 . . . , x.sub.D), the random number generation apparatus uses those calculated by another apparatus in advance.

[0044] The first random number generating part 2 generates a random number u=(u.sub.1, . . . ,u.sub.D).sup.T∈[−∞,∞].sup.D (step S2). The first random number generating part 2 generates, for example, a uniform random number u=(u.sub.1, . . . ,u.sub.D).sup.T∈[−∞,∞].sup.D as the random number u. The generated random number u is outputted to the determining part 4.

[0045] The second random number generating part 3 generates a random number v∈[0,f′.sub.max] (step S3). The second random number generating part 3 generates a uniform random number v∈[0,f′.sub.max] as the random number v. The generated random number v is outputted to the determining part 4.

[0046] The determining part 4 determines whether f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v or not. If f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v, the determining part 4 adopts the u as a random number according to f′(x.sub.1, . . . ,x.sub.D) and outputs the random number u (step S4).

[0047] If f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)<v, the determining part 4 causes the first random number generating part 2 and the second random number generating part 3 to perform the processes of steps S2 and S3, respectively, again. In other words, the determining part 4 causes the first random number generating part 2 and the second random number generating part 3 to perform the processes of steps S2 and S3, respectively, until f′(x.sub.1=u.sub.1, . . . ,x.sub.D=u.sub.D)≥v.

[0048] By the above processes, a multidimensional random number according to a multidimensional probability distribution such that a probability in the hole [h], which is a predetermined area, is zero can be generated. If an expression of a multidimensional probability distribution can be obtained, it is possible to generate random numbers not only from a multidimensional probability distribution such that a probability in an impossible area is zero but from an arbitrary probability distribution.

[0049] For example, by using this random number generation method, personal data that is impossible in a real society is not generated when anonymization of a database that includes personal data having a plurality of attributes is performed.

[0050] Attributes in a database to be anonymized are not necessarily independent but may be dependent on one another. In Non-patent literature 1, anonymization is applicable only when attributes in a database are independent and cannot be trivially extended to a multidimensional probability distribution such that there are attributes dependent on one another. FIG. 3 shows the above this. FIG. 3(a) is a perspective view, and FIG. 3(b) is a view from above. From FIG. 3, transition to a possible area is also prevented, which is different from what is to be achieved here. One of the points is to assume a simultaneous probability distribution and use a probability distribution having a hole from the simultaneous probability distribution to solve the above. Of course, this random number generation method is applicable to an arbitrary probability distribution and, therefore, can be used for privacy protection other than anonymization.

Second Embodiment

[0051] A procedure for generating a random number r∈R.sup.D the processing speed of which is faster than that of the procedure of the first embodiment will be shown below. In this procedure, a technique of an inverse function method is used.

[0052] For example, a random number generation apparatus of the second embodiment is provided with an arithmetic operation part 5 as shown in FIG. 4. The random number generation apparatus may be further provided with a function generating part 1 indicated by a broken line in FIG. 4.

[0053] For example, a random number generation method of the second embodiment is realized by each part of the random number generation apparatus performing a process of step S5 illustrated in FIG. 5 and described below.

[0054] The random number generation apparatus outputs a D-dimensional random number r=(r.sub.1, . . . ,r.sub.D).sup.T with the basic distribution function f and the hole [h] as input.

[0055] A probability H of a basic distribution function f(x.sub.1, . . . , x.sub.D) in the hole [h] is defined as below.

[Formula 6]

H=∫.sub.x.sub.1.sub.∈[h.sub.1.sub.]. . . ∫.sub.x.sub.D.sub.∈[h.sub.D.sub.]f(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.D

[0056] When α=1/(1−H), a corrected distribution function f′(x.sub.1, . . . , x.sub.D) is defined by Expressions (1) and (2).

[Formula 7]

f′(x.sub.1, . . . ,x.sub.D)=0 if x.sub.1∈[h.sub.1]∧ . . . ∧x.sub.D∈[h.sub.D]  (1)

f′(x.sub.1, . . . ,x.sub.D)=α.Math.f(x.sub.1, . . . ,x.sub.D) otherwise  (2)

[0057] For example, the random number generation apparatus is provided with the function generating part 1 that calculates the probability H and the corrected distribution function f′(x.sub.1 . . . , x.sub.D), and the function generating part 1 calculates the probability H and the corrected distribution f′(x.sub.1 . . . , x.sub.D) in advance before subsequent processes are performed (step S1). The random number generation apparatus may not be provided with the function generating part 1. In this case, in subsequent processes, as the probability H and the corrected distribution function f′(x.sub.1 . . . , x.sub.D), the random number generation apparatus uses those calculated by another apparatus in advance.

[0058] By performing, for each of i=1, . . . , D, a process for generating a random number u.sub.i∈[0,1], obtaining a random number r.sub.i=F.sup.−1(u.sub.i) according to f′(x.sub.i) using the generated u.sub.i, and x.sub.i=r.sub.i, the arithmetic operation part 5 obtains r=(r.sub.1, . . . ,r.sub.D).sup.T in the end (step S5), wherein f′(x.sub.i) is a peripheral distribution of f′(x.sub.1, . . . ,x.sub.D) of x.sub.i, F(t.sub.i) is a function defined by Expression (2′)

[Formula 8]

f′(x.sub.i)=∫.sub.−∞.sup.∞ . . . ∫.sub.−∞.sup.∞f′(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.i−1dx.sub.i+1 . . . dx.sub.D

F(t.sub.i)=∫.sub.−∞.sup.t.sup.if′(x.sub.i)dx.sub.i  (2′)

and F.sup.−1(t.sub.i) is an inverse function of F(t.sub.i).

[0059] The arithmetic operation part 5 may perform processes from step S50 to step S57 below to perform step S5.

[0060] For example, first, for i=1 (step S50), the arithmetic operation part 5 derives a peripheral distribution f′(x.sub.1) of f′(x.sub.1,x.sub.2, . . . ,x.sub.D) of x.sub.1 (step S51).

[Formula 9]

f′(x.sub.i)=∫.sub.−∞.sup.∞ . . . ∫.sub.−∞.sup.∞f′(x.sub.1, . . . ,x.sub.D)dx.sub.1 . . . dx.sub.i−1dx.sub.i+1 . . . dx.sub.D

[0061] Then, the arithmetic operation part 5 derives a cumulative density function F(t.sub.1) (step S52).

[Formula 10]

F(t.sub.i)=∫.sub.−∞.sup.t.sup.if′(x.sub.1)dx.sub.1

[0062] Then, the arithmetic operation part 5 derives F.sup.−1(t.sub.1) which is an inverse function of F(t.sub.1) (step S53).

[0063] Then, the arithmetic operation part 5 generates a random number u.sub.1∈[0,1] (step S54). The arithmetic operation part 5 generates, for example, a uniform random number u.sub.1∈[0,1] as the random number u.sub.1.

[0064] Then, the arithmetic operation part 5 obtains a random number r.sub.1F.sup.−1(u.sub.1) according to f′(x.sub.1) using the generated u.sub.1 (step S55). That is, the arithmetic operation part 5 calculates an output value in the case of inputting the generated u.sub.1 to F.sup.−1(t.sub.1) and sets the output value as r.sub.1.

[0065] Then, the arithmetic operation part 5 substitutes r.sub.1 for x.sub.1 of f′(x.sub.1, . . . ,x.sub.D) to obtain f′(x.sub.2, . . . ,x.sub.D|x.sub.1=r.sub.1) (step S56).

[0066] Then, for integers .sup.∀i∈[2,D], the arithmetic operation part 5 performs an operation similar to steps S51 to S56 described above for f′(x.sub.i, . . . ,x.sub.D|x.sub.1=r.sub.1, . . . ,x.sub.i−1=r.sub.i−1) to obtain r=(r.sub.1, . . . ,r.sub.D).sup.T (step S57).

[0067] As described above, a multidimensional probability distribution may be converted to one-dimensional peripheral distributions to sequentially generate random numbers using an inverse function method.

[0068] It is possible to generate random numbers according to a multidimensional probability distribution such that a probability in the hole [h], which is a predetermined area, is zero by the second embodiment as like as the first embodiment though the procedure for generating random numbers of the second embodiment is different from that of the first embodiment.

Specific Example 1

[0069] An example of the corrected distribution function f′ in the case of D=2 will be described below.

[0070] Where, N is a predetermined positive integer, and there are N predetermined possible ranges [h.sub.i] for the random variable x.sub.i. The N predetermined possible ranges are {[h.sub.i]}.sub.i=1.sup.N{([h.sub.1].sub.i,[h.sub.2].sub.i).sup.T}.sub.i=1.sup.N={([(s.sub.1).sub.i,(e.sub.1).sub.i],[(s.sub.2).sub.i,(e.sub.2).sub.i]).sup.T}.sub.i=1.sup.N. As described above, the number of holes is to be N.

[0071] Further, (μ.sub.x1,2σ.sub.x1.sup.2) and (μ.sub.x2,2σ.sub.x2.sup.2) are predetermined parameters, and the basic distribution function f′(x1, . . . , x.sub.D) is Laplace distribution Lap(x.sub.1,x.sub.2) defined by Expression (3). The Laplace distribution Lap(x.sub.1,x.sub.2) is shown in FIG. 6. FIG. 6(a) is a perspective view, and FIG. 6(b) is a view from above.

[00001]$\begin{array}{cc}\left[\mathrm{Formula}11\right]& \\ \mathrm{Lap}\left(x_1,x_2\right)=\frac{1}{2{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\frac{1}{2{\sigma }_{x_2}}\exp \left(-\frac{.Math.x_2-{\mu }_{x_2}.Math.}{{\sigma }_{x_2}}\right)& \left(3\right)\end{array}$

[0072] The sign(a) is a function that outputs a sign {+,−} of an input a, a function g(s,e) is defined by Expressions (5) and (6) when s≤e, and H is defined by Expression (4), then the corrected distribution function f′ is Lap′(x.sub.1,x.sub.2) defined by Expressions (7) and (8).

[00002]$\begin{array}{cc}\left[\mathrm{Formula}12\right]& \\ \begin{array}{c}H=\underset{i=1}{\overset{N}{.Math.}}\left\{{\int }_{{\left[h_2\right]}_i}{\int }_{{\left[h_1\right]}_i}Lap\left(x_1,x_2\right)d{x}_{1}d{x}_2\right\}\\ =\frac{1}{4}\underset{i=0}{\overset{N}{.Math.}}\left\{g\left({\left(s_1\right)}_i,{\left(e_1\right)}_i\right)g\left({\left(s_2\right)}_i,{\left(e_2\right)}_i\right)\right\}\end{array}& \left(4\right)\\ \left[\mathrm{Formula}13\right]& \\ g\left(s,e\right)=2-\exp \left(\frac{s-{\mu }_{x_1}}{{\sigma }_{x_1}}\right)-\exp \left(\frac{-e+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)\mathrm{if}s\le {\mu }_{x_1}.Math.{\mu }_{x_1}\le e& \left(5\right)\\ g\left(s,e\right)=\mathrm{sign}\left(e-{\mu }_{x_1}\right)\exp \left(-\frac{.Math.e-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)-\mathrm{sign}\left(s-{\mu }_{x_1}\right)\exp \left(-\frac{.Math.s-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}& \left(6\right)\\ \left[\mathrm{Formula}14\right]& \\ {\mathrm{Lap}}^{\text{'}}\left(x_1,x_2\right)=0\mathrm{if}{x}_1\in {\left[h_1\right]}_i.Math.\mathrm{.Math.}.Math.x_D\in {\left[h_D\right]}_i{.Math.}^{{\exists }_i}& \left(7\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1,x_2\right)=\frac{\alpha }{4{\sigma }_{x_1}{\sigma }_{x_2}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\exp \left(-\frac{.Math.x_2-{\mu }_{x_2}.Math.}{{\sigma }_{x_2}}\right)\mathrm{otherwise}& \left(8\right)\end{array}$

Specific Example 2

[0073] Where, an example of the processes from step S50 to step S56 of the second embodiment will be described.

[0074] The corrected distribution function f′ is Lap′(x.sub.1,x.sub.2) with one hole [h] that is shown in FIG. 7. FIG. 7(a) is a perspective view, and FIG. 7(b) is a view from above. As shown in FIG. 7, in the specific example 2, the number of [h] is one, and [h]([h.sub.1],[h.sub.2])=([(a),(b)],[(c),(d)]).

[0075] Where, a first area S.sub.1 is (x.sub.1≥μ.sub.x1)∧(x.sub.2≥μ.sub.x2), a second area S.sub.2 is (x.sub.1≤μ.sub.x1)∧(x.sub.2≥μ.sub.x2), a third area S.sub.3 is (x.sub.1≥μ.sub.x1)∧(x.sub.2≤μ.sub.x2) and a fourth area S.sub.4 is (x.sub.1≤μ.sub.x1)∧(x.sub.2≤μ.sub.x2).

[0076] First, a peripheral distribution of x.sub.1 will be considered in order to obtain a random number r.sub.1.

[0077] 1. If the hole [h] is in the first area S.sub.1 or the second area S.sub.2, the corrected distribution function f′ is Lap′(x.sub.1) defined by Expressions (9) and (10).

[00003]$\begin{array}{cc}\left[\mathrm{Formula}15\right]& \\ {\mathrm{Lap}}^{\text{'}}\left(x_1\right)=\frac{\alpha }{4{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\left(2-\exp \left(\frac{-c+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)+\exp \left(\frac{-d+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)\right)\mathrm{if}a\le x_1\le b& \left(9\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1\right)=\frac{\alpha }{2{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}& \left(10\right)\end{array}$

[0078] 2. If the hole [h] is in the third area S.sub.3 or the fourth area S.sub.4, the corrected distribution function f′ is Lap′(x.sub.1) defined by Expressions (11) and (12).

[00004]$\begin{array}{cc}\left[\mathrm{Formula}16\right]& \\ \mathrm{La}{p}^{\text{'}}\left(x_1\right)=\frac{\alpha }{4{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\left(2+\exp \left(\frac{c-{\mu }_{x_2}}{{\sigma }_{x_2}}\right)-\exp \left(\frac{d-{\mu }_{x_2}}{{\sigma }_{x_2}}\right)\right)\mathrm{if}a\le x_1\le b& \left(11\right)\\ {\mathrm{Lap}}^{\text{'}}\left(x_1\right)=\frac{\alpha }{2{\sigma }_{x_1}}\exp \left(-\frac{.Math.x_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\mathrm{otherwise}& \left(12\right)\end{array}$

[0079] If a hole is across areas, the above cases 1. and 2. can be combined. Next, in order to generate a random number r.sub.1, inverse functions shown by Expressions (13), (14), (15) and (16) are derived from the cumulative density function:

[Formula 17]

F(t.sub.i)=Lap′(x.sub.1≤t.sub.1)=∫.sub.−∞.sup.t.sup.iLap′(x.sub.1)dx.sub.1.

[0080] Since inverse functions can be derived in other areas by using a similar procedure, description will be made here on only a case where there is a hole in the first area.

[0081] Hereinafter,

[00005]$\begin{array}{cc}\beta =2-\exp \left(\frac{-c+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)+\exp \left(\frac{-d+{\mu }_{x_2}}{{\sigma }_{x_2}}\right)& \left[\mathrm{Formula}18\right]\end{array}$

[0082] i) When −∞≤t.sub.1≤μ.sub.x1:

[00006]$\begin{array}{cc}\left[\mathrm{Formula}19\right]& \\ t_1={\mu }_{x_1}+{\sigma }_{x_1}\log \left(\frac{2}{\alpha }F\left(t_1\right)\right)& \left(13\right)\end{array}$

[0083] ii) When μ.sub.x1≤t.sub.1≤a:

[00007]$\begin{array}{cc}\left[\mathrm{Formula}20\right]& \\ t_1={\mu }_{x_1}-{\sigma }_{x_1}\log \left(2-\frac{2}{\alpha }F\left(t_1\right)\right)& \left(14\right)\end{array}$

[0084] iii) When a≤t.sub.1≤b:

[00008]$\begin{array}{cc}\left[\mathrm{Formula}21\right]& \\ t_1={\mu }_{x_1}-{\sigma }_{x_1}\log \left(\frac{2}{\beta }\left(2-\frac{2}{\alpha }F\left(t_1\right)+\frac{\beta }{2}\exp \left(\frac{-a+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)-\exp \left(\frac{-a+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)\right)\right)& \left(15\right)\end{array}$

[0085] iv) When b≤t.sub.1:

[00009]$\begin{array}{cc}\left[\mathrm{Formula}22\right]& \\ t_1={\mu }_{x_1}-{\sigma }_{x_1}\log \left[2-\frac{2}{\alpha }F\left(t_1\right)-\exp \left(\frac{-a+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)+\frac{\beta }{2}\left(\exp \left(\frac{-a+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)-\exp \left(\frac{-b+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)\right)+\exp \left(\frac{-b+{\mu }_{x_1}}{{\sigma }_{x_1}}\right)\right)& \left(16\right)\end{array}$

[0086] By substituting u.sub.1∈[0,1] according to a uniform distribution U.sub.[0,1] for F(t.sub.1) of Expressions (13), (14), (15) and (16), the random number r.sub.1=t.sub.1 according to Expressions (9) and (10) is generated. A probability density function Lap′(x.sub.2|x.sub.1=r.sub.1) in the case of x.sub.1=r.sub.1 is as follows:

[00010]$\begin{array}{cc}\left[\mathrm{Formula}23\right]& \\ \mathrm{Lap}\text{'}\left(x_2|x_1=r_1\right)=0\mathrm{if}a\le r_1\le b.Math.c\le x_2\le d& \left(17\right)\\ \mathrm{La}{p}^{\text{'}}\left(x_2|x_1=r_1\right)=\frac{\alpha }{4{\sigma }_{x_1}{\sigma }_{x_2}}\exp \left(-\frac{.Math.r_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)\exp \left(-\frac{.Math.x_2-{\mu }_{x_2}.Math.}{{\sigma }_{x_2}}\right)\mathrm{otherwise}& \left(18\right)\end{array}$

[0087] Where, γ is defined by the following expression:

[00011]$\begin{array}{cc}\gamma =\exp \left(-\frac{.Math.r_1-{\mu }_{x_1}.Math.}{{\sigma }_{x_1}}\right)& \left[\mathrm{Formula}24\right]\end{array}$

[0088] At this time, in order to generate a random number r.sub.2, inverse functions shown in Expressions (19), (20) and (21) are derived from the cumulative density function:

[Formula 25]

F(t.sub.2)=Lap′(x.sub.2≤t.sub.2)=∫.sub.−∞.sup.t.sup.2Lap′(x.sub.2)dx.sub.2

[0089] i) When −∞≤t.sub.2≤μ.sub.x2:

[00012]$\begin{array}{cc}\left[\mathrm{Formula}26\right]& \\ t_2={\mu }_{x_2}+{\sigma }_{x_2}\log \left(\frac{4}{\mathrm{\alpha \gamma }}F\left(t_2\right)\right)& \left(19\right)\end{array}$

[0090] ii) When μ.sub.x2≤t.sub.2≤c:

[00013]$\begin{array}{cc}\left[\mathrm{Formula}27\right]& \\ t_2={\mu }_{x_2}-{\sigma }_{x_2}\log \left(2-\frac{4}{\alpha \gamma }F\left(t_2\right)\right)& \left(20\right)\end{array}$

[0091] iii) When c≤t.sub.2≤d, F(t.sub.2) is determined regardless of t.sub.2. Therefore, an inverse function does not exist. That is, random numbers within this range are not generated.

[0092] iv) When d≤t.sub.2:

[00014]$\begin{array}{cc}\left[\mathrm{Formula}28\right]& \\ t_2={\mu }_{x_2}-{\sigma }_{x_2}\log \left(\beta -\frac{4}{\mathrm{\alpha \gamma }}F\left(t_2\right)\right)& \left(21\right)\end{array}$

[0093] By substituting u.sub.2∈[0,1] according to a uniform distribution U.sub.[0,1] for F(t.sub.2) of Expressions (19), (20) and (21), the random number r.sub.2=t.sub.2 according to Expressions (17) and (18) is generated. In this way, r=(r.sub.1,r.sub.2).sup.T is generated.

[0094] [Program and Recording Medium]

[0095] When each process of the random number generation apparatus is realized by a computer, processing content of functions that the random number generation apparatus should have is written by a program. By executing the program by computer, the processes of the random number generation apparatus are realized on the computer.

[0096] The program in which the processing content is written can be recorded to a computer-readable recording medium. As the computer-readable recording medium, any recording medium, for example, a magnetic recording device, an optical disk, magneto-optical recording medium or a semiconductor memory is possible.

[0097] Each processing part may be configured by causing a predetermined program to be executed on the computer, or at least a part of processing content of the processing part may be realized as hardware.

[0098] [Modification]

[0099] It goes without saying that the present invention can be appropriately modified within a range not departing from the spirit of the invention.