Cryptography – Electric signal modification
Reexamination Certificate
1997-02-14
2001-03-27
Cangialosi, Salvatore (Department: 2661)
Cryptography
Electric signal modification
C380S030000
Reexamination Certificate
active
06208738
ABSTRACT:
FIELD OF INVENTION
The present invention relates in general to a method of accelerating an integral evaluation computer program with an acceleration program without disclosing the internal execution and functionality of the programs. More specifically, the present invention is an interface which allows a program to evaluate a secret integral by the Monte Carlo method using a sequence of numbers provided by a sequence generation program while protecting the secrecy of the sequence generation program.
BACKGROUND OF INVENTION
The Monte Carlo method provides approximate solutions to mathematical problems by performing statistical sampling calculations on a computer. The method was developed originally during the middle 1940's as part of research for the atomic bomb program at Los Alamos. It can be used for problems which are inherently probabilistic and for problems that are apparently deterministic. An example of the former is the simulation of random neutron diffusion in a nuclear reactor. An example of the latter is the calculation of the energy levels of a quantum system. The Monte Carlo method is a standard tool in the science and finance fields. An overview of the Monte Carlo method which includes detailed explanations of the examples above is M. H. Kalos and P. A. Whitlock, “Monte Carlo Methods Volume I: Basics,” pp. 7-37 (Wiley, New York, 1986).
The Monte Carlo method is widely used for many applications in scientific research, applied technology and finance. These include but are not limited to: simulation of the thermal properties of materials such as magnets and superconductors; simulation of the properties of industrially important polymer molecules such as polyethylene and proteins; the valuation of derivative securities such as interest rate derivatives or mortgage-backed securities; the estimation of the risk inherent in a portfolio of diverse financial instruments such as stocks, bonds, commodities and options; and the generation of realistic three-dimensional graphical images.
In such applications and others, the Monte Carlo method is used to estimate a statistical quantity appropriate for the application: typically this is an average value of a quantity computed with respect to a known probability distribution. The Monte Carlo method can also be used to provide estimates of the value of integrals of any dimension. The output from all of the calculations described above is usually either displayed on a computer screen or printed.
In the case of financial applications, such as interest-rate derivatives or mortgage backed securities, the Monte Carlo method is used because the complexity of the transactions and cash flows in the specification of the derivative security in question prevents the use of known alternative, faster methods of derivative valuation. Indeed, it is a generally held view that the Monte Carlo method is the most dependable and versatile technique at the disposal of practitioners in financial derivatives, and one robust enough so it may always be used if alternative techniques fail for any reason.
In many cases of practical interest, it is possible to equate the results of the Monte Carlo method to the solution of an appropriate differential equation associated with the statistical properties of the application of interest. When this can be done, it is advantageous if the speed of calculation is important to the user, because the differential equation is typically solvable by so-called lattice or finite-difference methods, known to those skilled in the art. In the particular context of financial applications, these lattice methods are known as tree methods, and are described by Jon C. Hull, “Options, Futures and Other Derivative Securities, 2d. Ed.,” Chpt. 14 (Prentice Hall, Englewood Cliffs, 1993). The tree methods and the Monte Carlo method are completely equivalent mathematically, but differ in the manner of implementation.
Monte Carlo problems are typically formulated as multi-dimensional integrals, which without loss of generality can be taken to be over a unit hypercube. For example, the value of a derivative security can be represented as an integral over a multi-dimensional unit cube, as shown by S. H. Paskov and J. F. Traub,
Journal of Portfolio Management
, pp. 113-120, (Fall 1995). The dimension of the cube is determined by the underlying stochastic processes and the number of discrete time intervals involved in the specification of the derivative security.
The evaluation of an integral by the Monte Carlo method is performed by (i) choosing a number, N, of points at random in the multi-dimensional cube; (ii) evaluating the integrand at those points; and (iii) averaging the value of the integrand at those points to obtain the estimate of the integral. Thus the Monte Carlo estimate of the integral:
I=ƒ
f
(
x
)
d
D
x
of a function f(x), where x is a point in a D-dimensional hypercube, is given by the large N limit of:
I
=
(
1
/
N
)
∑
i
=
1
N
f
(
x
i
)
where the sum runs from i=1 to N and x
1
is a sequence of random points in the D-dimensional hypercube. In present integrations performed on a digital computer, the points are chosen from a pseudo-random sequence generation program, such as those provided with many compilers. An example is the “rand ()” function provided with draft compliant ANSI C++ language.
Monte Carlo problems can also be formulated directly as simulations of the underlying stochastic process. For example, as is well known to those skilled in the art, and explained by John C. Hull, “Options, Futures and Other Derivative Securities 2d. Ed.,” pp. 330-331 (Prentice Hall, Englewood Cliffs, 1993), the behavior of a stock price over time is sometimes modeled as random fluctuations superimposed on a steadily increasing average price. The time series for the change in value of the stock at the end of the day over a particular set of (e.g. 360) consecutive trading days constitutes a realization or particular scenario of the random price movements. In the following 360 day period the time series for the stock price movements would follow a different scenario. A derivative security whose value is some predetermined function of the stock price will have a value at the end of each 360 day period which in general depends upon the entire time series for the stock during each scenario. The average value for the derivative security 360 days from a given date can be calculated by simulating on a computer a large number N (e.g. 10,000) scenarios of the stock price movement which are statistically consistent with the known behavior or model of the stock price, calculating the value of the derivative security at the end of each scenario, and averaging the results. In this example, this procedure would be mathematically equivalent to performing a multidimensional integral in 360 dimensions.
The procedures described above will converge to the correct result if N is sufficiently large, but the rate of convergence is relatively slow. For example, the root-mean-square-error between the estimate after N points and the correct result decreases in proportion to 1l/{square root over (N)}, independent of the dimension of the cube. In financial derivatives, some securities may require values of N as large as 10 million in order to achieve satisfactory accuracy. Such large calculations can take several hours on a personal computer having a Pentium type processor. Such lengthy time delays prevent derivative dealers from providing clients with real-time prices for these securities and thus may result in lost sales or trading opportunities and may also result in trades that are not based on real time information.
Thus, it is desirable to improve the rate of convergence of the estimate to obtain real-time pricing solutions. It has been found that this may be accomplished by replacing the pseudo-random sequence of points with an alternative sequence of points with appropriate properties. Deterministic sequences which cover the multi-dimensional cube more efficiently than pseudo-random seque
Goldenfeld Nigel David
Linde Dmitri
Sokol Alexander
Cangialosi Salvatore
Mayer Brown & Platt
Numerix Corp.
LandOfFree
Interface between two proprietary computer programs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interface between two proprietary computer programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interface between two proprietary computer programs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2533880