# RANDOM NUMBER GENERATION APPARATUS, METHOD AND PROGRAM

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

## Latest NIPPON TELEGRAPH AND TELEPHONE CORPORATION Patents:

- DIAGNOSTIC APPARATUS
- VIDEO TRANSMISSION DEVICE AND VIDEO TRANSMISSION METHOD
- ANOMALY DETECTION APPARATUS, PROBABILITY DISTRIBUTION LEARNING APPARATUS, AUTOENCODER LEARNING APPARATUS, DATA TRANSFORMATION APPARATUS, AND PROGRAM
- IMAGE PROCESSING APPARATUS, IMAGE PROCESSING METHOD AND IMAGE PROCESSING PROGRAM
- LEARNING DEVICE, LEARNING METHOD, AND LEARNING PROGRAM

**Description**

**TECHNICAL FIELD**

The present invention relates to a technique for generating random numbers.

**BACKGROUND ART**

Patent Literature 1 has been known as a noise addition method that has been conventionally used in anonymization, one of privacy protection techniques (for example, Non-patent literatures 1, 2, 3 4 and 5).

A subject in the above patent literature is to generate random numbers according to an arbitrary probability distribution of an arbitrary dimension.

**PRIOR ART LITERATURE**

**Patent Literature**

- Patent literature 1: Japanese Patent Application Laid-Open No. 2014-081545

**Non-Patent Literature**

- Non-patent literature 1: Dai Ikarashi, Koji Chida, Katsumi Takahashi, “Efficient Privacy-preserving Cross Tabulation for Multi-valued Attributes”, Papers of Information Processing Society Symposium, Volume 2008, No. 8, 1st Volume, pp. 497-502, Oct. 8, 2008
- Non-patent literature 2: Dai Ikarashi, Koji Chida, Katsumi Takahashi, “A Probabilistic Extension of k-Anonimity”, CSS2009, Volume 2009, pp. 1-6, October 2009
- Non-patent literature 3: Dai Ikarashi, Koji Chida, Katsumi Takahashi, “Randomized k-Anonymization for Numeric Attributes”, CSS2011, Volume 2011, No. 3, pp. 450-455, Oct. 12, 2011
- Non-patent literature 4: Dai Ikarashi, Satoshi Hasegawa, Tatsuya Osame, Ryo Kikuchi, Koji Chida, “A Privacy Preserving Cross-tabulation which Guarantees k-Anonymity by Randomization for Numeric Attributes”, Volume 2012, No. 3, pp. 639-646, Oct. 23, 2012
- Non-patent literature 5: Ryo Kikuchi, Dai Igarashi, Koji Chida, Koki Hamada, “Data-Dependent Pk-Anonymization Method for Publishing Useful Anonymized Table”, SCIS2013

**SUMMARY OF THE INVENTION**

**Problems to be Solved by the Invention**

One of methods for protecting privacy of personal data in a database is anonymization.

In order to anonymize numerical attributes, an anonymization method of causing each attribute value to transition to another attribute value using a random number according to a probability distribution called Laplace distribution (Non-patent literatures 2, 3 and 4) may be used. As an example of numerical attribute personal data, an example of position information (latitude/longitude) about a person will be considered. Though there is almost no possibility that a person exists in an area of the sea other than routes, it may seem as if a person existed in the area due to anonymization.

In order to anonymize a discrete attribute called a category attribute, which is not a numerical attribute, an anonymization method of causing the discrete attribute value to transition to another attribute value with a probability ρ may be used (Non-patent literatures 1 and 5). As an example of the category attribute, purchase information about a person will be considered. Though there cannot be a person who purchases a movie ticket of a high school student price and an alcoholic drink, it may seem as if such a person that belongs to the category area existed due to anonymization.

A reason why such state transition of a numerical attribute and a category attribute occurs is that a random number included in the impossible area is generated.

In order to prevent such impossible state transition, it is necessary to generate random numbers according to a multidimensional probability distribution of an arbitrary dimension such that a probability in an impossible area is zero. A method for generating such random numbers, however, has not been proposed yet.

The present invention is intended to provide a random number generation apparatus, method and program for generating random numbers according to a multidimensional probability distribution such that a probability in a predetermined area is zero.

**Means to Solve the Problems**

A random number generation apparatus according to one aspect of the present invention comprises:

a first random number generating part generating a random number u=(u_{1}, . . . ,u_{D})^{T}∈[−∞,∞]^{D};

a second random number generating part generating a random number v∈[0,f′_{max}]; and

a determining part determining whether f′(x_{1}=u_{1}, . . . ,x_{D}=u_{D})≥v or not, and, if f′(x_{1}=u_{1}, . . . ,x_{D}=u_{D})≥v, adopting u as a random number according to f′(x_{1}, . . . ,x_{D}), wherein

D is a predetermined positive integer, for i=1, . . . ,D, [h_{i}] is a predetermined possible range for a random variable x_{i}, a hole [h] is [h]=([h_{1}], . . . ,[h_{D}])^{T}, H is a probability of a predetermined basic distribution function f(x_{1}, . . . ,x_{D}) in the hole [h], α=1/(1−H), a corrected distribution function f′(x_{1}, . . . ,x_{D}) is defined by Expressions (1) and (2):

[Formula 1]

*H=∫*_{x}_{1}_{∈[h}_{1}_{]}. . . ∫_{x}_{D}_{∈[h}_{D}_{]}*f*(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{D }

*f*′(*x*_{1}*, . . . ,x*_{D})=0 if *x*_{1}∈[*h*_{1}]*∧ . . . ∧x*_{D}∈[*h*_{D}] (1)

*f*′(*x*_{1}*, . . . ,x*_{D})=α·*f*(*x*_{1}*, . . . ,x*_{D}) otherwise (2)

and f′_{max }is a maximum value of f′(x_{1}, . . . ,x_{D}).

A random number generation apparatus according to another aspect of the present invention comprises:

an arithmetic operation part obtaining r=(r_{1}, . . . ,r_{D})^{T }in the end, by performing, for each of i=1, . . . ,D, a process for generating a random number u_{i}ç[0,1], obtaining a random number r_{i}=F^{−1}(u_{i}) according to f′(x_{i}) using the generated u_{i}, and x_{i}=r_{i}, wherein

D is a predetermined positive integer, for i=1, . . . ,D, [h_{i}] is a predetermined possible range for a random variable x_{i}, a hole [h] is [h]=([h_{1}], . . . ,[h_{D}])^{T}, H is a probability of a predetermined basic distribution function f(x_{1}, . . . ,x_{D}) in the hole [h], α=1/(1−H), a corrected distribution function f′(x_{1}, . . . ,x_{D}) is defined by Expressions (1) and (2):

[Formula 2]

*H=∫*_{x}_{1}_{∈[h}_{1}_{]}. . . ∫_{x}_{D}_{∈[h}_{D}_{]}*f*(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{D }

*f*′(*x*_{1}*, . . . ,x*_{D})=0 if *x*_{1}∈[*h*_{1]}*∧ . . . ∧x*_{D}∈[*h*_{D}] (1)

*f*′(*x*_{1}*, . . . ,x*_{D})=α·*f*(*x*_{1}*, . . . ,x*_{D}) otherwise (2)

f′(x_{i}) is a peripheral distribution of f′(x_{1}, . . . ,x_{D}) of x_{i}, F(t_{1}) is a function defined by Expression (2′):

[Formula 3]

*f*′(*x*_{i})=∫_{−∞}^{∞} . . . ∫_{−∞}^{∞}*f*′(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{i−1}*dx*_{i+1 }*. . . dx*_{D }

*F*(*t*_{i})=∫_{−∞}^{t}^{i}*f*′(*x*_{i})*dx*_{i} (2′)

and F^{−1}(t_{i}) is an inverse function of F(t_{i}).

**Effects of the Invention**

It is possible to generate random numbers according to a multidimensional distribution such that a probability in a predetermined area is zero.

**BRIEF DESCRIPTION OF THE DRAWINGS**

**DETAILED DESCRIPTION OF THE EMBODIMENTS**

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

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

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.

A hole [h]=([h_{1}], . . . ,[h_{D}])^{T }is a hypercube in D-dimensional space, and each [h_{i}] indicates a range [s_{i},e_{i}] for a random variable x_{i}.

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

**First Embodiment**

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 **1** indicated by a broken line in

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 S**2** to step S**4** illustrated in

Hereinafter, when the basic distribution function f is given, a procedure for generating a random number r∈R^{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′_{max}.

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

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

[Formula 4]

*H=∫*_{x}_{1}_{∈[h}_{1}_{]}. . . ∫_{x}_{D}_{∈[h}_{D}_{]}*f*(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{D }

When α=1/(1−H), a corrected distribution function f(x_{1}, . . . , x_{D}) is defined by Expressions (1) and (2).

[Formula 5]

*f*′(*x*_{1}*, . . . ,x*_{D})=0 if *x*_{1}∈[*h*_{1}]*∧ . . . ∧x*_{D}∈[*h*_{D}] (1)

*f*′(*x*_{1}*, . . . ,x*_{D})=α·*f*(*x*_{1}*, . . . ,x*_{D}) otherwise (2)

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_{1 }. . . , x_{D}), and the function generating part **1** calculates the probability H and the corrected distribution f′(x_{1 }. . . , x_{D}) in advance before subsequent processes are performed (step S**1**). 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_{1 }. . . , x_{D}), the random number generation apparatus uses those calculated by another apparatus in advance.

The first random number generating part **2** generates a random number u=(u_{1}, . . . ,u_{D})^{T}∈[−∞,∞]^{D }(step S**2**). The first random number generating part **2** generates, for example, a uniform random number u=(u_{1}, . . . ,u_{D})^{T}∈[−∞,∞]^{D }as the random number u. The generated random number u is outputted to the determining part **4**.

The second random number generating part **3** generates a random number v∈[0,f′_{max}] (step S**3**). The second random number generating part **3** generates a uniform random number v∈[0,f′_{max}] as the random number v. The generated random number v is outputted to the determining part **4**.

The determining part **4** determines whether f′(x_{1}=u_{1}, . . . ,x_{D}=u_{D})≥v or not. If f′(x_{1}=u_{1}, . . . ,x_{D}=u_{D})≥v, the determining part **4** adopts the u as a random number according to f′(x_{1}, . . . ,x_{D}) and outputs the random number u (step S**4**).

If f′(x_{1}=u_{1}, . . . ,x_{D}=u_{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 S**2** and S**3**, 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 S**2** and S**3**, respectively, until f′(x_{1}=u_{1}, . . . ,x_{D}=u_{D})≥v.

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.

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.

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. *a*)*b*)

**Second Embodiment**

A procedure for generating a random number r∈R^{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.

For example, a random number generation apparatus of the second embodiment is provided with an arithmetic operation part **5** as shown in **1** indicated by a broken line in

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 S**5** illustrated in

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

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

[Formula 6]

*H=∫*_{x}_{1}_{∈[h}_{1}_{]}. . . ∫_{x}_{D}_{∈[h}_{D}_{]}*f*(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{D }

When α=1/(1−H), a corrected distribution function f′(x_{1}, . . . , x_{D}) is defined by Expressions (1) and (2).

[Formula 7]

*f*′(*x*_{1}*, . . . ,x*_{D})=0 if *x*_{1}∈[*h*_{1}]*∧ . . . ∧x*_{D}∈[*h*_{D}] (1)

*f*′(*x*_{1}*, . . . ,x*_{D})=α·*f*(*x*_{1}*, . . . ,x*_{D}) otherwise (2)

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_{1 }. . . , x_{D}), and the function generating part **1** calculates the probability H and the corrected distribution f′(x_{1 }. . . , x_{D}) in advance before subsequent processes are performed (step S**1**). 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_{1 }. . . , x_{D}), the random number generation apparatus uses those calculated by another apparatus in advance.

By performing, for each of i=1, . . . , D, a process for generating a random number u_{i}∈[0,1], obtaining a random number r_{i}=F^{−1}(u_{i}) according to f′(x_{i}) using the generated u_{i}, and x_{i}=r_{i}, the arithmetic operation part **5** obtains r=(r_{1}, . . . ,r_{D})^{T }in the end (step S**5**), wherein f′(x_{i}) is a peripheral distribution of f′(x_{1}, . . . ,x_{D}) of x_{i}, F(t_{i}) is a function defined by Expression (2′)

[Formula 8]

*f*′(*x*_{i})=∫_{−∞}^{∞} . . . ∫_{−∞}^{∞}*f*′(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{i−1}*dx*_{i+1 }*. . . dx*_{D }

*F*(*t*_{i})=∫_{−∞}^{t}^{i}*f*′(*x*_{i})*dx*_{i} (2′)

and F^{−1}(t_{i}) is an inverse function of F(t_{i}).

The arithmetic operation part **5** may perform processes from step S**50** to step S**57** below to perform step S**5**.

For example, first, for i=1 (step S**50**), the arithmetic operation part **5** derives a peripheral distribution f′(x_{1}) of f′(x_{1},x_{2}, . . . ,x_{D}) of x_{1 }(step S**51**).

[Formula 9]

*f*′(*x*_{i})=∫_{−∞}^{∞} . . . ∫_{−∞}^{∞}*f*′(*x*_{1}*, . . . ,x*_{D})*dx*_{1 }*. . . dx*_{i−1}*dx*_{i+1 }*. . . dx*_{D }

Then, the arithmetic operation part **5** derives a cumulative density function F(t_{1}) (step S**52**).

[Formula 10]

*F*(*t*_{i})=∫_{−∞}^{t}^{i}*f*′(*x*_{1})*dx*_{1 }

Then, the arithmetic operation part **5** derives F^{−1}(t_{1}) which is an inverse function of F(t_{1}) (step S**53**).

Then, the arithmetic operation part **5** generates a random number u_{1}∈[0,1] (step S**54**). The arithmetic operation part **5** generates, for example, a uniform random number u_{1}∈[0,1] as the random number u_{1}.

Then, the arithmetic operation part **5** obtains a random number r_{1}F^{−1}(u_{1}) according to f′(x_{1}) using the generated u_{1 }(step S**55**). That is, the arithmetic operation part **5** calculates an output value in the case of inputting the generated u_{1 }to F^{−1}(t_{1}) and sets the output value as r_{1}.

Then, the arithmetic operation part **5** substitutes r_{1 }for x_{1 }of f′(x_{1}, . . . ,x_{D}) to obtain f′(x_{2}, . . . ,x_{D}|x_{1}=r_{1}) (step S**56**).

Then, for integers ^{∀}i∈[2,D], the arithmetic operation part **5** performs an operation similar to steps S**51** to S**56** described above for f′(x_{i}, . . . ,x_{D}|x_{1}=r_{1}, . . . ,x_{i−1}=r_{i−1}) to obtain r=(r_{1}, . . . ,r_{D})^{T }(step S**57**).

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.

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**

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

Where, N is a predetermined positive integer, and there are N predetermined possible ranges [h_{i}] for the random variable x_{i}. The N predetermined possible ranges are {[h_{i}]}_{i=1}^{N}{([h_{1}]_{i},[h_{2}]_{i})^{T}}_{i=1}^{N}={([(s_{1})_{i},(e_{1})_{i}],[(s_{2})_{i},(e_{2})_{i}])^{T}}_{i=1}^{N}. As described above, the number of holes is to be N.

Further, (μ_{x1},2σ_{x1}^{2}) and (μ_{x2},2σ_{x2}^{2}) are predetermined parameters, and the basic distribution function f′(x**1**, . . . , x_{D}) is Laplace distribution Lap(x_{1},x_{2}) defined by Expression (3). The Laplace distribution Lap(x_{1},x_{2}) is shown in *a*)*b*)

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_{1},x_{2}) defined by Expressions (7) and (8).

**Specific Example 2**

Where, an example of the processes from step S**50** to step S**56** of the second embodiment will be described.

The corrected distribution function f′ is Lap′(x_{1},x_{2}) with one hole [h] that is shown in *a*)*b*)_{1}],[h_{2}])=([(a),(b)],[(c),(d)]).

Where, a first area S_{1 }is (x_{1}≥μ_{x1})∧(x_{2}≥μ_{x2}), a second area S_{2 }is (x_{1}≤μ_{x1})∧(x_{2}≥μ_{x2}), a third area S_{3 }is (x_{1}≥μ_{x1})∧(x_{2}≤μ_{x2}) and a fourth area S_{4 }is (x_{1}≤μ_{x1})∧(x_{2}≤μ_{x2}).

First, a peripheral distribution of x_{1 }will be considered in order to obtain a random number r_{1}.

1. If the hole [h] is in the first area S_{1 }or the second area S_{2}, the corrected distribution function f′ is Lap′(x_{1}) defined by Expressions (9) and (10).

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

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

[Formula 17]

*F*(*t*_{i})=Lap′(*x*_{1}*≤t*_{1})=∫_{−∞}^{t}^{i}Lap′(*x*_{1})*dx*_{1}.

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.

Hereinafter,

i) When −∞≤t_{1}≤μ_{x1}:

ii) When μ_{x1}≤t_{1}≤a:

iii) When a≤t_{1}≤b:

iv) When b≤t_{1}:

By substituting u_{1}∈[0,1] according to a uniform distribution U_{[0,1] }for F(t_{1}) of Expressions (13), (14), (15) and (16), the random number r_{1}=t_{1 }according to Expressions (9) and (10) is generated. A probability density function Lap′(x_{2}|x_{1}=r_{1}) in the case of x_{1}=r_{1 }is as follows:

Where, γ is defined by the following expression:

At this time, in order to generate a random number r_{2}, inverse functions shown in Expressions (19), (20) and (21) are derived from the cumulative density function:

[Formula 25]

*F*(*t*_{2})=Lap′(*x*_{2}*≤t*_{2})=∫_{−∞}^{t}^{2}Lap′(*x*_{2})*dx*_{2 }

i) When −∞≤t_{2}≤μ_{x2}:

ii) When μ_{x2}≤t_{2}≤c:

iii) When c≤t_{2}≤d, F(t_{2}) is determined regardless of t_{2}. Therefore, an inverse function does not exist. That is, random numbers within this range are not generated.

iv) When d≤t_{2}:

By substituting u_{2}∈[0,1] according to a uniform distribution U_{[0,1] }for F(t_{2}) of Expressions (19), (20) and (21), the random number r_{2}=t_{2 }according to Expressions (17) and (18) is generated. In this way, r=(r_{1},r_{2})^{T }is generated.

[Program and Recording Medium]

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.

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.

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.

[Modification]

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

## Claims

1. A random number generation apparatus, comprising: and f′fax is a maximum value of f′(x1,...,xD).

- a first random number generating part generating a random number u=(u1,...,uD)T∈[−∞,∞]D;

- a second random number generating part generating a random number v∈[0,f′max]; and

- a determining part determining whether f′(x1=u1,...,xD=uD)≥v or not, and, if f′(x1=u1,...,xD=uD)≥v, adopting u as a random number according to f′(x1,...,xD), wherein

- D is a predetermined positive integer, for i=1,...,D, [hi] is a predetermined possible range for a random variable xi, a hole [h] is [h]=([h1],...,[hD])T, H is a probability of a predetermined basic distribution function f(x1,...,xD) in the hole [h], α=1/(1−H), a corrected distribution function f′(x1,...,xD) is defined by Expressions (1) and (2): [Formula 29] H=∫x1∈[h1]... ∫xD∈[hD]f(x1,...,xD)dx1... dxD f′(x1,...,xD)=0 if x1∈[h1]∧... ∧xD∈[hD] (1) f′(x1,...,xD)=α·f(x1,...,xD) otherwise (2)

2. A random number generation apparatus comprising: f′(xi) is a peripheral distribution of f′(x1,...,xD) of xi, F(ti) is a function defined by Expression (2′): and F−1(ti) is an inverse function of F(ti).

- an arithmetic operation part obtaining r=(r1,...,rD)T in the end, by performing, for each of i=1,...,D, a process for generating a random number ui∈[0,1], obtaining a random number ri=F−1(ui) according to f′(xi) using the generated and xi=ri, wherein

- D is a predetermined positive integer, for i=1,...,D, [hi] is a predetermined possible range for a random variable xi, a hole [h] is [h]=([h1],...,[hD])T, H is a probability of a predetermined basic distribution function f(x1,...,xD) in the hole [h], α=1/(1−H), a corrected distribution function f′(x1,...,xD) is defined by Expressions (1) and (2): [Formula 30] H=∫x1∈[h1]... ∫xD∈[hD]f(x1,...,xD)dx1... dxD f′(x1,...,xD)=0 if x1∈[h1]∧... ∧xD∈[hD] (1) f′(x1,...,xD)=α·f(x1,...,xD) otherwise (2)

- [Formula 31]

- f′(xi)=∫−∞∞... ∫−∞∞f′(x1,...,xD)dx1... dxi−1dxi+1... dxD

- F(ti)=∫−∞tif′(xi)dxi (2′)

3. The random number generation apparatus according to claim 1 or 2, wherein [ Formula 32 ] Lap ( x 1, x 2 ) = 1 2 σ x 1 exp ( - x 1 - μ x 1 σ x 1 ) 1 2 σ x 2 exp ( - x 2 - μ x 2 σ x 2 ) ( 3 ) [ Formula 33 ] H = ∑ i = 1 N { ∫ [ h 2 ] i ∫ [ h 1 ] i L a p ( x 1, x 2 ) d x 1 d x 2 } = 1 4 ∑ i = 0 N { g ( ( s 1 ) i, ( e 1 ) i ) g ( ( s 2 ) i, ( e 2 ) i ) } ( 4 ) [ Formula 34 ] g ( s, e ) = 2 - exp ( s - μ x 1 σ x 1 ) - exp ( - e + μ x 1 σ x 1 ) if s ≤ μ x 1 ⋀ μ x 1 ≤ e ( 5 ) g ( s, e ) = sign ( e - μ x 1 ) exp ( - e - μ x 1 σ x 1 ) - sign ( s - μ x 1 ) exp ( - s - μ x 1 σ x 1 ) otherwise ( 6 ) [ Formula 35 ] Lap ' ( x 1, x 2 ) = 0 if x 1 ∈ [ h 1 ] i ⋀ ⋯ ⋀ x D ∈ [ h D ] i ❘ ∃ i ( 7 ) Lap ' ( x 1, x 2 ) = α 4 σ x 1 σ x 2 exp ( - x 1 - μ x 1 σ x 1 ) exp ( - x 2 - μ x 2 σ x 2 ) otherwise. ( 8 )

- when D=2, N is a predetermined positive integer, there are N predetermined possible ranges [hi] for the random variable xi, the N predetermined possible ranges are {[hi]}i=1N{([h1]i,[h2]i)T}i=1N={([(s1)i,(e1)i],[(s2)i,(e2)i])T}i=1N, (μx1,2σx12),(μx2,2σx22) are predetermined parameters, the basic distribution function f(x1,...,xD) is Lap(x1,x2) 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′(x1,x2) defined by Expressions (7) and (8):

4. The random number generation apparatus according to claim 2, wherein [ Formula 36 ] La p ' ( x 1 ) = α 4 σ x 1 exp ( - x 1 - μ x 1 σ x 1 ) ( 2 - exp ( - c + μ x 2 σ x 2 ) + exp ( - d + μ x 2 σ x 2 ) ) if a ≤ x 1 ≤ b ( 9 ) Lap ' ( x 1 ) = α 2 σ x 1 exp ( - x 1 - μ x 1 σ x 1 ) otherwise ( 10 ) La p ' ( x 1 ) = α 4 σ x 1 exp ( - x 1 - μ x 1 σ x 1 ) ( 2 + exp ( c - μ x 2 σ x 2 ) - exp ( d - μ x 2 σ x 2 ) ) if a ≤ x 1 ≤ b ( 11 ) Lap ' ( x 1 ) = α 2 σ x i exp ( - x 1 - μ x 1 σ x 1 ) otherwise. ( 12 )

- when D=2, the predetermined possible range [hi] for the random variable xi is [hi]=([h1]i,[h2]i)T=([a,b],[c,d])T, (μx1,2σx12) and (μx2,2σx22) are predetermined parameters, a first area S1 is (x1≥μx1)∧(x2≥μx2), a second area S2 is (x1≤μx1)∧(x2≥μx2), a third area S3 is (x1≥μx1)∧(x2≤μx2) and a fourth area S4 is (x1≤μx1)∧(x2≤μx2), if the hole [h] is in the first area S1 or the second area S2, the corrected distribution function f′ is Lap′(x1) defined by Expressions (9) and (10), and if the hole [h] is in the third area S3 or the fourth area S4, the corrected distribution function f′ is Lap′(x1) defined by Expressions (11) and (12):

5. A random number generation method comprising: and f′max is a maximum value of f′(x1,...,xD).

- a first random number generating step of a first random number generating part generating a random number u=(u1,...,uD)T∈[−∞,∞]D;

- a second random number generating step of a second random number generating part generating a random number v∈[0,f′max]; and

- a determining step of a determining part determining whether f′(x1=u1,...,xD=uD)≥v or not, and, if f′(x1=u1,...,xD=uD)≥v, adopting u as a random number according to f′(x1,...,xD), wherein

- D is a predetermined positive integer, for i=1,...,D, [hi] is a predetermined possible range for a random variable x a hole [h] is [h]=([h1],...,[hD])T, H is a probability of a predetermined basic distribution function f(x1,...,xD) in the hole [h], α=1/(1−H), a corrected distribution function f′(x1,...,xD) is defined by Expressions (1) and (2): [Formula 37] H=∫x1∈[h1]... ∫xD∈[hD]f(x1,...,xD)dx1... dxD f′(x1,...,xD)=0 if x1∈[h1]∧... ∧xD∈[hD] (1) f′(x1,...,xD)=α·f(x1,...,xD) otherwise (2)

6. A random number generation method, comprising: f′(xi) is a peripheral distribution of f′(x1,...,xD) of xi, F(ti) is a function defined by Expression (2′): and F−1(ti) is an inverse function of F(ti).

- an arithmetic operation step of an arithmetic operation part obtaining r=(r1,...,rD)T in the end, by performing, for each of i=1,...,D, a process for generating a random number ui∈[0,1], obtaining a random number ri=F−1(ui) according to f′(xi) using the generated and xi=ri, wherein

- D is a predetermined positive integer, for i=1,...,D, [hi] is a predetermined possible range for a random variable xi, a hole [h] is [h]([h1],...,[hD])T, H is a probability of a predetermined basic distribution function f(x1,...,xD) in the hole [h], α=1/(1−H), a corrected distribution function f′(x1,...,xD) is defined by Expressions (1) and (2): [Formula 38] H=∫x1∈[h1]... ∫xD∈[hD]f(x1,...,xD)dx1... dxD f′(x1,...,xD)=0 if x1∈[h1]∧... ∧xD∈[hD] (1) f′(x1,...,xD)=α·f(x1,...,xD) otherwise (2)

- [Formula 39]

- f′(xi)=∫−∞∞... ∫−∞∞f′(x1,...,xD)dx1... dxi−1dxi+1... dxD

- F(ti)=∫−∞tif′(xi)dxi (2′)

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

**Patent History**

**Publication number**: 20210286593

**Type:**Application

**Filed**: Jan 12, 2018

**Publication Date**: Sep 16, 2021

**Applicant**: NIPPON TELEGRAPH AND TELEPHONE CORPORATION (Chiyoda-ku)

**Inventors**: Rina OKADA (Musashino-chi), Satoshi HASEGAWA (Musashino-chi), Shogo MASAKI (Musashino-chi)

**Application Number**: 16/476,728

**Classifications**

**International Classification**: G06F 7/58 (20060101); G06F 17/18 (20060101);